数据小白必看：七大排序算法超详细讲解（下）

喜欢做梦

发布于 2024-12-26 09:16:42

10200

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

交换排序

冒泡排序

基本思想

基本思想：将待排序的元素看做是“气泡”，比较相邻两个元素进行交换，每次遍历都会将当前最大（最小）的元素像“气泡”一样，浮到一端。

实现过程：

代码：

    public static  void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg=false;
            for (int j = i; j < array.length-i-1 ; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(flg==false){
                break;
            }
        }
    }
}

时间复杂度：没有讨论优化的情况下：O（N^2），优化后：O（N）;
空间复杂度：O（1）；
稳定性：稳定；

快速排序

基本思想

基本思想：任取待排序元素序列中的某元素作为基准值，通过一趟排序将待排序集合分割成两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素在相应的位置上。

 public static  void quickSort(int[] array){
        //快速排序入口
          quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        //递归结束条件
        if (start>=end){
            return;
        }
        //划分区间
        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

1.Hoare版

实现过程：

思路：

将最左边的数作为基准数；
通过双指针从两端向中间移动，通过内层循环，直到right寻找比tmp大的元素，left寻找比right小的元素，将两下标元素进行交换，直到两指针相遇；
将基准数与两指针相遇的位置进行交换，划分左右区间；

    //Hoare版分割
    public static int partitionHoare(int[] array,int left,int right){
       int tmp=array[left];
       int tmpleft=left;
       //直到两指针相遇结束循环
       while(left<right){
           //right寻找比tmp小的元素
           //所以只要大于等于tmp，那么right向左移动
           while(left<right && array[right]>=tmp){
               right--;
           }
           //left寻找比tmp大的元素
           //所以只要小于等于tmp，那么left向右移动
           while(left<right && array[left]<=tmp){
                left++;
            }
           //将左右指针的元素进行交换
           swap(array,left,right);
       }
       //将基准数与指针相遇的地方交换，划分左右区间
       swap(array,left,tmpleft);
       return left;
    }

可能有的疑惑：

可不可以后面往前面向后面找，为什么是从后面开始往前面找？

答案是不可以的。

如上图所示，从前往后找可能会使left比right更先找到比基准值大的值，然后将他们进行交换，导致左边区间可能出现比基准值大的元素

2.在内层循环，双指针移动过程中为什么left还要写小于right，他进入内层循环的条件不就是left<right吗?

如果要排序的数组是[6,1,4,2],left下标只要没有比tmp下标的元素来的大，那么就要一直向右移动，甚至移到right的右边。right也同理。

3.为什么array[left]和array[right]循环条件为什么还要等于tmp？

如果数组中有相同的元素，而内层循环条件是array[left]<tmp，array[right]>tmp,那么将会造成死循环。

2.挖坑法

实现过程：

思路：

最左边的树作为基准数；
通过双指针从两端向中间移动，通过内层循环，直到right寻找比tmp大的元素，将right的元素给left，left寻找比right小的元素，将left的元素给right，直到两指针相遇；
将基准数给两指针相遇的位置，划分左右区间；

代码：

    public static int partition(int[] array,int left,int right){
        int tmp=array[left];
        while(left<right){
            //右指针寻找比tmp小的值给左指针
            while(left<right && array[right]>=tmp){
                right--;
            }
            //将right下标元素给left下标元素
            array[left]=array[right];
            //左指针寻找比tmp大的值给右指针
            while(left<right && array[left]<=tmp){
                left++;
            }
            //将left下标元素给right下标元素
            array[right]=array[left];

        }
        //将基准数给left或者right下标
        array[left]=tmp;
        return left;
    }

3.前后指针法

实现过程：

思路：

初始化prev指向首位置，cur指向prev的下一个位置；
如果cur的元素小于基准值，并且prev向后移动一位与cur不等，那么将cur与prev中的元素进行交换；
cur遍历完后，交换基准值与left的元素，划分区间。

    public static int partition2(int[] array,int left,int right){
          int prev=left;
          int cur=left+1;
          while(cur<=right){
              if(array[cur]<array[left] && array[++prev]!=array[cur]){
                  swap(array,cur,prev);
              }
              cur++;
          }
          swap(array,prev,left);
          return prev;
    }

优化快速排序

1. 三数取中法选key

  public static void quick(int[] array,int start,int end){
        //递归结束条件
        if (start>=end){
            return;
        }
        //找到中间元素下标
        int midIndex=getMid(array,start,end);
        //将中间元素与首元素进行比较
        swap(array,midIndex,start);
        //划分区间
        int pivot=partition2(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
private static int getMid(int[] array, int left,int right){
        int mid=(left+right)/2;
        //如果left下标小于right下标元素
        if(array[left]<array[right]){
            //比较left与mid
            if(array[left]>array[mid]){
                return left;
            }else if(array[right]<array[mid]){
                //比较right与mid
                return right;
            }else{
                return mid;
            }
            //如果left下标大于right下标元素
        }else{
            //比较left与mid
            if(array[left]<array[mid]){
                return left;
            }else if(array[right]>array[mid]){
                //比较right与mid
                return right;
            }else{
                return mid;
            }
        }
    }

2.递归到小的子区间时，可以考虑使用插入排序

 public static void quick(int[] array,int start,int end){
        //递归结束条件
        if (start>=end){
            return;
        }
        if(end-start+1<=7){
            insertSortRange(array,start,end);
        }
        int midIndex=getMid(array,start,end);
        swap(array,midIndex,start);
        //划分区间
        int pivot=partition2(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static void insertSortRange(int[] array,int start,int end){
        //这里end取闭区间
        for (int i = start+1; i <= end; i++) {
            //将下标i中的元素给tmp；
            int tmp=array[i];
            int j = i-1;
            for (; j >=start; j--) {
                //将j中的元素与tmp中的元素进行比较
                //如果j中的元素大于tmp中的元素，那么将j中的元素放到j+1的元素中
                if(tmp<array[j]){
                    array[j+1]=array[j];
                }else{
                    //否则说明j+1是适合tmp元素的位置，将其插入
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

快速排序非递归

实现过程：

思路：

先对整体数组做一次划分；
将基准元素两边的左右边界进行入栈；
先弹出右边界，在弹出左边界，在左右边界区间中再进行划分，循环此操作直到栈为空为止。

代码：

 public static  void quickSort(int[] array){
        //快速排序入口
        quickNor(array,0,array.length-1);
         // quick(array,0,array.length-1);
    }
 public static void quickNor(int[] array,int left,int right){
        Deque<Integer> stack=new ArrayDeque<>();
        //划分区域
        int pivot=partition(array,left,right);
        //将两边的左右区间放入栈中
        if(pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push(pivot+1);
            stack.push(right);
        }
        //只要栈不为空，就代表还不是整体有序
        while(!stack.isEmpty()){
            //弹出右边界，在弹出左边界
            right=stack.pop();
            left=stack.pop();
            //将左右边界区间在进行分割
            pivot=partition(array,left,right);
            //如果满足条件，在进行入栈
            if(pivot-1>left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right){
                stack.push(pivot+1);
                stack.push(right);
            }
        }        }
 //挖坑法
    public static int partition(int[] array,int left,int right){
        int tmp=array[left];
        while(left<right){
            //右指针寻找比tmp小的值给左指针
            while(left<right && array[right]>=tmp){
                right--;
            }
            //将right下标元素给left下标元素
            array[left]=array[right];
            //左指针寻找比tmp大的值给右指针
            while(left<right && array[left]<=tmp){
                left++;
            }
            //将left下标元素给right下标元素
            array[right]=array[left];

        }
        //将基准数给left或者right下标
        array[left]=tmp;
        return left;
    }

快速排序总结

快速排序整体的综合性能和使用场景都比较好，所以才敢叫快速排序；
稳定性：不稳定；
时间复杂度：最好情况：O（N*logN），最坏情况：O^2;
空间复杂度：最好情况：O（logN）,最坏情况：O（N）；

归并排序

基本思想：

归并排序是一种高效的基于分治策略的排序算法。分治策略：将一个数组分成两个子数组，然后递归的对这两个子数组进行排序，最后将排好序的子树组合并成一个完整的排序数组。

实现过程：

思路：

分解：

如果子数组只有一个元素返回，也就是当left>=right的时候，停止分解；
否则对数组进行左右递归分解；

合并：

创建临时数组tmp；
用两个指针来比较两个元素大小，将小的放入tmp；
将剩余的元素放入tmp中；
将数组放入原数组对应的位置。

代码：

 public static void mergeSort(int[] array){
        mergeSortTmp(array,0,array.length-1);
    }
    //分解
    public static void mergeSortTmp(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //分解：
        int mid=(left+right)/2;
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    //合并
    public static void merge(int[] array,int left,int mid,int right){
        int[] tmp=new int[right-left+1];
        int k=0;
           int s1=left;
           int s2=mid+1;
           while(s1<=mid && s2<=right){
               if(array[s1]<=array[s2]){
                   tmp[k++]=array[s1++];
               }else{
                   tmp[k++]=array[s2++];
               }
           }
           //放入剩余的元素
           while(s1<=mid){
               tmp[k++]=array[s1++];
           }
           while(s2<=right){
            tmp[k++]=array[s2++];
           }
           //保证数组有序
        for (int i = 0; i < k; i++) {
            array[i+left]=tmp[i];
        }
        }

归并排序思考的更多的是解决在磁盘中的外排序问题；
稳定性：稳定；
时间复杂度：O（N*logN）；
空间复杂度：O（N）；

排序算法总结

排序	最好	平均	最坏	空间复杂度	时间复杂度
冒泡排序	O（n）	O（n^2）	O（n^2）	O（1）	稳定
插入排序	O（n）	O（n^2）	O（n^2）	O（1）	稳定
希尔排序	O（n）	O（n^1.3）	O（n^2）	O（1）	不稳定
选择排序	O（n^2）	O（n^2）	O（n^2）	O（1）	不稳定
堆排序	O（n*log（n））	O（n*log（n））	O（n*log（n））	O（1）	不稳定
快速排序	O（n*log（n））	O（n*log（n））	O（n^2）	O（log（n））~O（n）	不稳定
归并排序	O（n*log（n））	O（n*log（n））	O（n*log（n））	O（n）	稳定