写这个的目的在于，说明快速排序的灵活运用。我们来看下关于快速排序中的一部分关键代码：
快速排序代码：
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用 void quicksort(int left,int right) { int i,j,t,temp; if(left>right) return; temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) { //顺序很重要，要先从右边开始找 while(a[j]>=temp && i<j) j--; //再找右边的 while(a[i]<=temp && i<j) i++; //交换两个数在数组中的位置 if(i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //最终将基准数归位 a[left]=a[i]; a[i]=temp; quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程 quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程 }
我们抽出关键部分来分析;
int partition_quickSort(int *arr,int start,int end)
{
int cmp_val=arr[start];
int i=start;
int j=end;
while(i!=j){
while(i<j&&arr[j]>=cmp_val){
j--;
}
while(i<j&&arr[i]<=cmp_val){
i++;
}
if(i<j){
int ex_temp=arr[j];
arr[j]=arr[i];
arr[i]=ex_temp;
}
}
arr[start]=arr[i];
arr[i]=cmp_val;
return i;
}
这代部分代码的功能就是：
那么返回值的
int partition_quickSort(int *arr,int start,int end)
代表的意思是，返回值左边的数都小于返回值，而返回值右边的数都大于返回值。于是我们就可以利用这个性质来解决问题了。
对于这个问题，数组中出现次数超过一半的数字，也就是说在排好序的该数组中，那么该数组中点的元素一定是所求的结果，
但是我们有必要进行对数组进行排序吗？ 答案是否
我们利用刚刚那个快速排序的性质，其返回值左边的数小于他，返回值右边的数大于他，（返回值是数组的一个小标）。
因此只要我们的返回值正好是数组的中点，也就是对应的该元素是排好序的该数组的中点，因为该数组左边的值小于它，右边
的值大于它。
如何使该函数的返回值恰 好是数组的中点呢（array.length/2）？
int moreThanHalfNum_Partition(int *arr,int Length){ if(arr==NULL||Length==0){ return 0; } int low=0; int high=Length-1; int mid=Length>>1; int index= partition_quickSort(arr,low,high); while(index!=mid){ if(index>mid){ index= partition_quickSort(arr,low,index-1); }else{ index= partition_quickSort(arr,index+1,high); } } int key=arr[mid]; if(isMoreHalf(arr,Length,key)){ return key; }else{ return 0; }}
上面的思路是，如果该函数的返回值位于“中点”右边，也就是
index>mid
那么可知，还是那么个性质，该数组下标
小于index的值都小于index对应的元素，该数组下标大于index的值都大于index对应的值。于
是我们的中点肯定位于index左边啦。于是
index= partition_quickSort(arr,low,index-1);
同理否则：
index= partition_quickSort(arr,index+1,high);
还是利用快速排序的性质
int partition_quickSort(int *arr,int start,int end){ int cmp_val=arr[start]; int i=start; int j=end; while(i!=j){ while(i<j&&arr[j]>=cmp_val){ j--; } while(i<j&&arr[i]<=cmp_val){ i++; } if(i<j){ int ex_temp=arr[j]; arr[j]=arr[i]; arr[i]=ex_temp; } } arr[start]=arr[i]; arr[i]=cmp_val; return i; }
这是返回的值的下标左边的元素都小于它的值，下标右边的值的大于它的值，因此只要该函数返回k-1就行了。于是
bool minKDataBeforeArr(int *arr,int Length,int k_bef){ if(arr==NULL||k_bef>Length){ return false; } int start=0; int k_index=0; int end=Length-1; k_index=partition_quickSort(arr,start,end); while(k_index!=k_bef-1){ if(k_index>k_bef-1){ end=k_index-1; k_index=partition_quickSort(arr,start,end); }else{ start=k_index+1; k_index=partition_quickSort(arr,start,end); } } for(int i=0;i<k_bef; i++){ for(int j=k_bef;j<Length; j++){ if(arr[i]>arr[j]){ return false; } } } return true; }
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655480.html
相关资源：数据结构—成绩单生成器
