正文

求出数组前面k个元素或数组中元素大于一半的元素（快速排序与堆排序的灵活运用）

IP云
IP云V管理员/1 阅读
06/19
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

写这个的目的在于，说明快速排序的灵活运用。我们来看下关于快速排序中的一部分关键代码：

快速排序代码：

  1. int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
  2. void quicksort(int left,int right)
  3. {
  4. int i,j,t,temp;
  5. if(left>right)
  6. return;
  8. temp=a[left]; //temp中存的就是基准数
  9. i=left;
  10. j=right;
  11. while(i!=j)
  12. {
  13. //顺序很重要，要先从右边开始找
  14. while(a[j]>=temp && i<j)
  15. j--;
  16. //再找右边的
  17. while(a[i]<=temp && i<j)
  18. i++;
  19. //交换两个数在数组中的位置
  20. if(i<j)
  21. {
  22. t=a[i];
  23. a[i]=a[j];
  24. a[j]=t;
  25. }
  26. }
  27. //最终将基准数归位
  28. a[left]=a[i];
  29. a[i]=temp;
  31. quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
  32. quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
  33. }

我们抽出关键部分来分析;

    1. int partition_quickSort(int *arr,int start,int end)

    {

  2. int cmp_val=arr[start];
  3. int i=start;
  4. int j=end;
  5. while(i!=j){
  6. while(i<j&&arr[j]>=cmp_val){
  7. j--;
  8. }
  9. while(i<j&&arr[i]<=cmp_val){
  10. i++;
  11. }
  12. if(i<j){
  13. int ex_temp=arr[j];
  14. arr[j]=arr[i];
  15. arr[i]=ex_temp;
  16. }
  17. }
  18. arr[start]=arr[i];
  19. arr[i]=cmp_val;
  20. return i;
  21. }
这代部分代码的功能就是：





那么返回值的

  1. int partition_quickSort(int *arr,int start,int end)
 代表的意思是，返回值左边的数都小于返回值，而返回值右边的数都大于返回值。于是我们就可以利用这个性质来解决问题了。
对于这个问题，数组中出现次数超过一半的数字，也就是说在排好序的该数组中，那么该数组中点的元素一定是所求的结果，
但是我们有必要进行对数组进行排序吗？ 答案是否
我们利用刚刚那个快速排序的性质，其返回值左边的数小于他，返回值右边的数大于他，（返回值是数组的一个小标）。
因此只要我们的返回值正好是数组的中点，也就是对应的该元素是排好序的该数组的中点，因为该数组左边的值小于它，右边
的值大于它。
如何使该函数的返回值恰 好是数组的中点呢（array.length/2）？

  1. int moreThanHalfNum_Partition(int *arr,int Length){
  2. if(arr==NULL||Length==0){
  3. return 0;
  4. }
  5. int low=0;
  6. int high=Length-1;
  7. int mid=Length>>1;
  8. int index= partition_quickSort(arr,low,high);
  9. while(index!=mid){
  10. if(index>mid){
  11. index= partition_quickSort(arr,low,index-1);
  12. }else{
  13. index= partition_quickSort(arr,index+1,high);
  14. }
  15. }
  16. int key=arr[mid];
  17. if(isMoreHalf(arr,Length,key)){
  18. return key;
  19. }else{
  20. return 0;
  21. }
  22. }
上面的思路是，如果该函数的返回值位于“中点”右边，也就是

  1. index>mid
那么可知，还是那么个性质，该数组下标小于index的值都小于index对应的元素，该数组下标大于index的值都大于index对应的值。于
是我们的中点肯定位于index左边啦。于是

  1. index= partition_quickSort(arr,low,index-1);
同理否则：

  1. index= partition_quickSort(arr,index+1,high);

还是利用快速排序的性质

  1. int partition_quickSort(int *arr,int start,int end){
  2. int cmp_val=arr[start];
  3. int i=start;
  4. int j=end;
  5. while(i!=j){
  6. while(i<j&&arr[j]>=cmp_val){
  7. j--;
  8. }
  9. while(i<j&&arr[i]<=cmp_val){
  10. i++;
  11. }
  12. if(i<j){
  13. int ex_temp=arr[j];
  14. arr[j]=arr[i];
  15. arr[i]=ex_temp;
  16. }
  17. }
  18. arr[start]=arr[i];
  19. arr[i]=cmp_val;
  20. return i;
  21. }
这是返回的值的下标左边的元素都小于它的值，下标右边的值的大于它的值，因此只要该函数返回k-1就行了。于是

  1. bool minKDataBeforeArr(int *arr,int Length,int k_bef){
  2. if(arr==NULL||k_bef>Length){
  3. return false;
  4. }
  5. int start=0;
  6. int k_index=0;
  7. int end=Length-1;
  8. k_index=partition_quickSort(arr,start,end);
  9. while(k_index!=k_bef-1){
  10. if(k_index>k_bef-1){
  11. end=k_index-1;
  12. k_index=partition_quickSort(arr,start,end);
  13. }else{
  14. start=k_index+1;
  15. k_index=partition_quickSort(arr,start,end);
  16. }
  17. }
  18. for(int i=0;i<k_bef; i++){
  19. for(int j=k_bef;j<Length; j++){
  20. if(arr[i]>arr[j]){
  21. return false;
  22. }
  23. }
  24. }
  25. return true;
  26. }
 


来自为知笔记(Wiz)