数据结构 —— 快速排序 + 二分搜索法
今日一言：
“想想，说人生无悔，都是赌气的话，
人生若无悔，那该多无趣啊。”
——《一代宗师》
数据结构 —— 快速排序 + 二分搜索法
这是一个月前写的然后忘了交的作业，水一下
C语言实现
/*********************************************************************************
*
* 二分搜索 + 快排
* create: 2020年4月21日 20点52分
* author: LOS(小鱼)
*
* *******************************************************************************
*
*********************************************************************************/
#include "stdio.h"
#include "stdlib.h"
#define size 50
int array[size];
typedef struct{
int left;
int right;
} ArrayC;
void getArrayList(){
int i = 0 , n ;
for ( ; i < size ; i++ ){
printf("请输入第%2d个数: ",i+1);
scanf("%d",&n);
fflush(stdin);
array[i] = n;
}
}
void getArrayByRand(){
int i = 0 ;
srand((unsigned)time(NULL));
printf("排序前：[");
for ( ; i < size ; i++ ){
array[i] = rand() % 50 + 10;
if( i == size - 1) printf("%d ]\n",array[i]);
else printf("%d, ",array[i]);
}
}
int binarySearchIndex(int value){
int left = 0;
int right = size-1;
int mI;
int temp;
while( left <= right ){
mI = (left+right)/2;
temp = array[mI];
if( temp < value ){
left = mI + 1;
}
if ( temp > value ){
right = mI - 1;
}
if( temp == value ) return mI;
}
return -1;
}
void printArray(){
printf("排序后：[ ");
int i = 0;
for ( ; i<size ; i++ ){
if( i != size-1 ) printf("%d, ",array[i]);
else printf("%d ]\n",array[i]);
}
}
void quickSort(ArrayC temp){
int tmp;//作为交换的临时数
int maxLeft = temp.right;//关键数更大的数中最为左边的索引
int keyValue = array[temp.right];//关键数
int keyIndex = temp.right;//关键数的索引
int left = temp.left;//存储初始时的temp.left索引
while( temp.left < temp.right ){
if( array[temp.left] > keyValue ){
//若第一次查询到比关键数大的数，则存储其索引
if( keyIndex == maxLeft ){
maxLeft = temp.left;
}
} else if(array[temp.left] <= keyValue ) {
//将不大于关键数的数全部交换到左边
if( keyIndex != maxLeft ){
tmp = array[maxLeft];
array[maxLeft] = array[temp.left];
array[temp.left] = tmp;
maxLeft++;
}
}
temp.left++;
}
//keyValue is max
if( maxLeft == keyIndex ){
//keyIndex默认是最右边，排序keyIndex左边的数
if ( keyIndex > left ){
ArrayC a;
a.right = keyIndex-1;
a.left = left;
quickSort2(a);
}
} else {
//将关键数交换到"中间位置"
tmp = array[maxLeft];
array[maxLeft] = array[keyIndex];
array[keyIndex] = tmp;
//left, 排序关键词左边的数
if( maxLeft > left ){
ArrayC b;
b.left = left;
b.right = maxLeft - 1;
quickSort2(b);
}
//right，排序含关键词在内的右边的数
if( maxLeft < temp.right ){
ArrayC c;
c.left = maxLeft;
c.right = temp.right;
quickSort2(c);
}
}
}
void printLineWithln(){
printf("----------------------------\n");
}
void showBar(char *title,char *content){
printLineWithln();
printf("%s\n",title);
printLineWithln();
printf("%s\n",content);
}
void show(){
int n;
getArrayByRand();
ArrayC a;
a.left = 0;
a.right = size - 1;
quickSort2(a);
printArray();
printf("请输入您要查找的数：");
scanf("%d",&n);
int i = binarySearchIndex(n);
if ( i != -1 ){
printf("查找成功\n");
printf("值：%5d在数组中的索引为：%2d\n",n,i);
} else {
printf("查找失败\n");
printf("值：%5d不在数组中\n",n);
}
}
void main( ){
int n;
while(1){
show();
printLineWithln();
printf("1.重新开始\t0.退出程序\n");
scanf("%d",&n);
fflush(stdin);
if ( n ){
system("cls");
} else {
printf("bye");
return;
}
}
}
运行结果
排序前：[35, 38, 35, 33, 38, 18, 23, 51, 53, 50, 43, 12, 58, 22, 44, 42, 31, 56, 48, 34, 58, 43, 45, 13, 56, 41, 41, 13,
12, 31, 20, 29, 37, 10, 19, 47, 48, 43, 30, 15, 18, 36, 44, 39, 23, 49, 40, 30, 34, 34 ]
排序后：[ 10, 12, 12, 13, 13, 15, 18, 18, 19, 20, 22, 23, 23, 29, 30, 30, 31, 31, 33, 34, 34, 34, 35, 35, 36, 37, 38, 38
, 39, 40, 41, 41, 42, 43, 43, 43, 44, 44, 45, 47, 48, 48, 49, 50, 51, 53, 56, 56, 58, 58 ]
请输入您要查找的数：42
查找成功
值： 42在数组中的索引为：32
----------------------------
1.重新开始 0.退出程序