devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

快速排序与归并排序_将待排序的数据分为两个子区间

作者：代码探险家 | 2024-06-23 17:00:48

赞

踩

将待排序的数据分为两个子区间

一、快速排序

1.基本思想

从待排序的关键字中选取一个关键字，将小于该关键字的移到前面，而将大于该关键字的移到后面，结果将待排序记录序列分为两个子表，最后将该关键字插到其分界线处。这个过程称为一趟快速排序。然后对两个子表继续进行快速排序。

2.具体步骤

    1）选择一个基准值（选择最右区间，最右边的数作为基准值）  选择基准值的方法有取边法、随机法和三数取中法。
    2）遍历整个区间，每个数都和基准值做比较，并且发生一定交换。(partition的方法有hover法、挖坑法和前后下标法）
    遍历结束后，使得
    比基准值小的数（包括等于）都在基准值的左边
    比基准值大的数（包括等于）都在基准值的右边
    3）分治算法
    分别对左右两个小区间进行同样的方式处理，直到小区间的size==0或者size==1

切割的算法分析：

1)hover法：

从左边找比基准值大的数，从右边找比基准值小的数。然后交换这两个数，直到begin==end，再将基准值插入到begin中。

2）挖坑法:

先记录基准值，然后从左边选出比基准值大的数，将该数填到基准值的位置上，接着从右边遍历，找出比基准值小的数，填到begin的位置上。直到begin==end，最后将基准值填到begin的位置上。

3）前后下标法：

设置两个下标引用：d和i，保证d前面的数都比基准值小(只要array[i]<pivot，就交换d和i对应的元素）[d,i]无序，直到i==right，则d的位置就是基准值的位置，将arr[d]和arr[right]交换。

3.代码

  1. public class QuickSort {
  2.     private static void quickSort(int[] array){
  3.         quickSortIR(array,0,array.length-1);
  4.     }
  5. //[left,right]
  6.     private static void quickSortIR(int[] array, int left, int right) {
  7.         //终止条件  区间里只有一个或者没有
  8.         if(left>=right){
  9.             return;
  10.         }
  11.         //1.取基准值
  12.        int key=array[right];
  13.         //2.分割
  14.         int pivotIndex=partition3(array,left,right);//返回基准值在的下标
  15.  
  16.         //[left,pivotIndex-1]:比基准值小的数   [pivotIndex+1,right]:比基准值大的数
  17.         quickSortIR(array,left,pivotIndex-1);
  18.         quickSortIR(array,pivotIndex+1,right);
  19.     }
  20. //分割 hover法  从左边找比基准值大的数，从右边找比基准值小的数。然后交换这两个数，直到begin==end，再将基准值插入到begin中。
  21.     private static int partition1(int[] array, int left, int right) {
  22.         int begin=left;
  23.         int end=right;
  24.         int pivot=array[right];
  25.         while(begin<end){
  26.             while(begin<end&&array[begin]<=pivot){
  27.                 begin++;
  28.             }
  29.             while(begin<end&&array[end]>=pivot){
  30.                 end--;
  31.             }
  32.             swap(array,begin,end);
  33.         }
  34.         //begin==end  则基准值要插入的位置是array[begin]，交换两个数
  35.         swap(array,begin,right);
  36.         return begin;
  37.     }
  38.     //挖坑法  先记录基准值，然后从左边选出比基准值大的数，将该数填到基准值的位置上，接着从右边遍历，找出比基准值小的数，填到begin的位置上。
  39.     //直到begin==end，最后将基准值填到begin的位置上。
  40.     private static int partition2(int[] array,int left,int right){
  41.         int pivot=array[right];
  42.         int begin=left;
  43.         int end=right;
  44.         while(begin<end){
  45.             while(begin<end&&array[begin]<=pivot){
  46.                 begin++;
  47.             }
  48.             array[end]=array[begin];
  49.             while(begin<end&&array[end]>=pivot){
  50.                 end--;
  51.             }
  52.             array[begin]=array[end];
  53.         }
  54.         array[begin]=pivot;
  55.         return begin;
  56.     }
  57. //前后下标法  设置两个下标引用，d和i，保证d前面的数都比基准值小(只要array[i]<pivot，就交换d和i对应的元素）[d,i]无序，直到i==right，则d的位置就是基准值的位置，将arr[d]和arr[right]交换。
  58.     private static int partition3(int[] array,int left,int right){
  59.         int d=left;
  60.         for(int i=left;i<=right;i++){
  61.             if(array[i]<array[right]){
  62.                 swap(array,i,d);
  63.                 d++;
  64.             }
  65.         }
  66.         swap(array,d,right);
  67.         return d;
  68.     }
  69.     private static void swap(int[] array, int begin, int end) {
  70.         int temp=array[begin];
  71.         array[begin]=array[end];
  72.         array[end]=temp;
  73.     }
  74.  
  75.     public static void main(String[] args) {
  76.         int[] array=new int[]{33,4,8,3,10,21,9,4};
  77.         quickSort(array);
  78.         for(int item:array){
  79.             System.out.print(item+" ");
  80.         }
  81.     }
  82. }

取基准值还有三数取中法，取值的代码为：

  1.   //返回三数取中的下标
  2.     private static int sanshuQuZhong(int[] array,int left,int right){
  3.         int mid=left+(right-left)/2;
  4.         if(array[left]>array[right]){
  5.             if(array[left]<array[mid]){
  6.                 return left;
  7.             }else if(array[mid]>array[right]){
  8.                 return mid;
  9.             }else{
  10.                 return right;
  11.             }
  12.         }else{
  13.             if(array[right]<array[mid]){
  14.                 return right;
  15.             }else if(array[mid]>array[left]){
  16.                 return mid;
  17.             }else{
  18.                 return left;
  19.             }
  20.         }
  21.     }
  22. private static void quickSortInnerSan(int[] array, int left, int right) {
  23.         //直到size==1或size==0
  24.         if(left==right){
  25.             return;//size==1
  26.         }
  27.         if(left>right){
  28.             return;//size==0
  29.         }
  30.         //要排序的区间是array[left,right]
  31.         //1.找基准值
  32.         int originIndex=sanshuQuZhong(array,left,right);
  33.         swap(array,originIndex,right);
  34.         //2.遍历整个区间，把区间分为三部分。  pivotIndex:基准值的下标
  35.         int pivotIndex=parition3(array,left,right);
  36.         //比基准值小的[left,pivotIndex-1]
  37.         //比基准值大的[pivotIndex+1,right]
  38.         //3.分治算法
  39.         //处理比基准值小的区间
  40.         quickSortInner(array,left,pivotIndex-1);
  41.         //处理比基准值大的区间
  42.         quickSortInner(array,pivotIndex+1,right);
  43.     }

    4.复杂度与稳定性

             时间复杂度                                          空间复杂度
   最好                平均             最坏             最好         平均        最坏    
   O(nlog(n))     O(nlog(n))    O(n^2)        O(logn)      O(log(n))     O(n)

不稳定

二、归并排序

1.基本思想

将待排序的元素序列分成两个长度相等的子序列，对每一个子序列进行排序，然后将它们合并成一个序列。

2.基本步骤

1）把要排序区间平均切分两部分
2）分治算法，对左右两个区间进行同样方式的排序
    直到
        size==1 已经有序
        size==0  区间没有数了（实际不会走到）
3）合并左右两个有序区间到一个有序区间（需要额外空间）

3.代码

  1. public class mergeSort {
  2.     public static void mergeSort(int[] array){
  3.         int[] extra=new int[array.length];
  4.         mergeInner(array,0,array.length,extra);
  5.     }
  6.     //分治算法，对左右两个区间进行同样方式的排序  [low,high)
  7.     private static void mergeInner(int[] array,int low,int high,int[] extra){
  8.         if(low==high-1||low>=high){//如果区间中只有一个数，或没有数，此时有序。则直接返回
  9.             return;
  10.         }
  11.         //计算左右区间   [low,mid)  右：[mid,high)
  12.         int mid=low+(high-low)/2;
  13. //        分治算法，处理两个小区间
  14.         mergeInner(array,low,mid,extra);
  15.         mergeInner(array,mid,high,extra);
  16.         //两个数组已经有序，下面进行合并两个有序数组
  17.         merge(array,low,mid,high,extra);
  18.     }
  19.         //合并两个有序数组  [low,mid)  [mid,high)
  20.     private static void merge(int[] array, int low, int mid,int high, int[] extra) {
  21.         int x=0;
  22.         int i=low;
  23.         int j=mid;
  24.         while(i<mid&&j<high){
  25.             if(array[i]<=array[j]){
  26.                 extra[x++]=array[i++];
  27.             }else{
  28.                 extra[x++]=array[j++];
  29.             }
  30.         }
  31.         //有一个数组的所有数都被搬完了
  32.         while(i<mid){
  33.             extra[x++]=array[i++];
  34.         }
  35.         while(j<high){
  36.             extra[x++]=array[j++];
  37.         }
  38.         //搬移 extra[0,high-low)-->array[low,high)
  39.         for(int k=low;k<high;k++){
  40.             array[k]=extra[k-low];
  41.         }
  42.     }
  43.  
  44.     public static void main(String[] args) {
  45.         int[] array=new int[]{23,1,45,9,8,5,6,3,10};
  46.         mergeNoR(array);
  47.         for(int item:array){
  48.             System.out.print(item+" ");
  49.         }
  50.     }
  51. //非递归版本
  52.     public static void mergeNoR(int[] array){
  53.         int[] extra=new int[array.length];
  54.         for(int i=1;i<array.length;i=i*2){
  55.             for(int j=0;j<array.length;j+=2*i){
  56.                 int low=j;
  57.                 int mid=j+i;
  58.                 if(mid>=array.length){
  59.                     //越界
  60.                     continue;
  61.                 }
  62.                 int high=mid+i;
  63.                 if(high>array.length){
  64.                     high=array.length;
  65.                 }
  66.                 merge(array,low,mid,high,extra);
  67.             }
  68.         }
  69.     }
  70. }

4.复杂度与稳定性分析

时间复杂度：O(n*log(n))
空间复杂度：O(n)-->extra[array.length]（统一开辟的）  合并n长  log(n)调用栈 "+"的关系
稳定

三、各排序算法的应用场景

冒泡排序：优化后的冒泡排序可用于当数据基本有序且数据量较少时。

直接插入排序：在待排序的关键字序列基本有序且数据量较少时。

希尔排序：数据量较小且基本有序时。

选择排序：数据规模较小时。

堆排序：处理数据量大的情况，数据呈流式输入时用堆排序也很方便。

归并排序：数据量较大且要求排序稳定时。

快速排序：处理大量数据时。

排序算法的稳定性：

稳定算法：冒泡排序、直接插入排序、归并排序。

不稳定算法：希尔排序、简单选择排序、堆排、快排

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/750123
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号