本文共 13533 字，大约阅读时间需要 45 分钟。

目录

---

一、相关术语介绍

• 稳定：在原待排序序列中，若两个数 a == b，且a在b前面，排序之后，a仍然在b前面，则称该排序算法是稳定的。
• 不稳定：在原待排序序列中，若两个数 a == b，且a在b前面，排序之后，a可能在b后面，则称该排序算法是不稳定的。
• 内排序：所有排序操作都在内存中完成。
• 外排序：由于待排序数据太大，因此把数据放在磁盘中，而排序过程通过磁盘和内存的数据传输才能进行。
• 时间复杂度：描述算法运行时间的函数。
• 空间复杂度：描述算法所需要的内存空间大小。

 

注：本文所介绍的六种排序算法都是内排序。

 

二、排序算法分类

除了按照排序操作是否需要借助外存分为内排序、外排序之外，排序操作还可以基于排序过程是否需要比较元素大小而分为比较排序和非比较排序。

本文介绍的六种经典排序算法都属于比较排序，在排序的最终结果里，元素之间的次序依赖于它们之间的比较，每个数都必须和其他数进行比较，才能确定自己的位置。比较排序的优势是适用于各种规模的数据，也不在乎数据的分布，都能进行排序。即比较排序适用于一切需要排序的情况。

非比较排序比如计数排序、基数排序、桶排序等，时间复杂度较低，一般只需要一次遍历即可，时间复杂度可以达到O(n)。但由于非比较排序需要占用空间来确定唯一的位置，所以对数据规模和数据分布有一定的要求，本文不做介绍。

 

三、各排序算法的比较

排序算法	平均时间复杂度	最好时间复杂度	最差时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O (n)	O(n²)	O (1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O (1)	不稳定
插入排序	O(n²)	O (n)	O(n²)	O (1)	稳定
归并排序	O (n log n)	O (n log n)	O (n log n)	O (n)	稳定
快速排序	O (n log n)	O (n log n)	O(n²)	O (log n)	不稳定
堆排序	O (n log n)	O (n log n)	O (n log n)	O (1)	不稳定

 

对于冒泡排序、选择排序 、插入排序来说，若问题规模为n，需要扫描一遍这n个数（找元素），还需要比较n次（找位置），所以平均时间复杂度都为O(n²)；而对于归并排序、快速排序和堆排序来说，仍然需要扫描一遍这n个数（找元素），但是找位置的问题规模通过分治法削减为log n次（找位置），所以平均时间复杂度为O(nlogn)。

 

四、具体算法介绍

注：比较排序中可能需要交换两个数，所以先自定义一个交换方法swap用于实现此功能，后续排序算法中即可直接调用swap方法完成两个数的交换。

//错误的写法：交换两个数（注意java参数传递是引用传递而不是数值传递，这里注意交换函数的写法）/*private static void swap(int a, int b){     int temp = a;     a = b;     b = temp;}*///正确的写法：//交换函数，交换数组中的两个数private static void swap(int[] arr, int i, int j){     int temp = arr[i];     arr[i] = arr[j];     arr[j] = temp;}

 

1. 冒泡排序

(1) 思想概述：

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 

(2) 算法描述:

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

(3) 排序示例：

(4) Java实现：

//冒泡排序    private static int[] bubbleSort(int[] arr){        int len = arr.length;        if(len > 0){            for(int i = 0 ; i < len ; i++){                for(int j = 0 ; j < len - 1 - i ; j++){                    if(arr[j] > arr[j + 1]){                        //swap(arr[j], arr[j + 1]);                        swap(arr, j, j + 1);                    }                }            }        }        return arr;    }

或

//冒泡排序private static int[] bubbleSort(int[] arr){      int len = arr.length;      if(len > 0){          for(int i = len - 1 ; i > 0 ; i--){              for(int j = 0 ; j < i ; j++){                  if(arr[j] > arr[j + 1]){                      //swap(arr[j], arr[j + 1]);                      swap(arr, j, j + 1);                  }              }          }      }      return arr;}

(5) 复杂度分析：

空间复杂度：不需要额外空间，故空间复杂度为O(1)。

时间复杂度：

最佳情况（O(n)）：可以在for循环之前定义一个boolean变量isSwapped记录是否产生了两个数交换，初始为false，当遍历过程中，若发现前面一个数比后面一个数大，需要交换它们，并将isSwapped置为true，当第一遍遍历完之后（即内层循环第一次执行完），如果isSwapped仍然为false，说明第一次遍历过程中没有产生交换，也就是说原序列所有数都是按照升序排列的，那么可以直接结束排序，这时候时间复杂度达到最优，为O(n)。

最差情况：（O(n²)）：原数组为降序，每相邻的两个元素都得交换 ，需要扫描一遍这n个数（找元素：O(n)），还需要比较n次（找位置：O(n)），时间复杂度为O(n²)。

平均情况：O(n²)

 

2. 选择排序

(1) 思想概述：

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（或最大）元素，存放到已排序序列（初始为空）的起始（或末尾）位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾（或队首 ）。以此类推，直到所有元素均排序完毕。

(2) 算法描述:

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第 i 趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

(3) 排序示例：

(4) Java实现：

//选择排序    private static int[] selectSort(int[] arr){        int len = arr.length;        if(len > 0){            //控制遍历轮数，每一轮遍历结束，i处存放的都是未排序序列中的最小值（最后一个数不用单独遍历，所以            //遍历轮数为 （len - 1）轮            for(int i = 0 ; i < len - 1; i++){                int minIndex = i;                //遍历未排序序列，找当前未排序序列中的最小值                for(int j = i + 1 ; j < len ; j++){                    if(arr[j] < arr[minIndex]){                        minIndex = j;                    }                }                if(i != minIndex){                    swap(arr, i , minIndex);                }            }        }        return arr;    }

(5) 复杂度分析：

空间复杂度：不需要额外空间，故空间复杂度为O(1)。

时间复杂度：

因为不管原始序列的顺序是什么样的，每一轮比较都只是选出第（ i + 1 ）小的元素，其余元素的大小顺序并不能保证， 所以不能提前结束，不管什么情况都要进行O(n)的找元素和O(n)的找位置，最好、最坏、平均时间复杂度都是O(n²)。

(6) 稳定性：

这里要注意选择排序是不稳定的，如果单纯看每一轮选择当前未排序序列中最小的元素时，若存在两个值相等的最小元素a和b，会优先选择在序列中先出现的元素加入已排序序列，这样看仿佛选择排序是稳定的。但是，由于将该元素加入已排序序列是通过交换实现的，有可能被交换的那个元素被交换到和该元素值相等的元素的后面去了，这样就有可能造成不稳定。比较抽象，举个例子帮助理解：

原序列：{2,3,5,2,1}

第一轮选择排序中，第五个数1为最小，它和第一个数2交换，这样，第一个数2就被交换到第五个位置了，排序后结果为{1,3,5,2,2}；

第二轮选择排序中，2应该是最小的，但是序列中有两个2，这时候会优先选择前面的那个2，即在第四位的那个2，但是在原序列中，这个2本来是在第一个2后面的，显然发生了顺序交换，因此产生了不稳定。

所以，因为选择排序的交换可能会造成排序的不稳定性。

 

3. 插入排序

(1) 思想概述：

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

(2) 算法描述:

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

(3) 排序示例：

(4) Java实现：

//插入排序    private static int[] insertSort(int[] arr){        int len = arr.length;        if(len > 0){            for(int i = 0 ; i < len - 1 ; i++){                int curInsertNum = arr[i + 1];  //未排序序列中新的待排序（待插入）的数                int insertIndex = i;   //新的待插入的数应该插入的位置的前一位                //从已排序序列中的最后一位开始往前遍历，找到第一个比curInsertNum小的数，插入这个数后面                for(insertIndex = i ; insertIndex >= 0 ; insertIndex--){                    //要插入的数小于已排序序列中下标 insertIndex处的数，则将下标 j处的数在序列中后移一位                    if(arr[insertIndex] > curInsertNum){                        arr[insertIndex + 1] = arr[insertIndex];                    }                    //注意插入操作不能放在这里，虽然当找到要插入的数的位置时（即大于已排序序列中的某个数）需要                    //将待插入的数插入该数的后面，但是这一步放在这的话，当待插入的数小于已排序序列中的所有数时                    //（即执行到 insertIndex == 0时 arr[insertIndex]还是大于curInsertNum，那么下一步                    // 就跳出循环不执行插入操作了，因此，应该在找到要插入的数的位置时跳出循环，然后在循环外执                    // 行插入操作，这样当跳出循环是因为所有数都比待插入的数大时，插入操作也能进行                    /*else {                        arr[insertIndex + 1] = curInsertNum;                        break;                    }*/                    else {   //要插入的数大于等于已排序序列中下标insertIndex处的数                        break;                    }                }                //执行插入操作，当跳出循环时 j == -1时，说明已排序序列中的所有数都大于待插入的数，所以待插入的                //数应该插入第一个位置，即 j == 0处                arr[insertIndex + 1] = curInsertNum;            }        }        return arr;    }

(5) 复杂度分析：

空间复杂度：不需要额外空间，故空间复杂度为O(1)。

时间复杂度：

最佳情况（O(n)）：当输入序列原本就是升序序列，每一轮都只要比较一次就可以插入，不用移动元素并进行多次比较，那么只需要扫描一遍这n个数（找元素：O(n)），找位置只需要O(1)，因此，最好时间复杂度为O(n)。

最差情况：（O(n²)）：原数组为降序，第 i 个待插入记录需要比较（ i+1）次才能找到合适位置，即需要扫描一遍这n个数（找元素：O(n)），还需要比较n次（找位置：O(n)），时间复杂度为O(n²)。

平均情况：O(n²)

 

4. 归并排序

(1) 思想概述：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 

和选择排序一样，归并排序的性能不受输入数据顺序的影响，但时间复杂度比选择排序好，始终都是O(n log n），代价是需要额外的内存空间，空间复杂度为O(n)。

(2) 算法描述:

归并排序算法在字面意思上已经简要显示出了算法的核心原理，即先递归再合并。

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

重复上述过程。

整个过程类似于二叉树遍历中的后序遍历，合并操作在两次递归操作之后。

(3) 排序示例：

参考：整理的一文

(4) Java实现：

//归并排序（自顶向下归并，每次都将一个大数组对半分成两个小数组）    private static int[] mergeSort(int[] arr, int left, int right){        if(left < right){            int mid = (left + right) / 2;            mergeSort(arr, left, mid);  //对左边的子序列进行归并排序，使得左边的子序列有序            mergeSort(arr, mid + 1, right); //对右边的子序列进行归并排序，使得右边的子序列有序            merge(arr, left, mid, right);  //合并左右两个子序列        }        return arr;    }    //数组arr中 (left，mid)区间和 (mid+1，right)区间这两个子区间分别有序，merge函数将这两个区间进行合并，    //合并后数组arr的 (left，right)区间有序    private static void merge(int[] arr, int left, int mid, int right){        //int[] temp = new int[arr.length];        int[] temp = new int[right - left + 1];  //临时数组，保存子区间内排好序的元素        int leftArrIndex = left;   //控制左子区间遍历时的下标        int rightArrIndex = mid + 1;  //控制右子区间遍历时的下标        int tempIndex = 0;   //控制临时数组中填充元素时的下标        //当左右子区间都还有元素未排好序时        while (leftArrIndex <= mid && rightArrIndex <= right){            if(arr[leftArrIndex] < arr[rightArrIndex]){                temp[tempIndex] = arr[leftArrIndex];                leftArrIndex++;            }else {                temp[tempIndex] = arr[rightArrIndex];                rightArrIndex++;            }            tempIndex++;        }        //若上面循环结束的时候，是右子序列已经归并到临时数组中，左子序列还有元素，那么接下来将左子序列全部按序        //填充到临时数组的对应位置即可        while (leftArrIndex <= mid){            temp[tempIndex] = arr[leftArrIndex];            tempIndex++;            leftArrIndex++;        }        //若上面循环结束的时候，是左子序列已经归并到临时数组中，右子序列还有元素，那么接下来将右子序列全部按序        //填充到临时数组的对应位置即可        while (rightArrIndex <= right){            temp[tempIndex] = arr[rightArrIndex];            tempIndex++;            rightArrIndex++;        }        //将临时数组temp中已排好序的部分按序拷贝到原数组arr中的待排序区间的相应位置        for(int i = 0 ; i < temp.length ; i++){            //arr数组中待排序部分的起始坐标是left，所以是 arr[i + left]而不是arr[i]            arr[i + left] = temp[i];        }    }

(5) 复杂度分析：

空间复杂度：归并排序每次递归都需要用到一个辅助表，长度与待排序的表相等，即O(n)。此外，虽然递归过程需要用到栈空间，递归次数是O(logn)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O(n)。

时间复杂度：与输入数据的顺序无关，最好、最坏、平均时间复杂度均为O(n log n)。

 

5. 快速排序

(1) 思想概述：

快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行快速排序，以达到整个序列有序。快速排序算法的核心思想也是分治法。

(2) 算法描述:

快速排序算法使用分治法来把一个串分为两个子串。具体算法描述如下：

• 从序列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序序列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）对小于基准值元素的子序列和大于基准值元素的子序列进行快速排序，直到整个原序列有序。

整个过程类似于二叉树遍历中的前序遍历，分区操作在两次递归操作之前。

(3) 排序示例：

参考：Runoob.com整理的一文

(4) Java实现：

//快速排序    private static int[] quickSort(int[] arr, int left, int right){        if(left < right){            int p = partition(arr, left, right);            quickSort(arr, left, p - 1);            quickSort(arr, p + 1, right);        }        return arr;    }    //选择一个分界点，并基于分界点交换元素，使得最终分界点左侧的元素都比它小，右侧的元素都比它大，并返回分界点下标    private static int partition(int[] arr, int left, int right){        int p = arr[left];        while (left < right){            while (left < right && arr[right] >= p){                right--;            }            //上面循环结束的时候，要么是left == right，要么是arr[right]小于基准值。根据快速排序的过程，当left == right时，说明这一轮排序已经结束了，所以在进行排序过程的操作之前，都需要判断一下left < right是否成立，只有left小于right的时候，才进行比较或者交换操作。所以，下面这个交换操作之前需要判断一下left < right是否成立。            if(left < right){                arr[left++] = arr[right];            }            while (left < right && arr[left] <= p){                left++;            }            //arr[right] = arr[left];            if(left < right){                arr[right--] = arr[left];            }        }        //循环退出时，left == right，它们指向的都是基准值应该在的位置，将基准值填入并返回该下标即可        arr[left] = p;   //将基准值（即分界点）移到已排序的左右子序列的中间        return left;  //返回基准的下标    }

(5) 复杂度分析：

空间复杂度：快速排序的空间复杂度主要是递归过程造成的栈空间的使用，与归并排序不同，归并排序每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了。而快速排序每次递归都会返回一个基准值（分界点）的位置，必须使用栈，所以空间复杂度就是栈使用的空间。

最佳情况下，递归树的深度是log n,其空间复杂度是O(log n)。

最差情况下，需要进行（n-1）次递归调用，其空间复杂度为O(n)。

平均情况下，空间复杂度为O(log n)。

时间复杂度：

最佳情况：输入序列基本无序，时间复杂度为O(n log n)。

最差情况：当输入序列是正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空）。如果递归树画出来，它就是一棵斜树。此时需要执行（n-1）次递归调用，且第 i 次划分需要经过（n-i）次关键字比较才能找到第 i 个记录，也就是key的位置，因此比较次数为 n(n-1)/2，最差时间复杂度为O(n²)。

平均情况：O(n log n)。

 

6. 堆排序

(1) 思想概述：

堆排序涉及概念较多，建议系统学习一番才能理解，为了避免内容过多，本文不详细展开相关概念。对堆相关概念不熟悉的朋友可以参考整理的一文。

(2) 算法描述:

• 将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；
• 将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
• 重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

(3) 排序示例：

参考整理的一文。

(4) Java实现：

//堆排序    private static int[] heapSort(int[] arr){        int len = arr.length;        //构建大顶堆        for(int curIndex = len / 2 - 1 ; curIndex >= 0 ; curIndex--){            //构建大顶堆的过程其实就是从最后一个非叶结点开始，从下至上，从右往左依次调整            adjustHeap(arr, curIndex , len);        }        //每次将大顶堆的第一个结点和最后一个结点值进行交换，这样最后一个结点存放的就是当前未排序序列中的最大值，        //交换后堆的结构发生了改变，所以需要重新调整，调整完后继续交换第一个结点和最后一个结点，一直进行上述过程，        //直到待排序的序列长度为0        for(int lastIndex = len - 1 ; lastIndex > 0 ; lastIndex--){            swap(arr, 0, lastIndex);            len--;    //每经过依次交换，就将当前最大值排到最后，待排序序列的长度就应该减 1            //adjustHeap(arr, len / 2 - 1, len);            adjustHeap(arr, 0, len);   //注意这里的第二个参数和构建大顶堆时不一样        }        return arr;    }    //调整堆中的结点值使堆符合大顶堆的特征，curIndex为当前待调整的非叶结点的索引，length为待排序的序列长度    private static void adjustHeap(int[] arr, int curIndex, int length){        int largestIndex = curIndex;//假设当前待调整的非叶结点就是三个结点（还有两个是它的子结点）中的最大值        int leftIndex = 2 * curIndex + 1;  //当前非叶结点左子结点的索引        int rightIndex = 2 * curIndex + 2; //当前非叶结点右子结点的索引        //若左子结点存在且值大于其父结点的值，则更新当前最大值的索引为左子结点的索引        if(leftIndex < length && arr[leftIndex] > arr[largestIndex]){            largestIndex = leftIndex;        }        //若右子结点存在且值大于其父结点的值，则更新当前最大值的索引为右子结点的索引        if(rightIndex < length && arr[rightIndex] > arr[largestIndex]){            largestIndex = rightIndex;        }        //经过上面两个判断，若最大值索引不是当前待调整结点的索引，说明当前待调整结点的左右子结点中有大于它的结点，        //那么就需要交换待调整结点和大于它的子结点的值        if(largestIndex != curIndex){            swap(arr, largestIndex, curIndex);            //互换之后，原本子结点位置的值发生了变化，若该子结点也有自己的子结点，那么可能也需要调整，所以需要            //将该结点作为待调整结点调用调整函数adjustHeap进行调整            adjustHeap(arr, largestIndex, length);        }    }

(5) 复杂度分析：

空间复杂度：不需要额外空间，故空间复杂度为O(1)。

时间复杂度：

堆排序过程每构建或调整一次堆，就得到第  i 大的数，每次调整堆的时间复杂度是O(log n)；若要将整个序列排成有序的序列，需要（n-1）次构建或调整堆，时间复杂度为O(n)，所以总的时间复杂度为O(n log n)。并且调整过程与序列是否有序无关，因此最好、最坏和平均时间复杂度均为O(n log n)。

 

五、总结以及各种排序算法的适用情况

1、数据规模较小

• 待排序列基本有序的情况下，可以选择插入排序；
• 对稳定性不作要求宜用选择排序，对稳定性有要求宜用插入排序或冒泡排序。

2、数据规模不是很大

• 完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
• 序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序。

3、数据规模很大

• 对稳定性有求，则可考虑归并排序。
• 对稳定性没要求，宜用堆排序。

4、序列初始基本有序（正序）

• 宜用插入排序或冒泡排序，不适合用快速排序。

5、总体无序，但是各子项相对有序的数列

• 归并排序

转载地址：https://blog.csdn.net/m0_37415978/article/details/115015165 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！