详解七大排序算法-阿里云开发者社区

对于排序算法，是我们在数据结构阶段，必须要牢牢掌握的一门知识体系，但是，对于排序算法，里面涉及到的思路，代码……各种时间复杂度等，都需要我们，记在脑袋瓜里面！！尽量一丢丢不要出现差错！面试所必备的精彩提问！！

言归正传：对于排序，我们首先需要知道的是：排序的概念！！

排序的概念！

所谓的排序，，就是使一串记录，按照其中的某个或者某些关键字的大小，递增递减的排序起来的操作！！

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍然在r[j]之前，这种排序算法是稳定的，否则是不稳定的！！

就比如：9 5 2 7 3 6 4 5 8 0 这些数据而言！

内部排序：数据元素部分放在内存的排序

外部排序：数据元素不能同时放在内存中，根据排序过程的要求不同，在内存与外存之间移动数据的排序（要排序的数据，在内存中放不下！！）

下面笔者就以七种常见的排序算法为列，来带大家走进排序！！（直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序）

1.插入排序：

插入排序：把待排序的记录按照其关键码值的大小，逐个插入到一个已经排序好的有序序列中，直到所有的记录插完为止，从而得到一个新的有序序列（扑克牌）

下面请看笔者的代码：

public static void insertSort(int[] arr){//对传入的数组进行排序
        for (int i = 1; i<arr.length; i++){
            for (int j = i-1; j>=0; j--){
                if(arr[j]>arr[j+1]){//稳定的
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }else
                    break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void main(String[] args) {
        int[] array={12,56,32,67,10,19,4};
        insertSort(array);
    }

2.希尔排序

希尔排序的思想：先选定一个整数，把待排序文件中的所有记录分成多个组，所有距离为一样的放在同一个组内，并对每一组的记录进行插入排序，取重复上述分组和排序的工作，当达到=1时，所有记录在统一组内排序好（先分组，5组，3组，最后为1组）

假设初始的数据为： 9 1 2 5 7 4 8 6 3 5

那么，我们有着一下的简单排序过程：

经过上述的过程，我们可以看出：组数越多，每组进行排序的数据越少！（两两交换（使用插入排序）越有序越快），组数越少，每组数据越多（数据在慢慢变得有序）

那么，我们对于希尔排序，有着一下的几点总结：

希尔排序是对直接插入排序算法的优化！
当gap>1时，都是预排序，目的是让数组接近有序，当gap=1时，数组已经接近有序了，这样就会很快，这样整体而言，可以达到优化的效果，我们实现后可以进行性能测试的对比！
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中，给出的希尔排序的时间复杂度不固定！

有了上述的思考，我们接下来就该实现一下代码了：

public static  void shellSort(int[] array){
        int gap=array.length;//分组
        while (gap>1){
            shell(array,gap);
            gap=gap/2;
        }
        //整体进行插入排序，此时gap=1
        shell(array,1);
    }
    //插入排序
    public static void shell(int[] array,int gap){
        for (int i = 0; i <array.length; i++) {
            int tmp=array[i];
            int j=i-gap;
            for(;j>=0;j=j-gap){
                if (array[j]>tmp){
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    public static void main(String[] args) {
        int[] array={12,56,32,67,10,19,4};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }

3.选择排序

在了解选择排序之前，我们需要知道的是：

选择排序的思想:每一次从待排序的数据元素中选出最小（最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完，直接选择排序！

第一次从R[0]到R[n-1]中选出最小值，与R[0]进行交换，第二次从R[1]到R[n-1]中选出最小值与R[1]交换……，以此类推，从而得到从小到大的有序排序

经过上面的简单分析，我们可以得出下列的有效代码：

public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                    //minIndex保存最小数据的下标值！
                }
            }
            swap(array, i, minIndex);
        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void main(String[] args) {
        int[] array={12,56,32,67,10,4};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }

4.堆排序

对于堆排序，是指利用堆积树（堆），这种数据结构所设计的一种排序算法，它是一种选择排序，通过堆来进行选择数据

需要注意的是：排升序建大堆，排降序建小堆！！

那么，根据笔者之前的堆排序的环节：https://blog.csdn.net/weixin_64308540/article/details/129217324?spm=1001.2014.3001.5502我们可以有着一下的简单代码：

public static void heapSort(int[] array){
        createBigHeap(array);//创建一个大根堆
        int end=array.length-1;
        while (end>0){//等于0的时候就不换了
            swap(array,0,end);//交换
            shiftDown(array,0,end);//向下调整
            end--;
        }
    }
    private static void createBigHeap(int[] array){
        //建立大根堆从最后一颗子树开始
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
            //array,length是指结束位置
        }
    }
    //向下调整
    private static void shiftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while (child<len){//至少有左孩子
            if (child+1<len && array[child]<array[child+1]){//有右孩子
                //此时child是左孩子最大值的下标
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);//交换
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void main(String[] args) {
        int[] array={12,56,32,67,10,4};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

5.交换排序

对于交换排序，我们在之前就已经有过接触，其实就是最简单的冒泡排序

交换排序的基本思想：所谓交换就是根据序列中的两个记录键值的比较结果，交换这两个记录在序列中的位置！

交换排序的特点：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

下面笔者就以冒泡排序来进行书写代码：

方法1：

public static void bubblesort2(int[] array ) {
        //趟数
        for (int i = 0; i < array.length-1; i++) {
            //每趟执行的次数
            boolean flg=false;
            for(int j=0;j<array.length-1-i;j++) {
                if(array[j]>array[j+1]) {
                    int tmp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=tmp;
                }
                flg=true;
            }
            if(flg==false) {
                return ;
            }
        }
    }
    public static void main(String[] args) {
        int[] array={1,29,10,36,5,21,46,3,6};
        bubblesort2(array);
        System.out.println(Arrays.toString(array));
    }

方法2：

public static void bubbleSort2(int[] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j]>array[j+1])
                    swap(array,j,j+1);
            }
        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void main(String[] args) {
        int[] array={12,56,32,67,10,19,4};
        bubbleSort2(array);
        System.out.println(Arrays.toString(array));
    }

在上述代码中，方法1是对方法2的简单优化！！

在方法1中，我们通过一个：boolean flg=false;来优化了代码！！原因在于，在进行冒泡排序的时候，可能对于一串数据，排到一半就有序了，那么，在没有优化之前，肯定还得一个一个尝试去遍历，但是，在优化以后，可以节约时间！！

6.快速排序

快速排序的思想：任取待排序元素序列中的某元素（一般是第一个元素），作为基准值，按照该排序码，将待排序的集合分为两个子序列，左子序中的所有元素均小于基准值，右子序中的所有元素均大于基准值，然后最左右子序列都重复该过程，直到所有的元素都排序在相应的位置为止！！

对于上述的简单思想，我们有着挖坑法！Hoare法！

下面我们先讲解一下挖坑法：

先将第一个数据存放在一个临时变量key中，形成一个坑位！

设置两个变量i，j，排序开始的时候，i=0，j=N-1！
以第一个数组元素作为关键数据，赋值给key，即key=A[0]！
从j开始向前搜素，即由后开始向前搜素（j--),找到第一个小于key的值A[j],将A[j]与A[i]的值进行交换！
从i开始向后搜素，即由前开始向后搜素（i++），找到第一个大于key的值A[i]，将A[i]与A[j]的值交换！
重复步骤3，4，直到i==j为止！

对于上述的思路，我们可以用递归来实现！！

package zyh.example.demo.algorithm.kuaisupaixu;
import java.util.Arrays;
/**
* @ClassName KuaiPai13
* @Author zhangyonghui
* @Description
* @Date 2022/3/29 11:26
* @Version 1.0
**/
public class KuaiPai13 {
  public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
  }
  /**
   * 快速排序--挖坑法
   * @param arr 数组
   * @param startIndex 左边界索引
   * @param endIndex 右边界索引
   */
  public static void quickSort(int[] arr, int startIndex, int endIndex) {
        // 递归结束条件：startIndex大等于endIndex的时候
        if (startIndex >= endIndex) {
              return;
        }
        // 得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        // 用分治法递归数列的两部分
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
  }
  /**
   * 具体每一轮的快速排序：
   * @param arr 数组
   * @param startIndex 左边界索引
   * @param endIndex 右边界索引
   * @return 返回基准值的位置，此时基准值左边的元素都小于基准值，基准值右边的元素都大于基准值
   */
  private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        // 初始化坑的位置，初始等于pivot基准值的位置
        int kengIndex = startIndex;
        //初始化左右游标/指针
        int leftYb = startIndex;
        int rightYb = endIndex;
        //大循环在左右指针重合时结束
        while ( leftYb<rightYb ) {
              //right指针从右向左进行比较
              // leftYb<rightYb ，左游标永远小于右游标，是遍历元素并发生元素变动的前提：
              while ( leftYb<rightYb) {
                    // 先遍历右边，
                    //  如果元素大于基准值--右游标左移：
                    if (arr[rightYb] >= pivot) {
                          rightYb--;
                    }else{ //如果右边的当前元素小于基准值了，那么将该元素填入坑中，该元素本来的位置成为新的坑；
                          arr[kengIndex] = arr[rightYb];
                          kengIndex = rightYb;
                          leftYb++;
                          break;
                    }
              }
              //再遍历左边，
              // leftYb<rightYb ，左游标永远小于右游标，是遍历元素并发生元素变动的前提：
              while (leftYb<rightYb) {
                    //如果元素小于基准值--左游标右移，
                    if (arr[leftYb] <= pivot) {
                          leftYb++;
                    }else{  //如果左边的当前元素大于基准值了，那么将该元素填入坑中，该元素本来的位置成为新的坑；
                          arr[kengIndex] = arr[leftYb];
                          kengIndex = leftYb;
                          rightYb--;
                          break;
                    }
              }
        }
        //跳出了大循环，说明此时此刻左右游标是重合的，这时将基准值放在重合位置(最后一个坑)，
        // 此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
        arr[kengIndex] = pivot;
        return kengIndex;
  }
}

接下来进入Hoare法！

right找到比基准小的停下来，left找到比基准大的停下来，进行比较，循环往复，最后当right==left的时候，将此时对应的值与基准进行比较！

请看笔者代码：

public class Main {
    static int[] a= {5, 3, 1, 9, 8, 2, 4, 7};
    public static void main(String[] args) {
        fastsort(0, a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
    private static int Hoare(int l, int r) {
        int p = a[l];
        int i = l-1;
        int j = r+1 ;
        while (true) {
            do {
                j--;
            } while (a[j] > p);
            do {
                i++;
            } while (a[i] < p);
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            } else
                return j;
        }
    }
    private static void fastsort(int l, int r) {
        if (l < r) {
            int s = Hoare(l, r);
            fastsort(l, s);
            fastsort(s+1, r);
        }
    }
}

7.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列，即，先使每个子序列有序，再使子序列断间有序！

主要的思路及其过程，如下图所示：

那么，接下来请看代码吧！！（递归实现）

//递归实现
public static void mergeSort(int[] array){
        mergeSortFunc(array,0, array.length);
    }
    private static void mergeSortFunc(int[] array,int left,int right){
        if (left>=right){
            return;
        }
        //分解
        int mid=(left+right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);//合并
    }
    private static void merge(int[] array,int start,int end,int mid){
        int s1=start;
        int s2=mid+1;
        int[] tmp=new int[end-start+1];//申请一个数组
        int k=0;//tmp数组下标
        while (s1<=mid && s2<=end){
            if (array[s1]<= array[s2]){
                tmp[k++]=array[s1++];
            }else {
                tmp[k++]=array[s2++];
            }
        }
        while (s1<=mid){
            tmp[k++]=array[s1++];
        }
        while (s2<=end){
            tmp[k++]=array[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i+start]=tmp[i];
        }
    }

感兴趣的老铁，可以看一下非递归实现的：

//非递归
    public static void mergeSort2(int[] array){
        int gap=1;
        while (gap<array.length){
            for (int i = 0; i < array.length; i++) {
                int left=i;
                int mid=left+gap+1;
                if (mid>= array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if (right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap=gap*2;
        }
    }

七大排序算法大致就到此结束了！！拜拜！

详解七大排序算法