排序算法总结

算法改变人生 2019-06-27

内部排序

以下为基于比较的排序。

一、插入排序

直接插入排序

  • 基本思想：

将元素插入到已经排好序的序列中。第一个元素已经是有序序列，然后比较外围的元素和序列的最后一个元素，判断是否需要插入，如果小，则插入。

  • 时间复杂度：最优 O(n) 最差 O(n^2)
  • 是否稳定：是
public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) 
            for (int j = i - 1; j >= 0; j--)
                if (arr[j + 1] < arr[j])
                    swap(arr, j + 1, j);
    }

改进后的插入排序

比如，用二分查找优化插入排序，因为是要插入到已经排好序的序列当中，所以在查找插入位置这个地方可以用二分查找来优化。

public int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (key < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }

    public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++)
            // determine whether to insert
            if (arr[i] < arr[i - 1]) {
                // record the element to insert
                int key = arr[i];
                // find insert index
                int indexInsert = binarySearch(arr, 0, i - 1, arr[i]);
                // move elements
                for (int j = i - 1; j >= indexInsert; j--)
                    arr[j + 1] = arr[j];
                // insert the key
                arr[indexInsert] = key;
            }
    }

二、选择排序

1. 简单选择排序

  • 基本思想：

选出后面最小的元素和前面的交换

  • 时间复杂度： 最优 O(n^2) 最差 O(n^2)
  • 是否稳定：否
public void selectSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int minIndex = i;
            // find the min index
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            if (minIndex != i)
                swap(arr, i, minIndex);
        }
    }

改进后的选择排序

之前的选择排序是一趟只找到最小的，如果一趟可以把最大最小都找出来，就可以将循环的次数减半。

不过在交换时需要注意一种情况，就是第一个元素就已经是最大元素的情况，因为前面已经交换过 i 和 min，所以再交换时就是交换的 n - i - 1 和 min，而不是 max。

public void selectSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n / 2; i++) {
            int min = i;
            int max = i;
            for (int j = i + 1; j < n - i; j++) {
                // find the min element
                if (arr[j] < arr[min]) {
                    min = j;
                    continue;
                }
                // find the max element
                if (arr[j] > arr[max])
                    max = j;
            }
            swap(arr, i, min);

            if (max != i)
                swap(arr, n - i - 1, max);
            else // the first element is the max element
                swap(arr, n - i - 1, min);
        }
    }

2. 堆排序

  • 基本思想：

堆排序也是一种直接选择排序，因为它也是将排好序的大根堆 or 小根堆的顶部元素逐个和尾部元素交换，也是一种选择。

  • 时间复杂度： 最优 O(nlgn) 最差 O(nlgn) 是一个很优秀的排序算法
  • 是否稳定：否
public void adjustHeap(int[] arr, int i, int len) {

        int parent = arr[i];

        // start from left child
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            // find max child (left or right)
            if (k + 1 < len && arr[k + 1] > arr[k])
                k++;
            // compare the parent and its child, but don't swap
            if (arr[k] > arr[i]) {
                arr[i] = arr[k];
                i = k;
            } else
                break;
        }

        // insert the original parent on index i
        arr[i] = parent;
    }

    public void heapSort(int[] arr) {

        int len = arr.length;

        // adjust heap from the last none-leaf node
        // from bottom to up; from right to left
        for (int i = len / 2 - 1; i >= 0; i--)
            adjustHeap(arr, i, len);

        // swap the top element and the last element
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, i, 0);
            adjustHeap(arr, 0, i);
        }
    }

三、归并排序

  • 基本思想：分治。将两个有序序列合并成一个有序序列，递归进行。需要辅助数组。
  • 时间复杂度： 最优 O(nlgn) 最差 O(nlgn)
  • 空间复杂度

O(n)

  • 是否稳定：是
/* create an array in advance to avoid creating arrays frequently */
    private void sort(int[] arr) {
        int n = arr.length;
        int[] temp_arr = new int[n];
        mergeSort(arr, 0, n - 1, temp_arr);
    }

    public void mergeSort(int[] arr, int left, int right, int[] temp_arr) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp_arr);
            mergeSort(arr, mid + 1, right, temp_arr);
            merge(arr, left, mid, right, temp_arr);
        }
    }

    public void merge(int[] arr, int left, int mid, int right, int[] temp_arr) {

        int i = left;
        int j = mid + 1;
        int t = 0;

        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp_arr[t++] = arr[i];
                i++;
            } else {
                temp_arr[t++] = arr[j];
                j++;
            }
        }

        // insert the remaining elements
        while (i <= mid)
            temp_arr[t++] = arr[i++];
        while (j <= right)
            temp_arr[t++] = arr[j++];

        t = 0;
        // copy elements into array
        while (left <= right)
            arr[left++] = temp_arr[t++];
    }

四、交换排序

1. 冒泡排序

  • 基本思想：

总共有 n 个元素，就比较 n - 1 趟，每一趟比较都会将相邻元素进行比较，然后将较大的元素向后放，就像大数沉底，小数像上冒一样。冒泡排序的交换次数等于原始序列的逆序数。

  • 时间复杂度： 最优 O(n) 最差也是平均 O(n^2)
  • 是否稳定：是
public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);
            }
        }
    }

改进后的冒泡排序一

交换过后，会有部分元素是已经排好序了，这一部分再进行比较是没有意义的，可以从这个地方入手改进冒泡排序。

用一个标志位记录最后一次进行交换的位置，这个位置后面的元素是没有进行交换的，说明是已经排好序的，所以不需要再比较。

public void bubbleSort(int[] arr) {

        int n = arr.length;
        int i = n - 1;
        int pos = 0;

        while (i > 0) {
            for (int j = 0; j < i; j++) {
                pos = 0;
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    pos = j;
                }
            }
            i = pos;
        }
    }

改进后的冒泡排序二

双向冒泡（正反两个方向同时排序），使排序次数几乎减少一半

public void bubbleSort(int[] arr) {

        int n = arr.length;
        int left = 0;
        int right = n - 1;

        while (left < right) {
            for (int i = left; i < right; i++) {
                if (arr[i] > arr[i + 1])
                    swap(arr, i, i + 1);
            }
            right--;

            for (int i = right; i > left; i--) {
                if (arr[i] < arr[i - 1])
                    swap(arr, i, i - 1);
            }
            left++;
        }
    }

2. 快速排序

  • 基本思想：

根据选择的基准元素进行划分，然后两边都进行排序，再递归进行。需要注意的是，遍历需要从选择的基准元素的反方向开始。

  • 时间复杂度： 最优也是平均 O(nlgn) 最差 O(n^2) 即每次选的基准元素都是最大（小）值
  • 是否稳定：否
public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotLoc = partition(arr, low, high);
            quickSort(arr, low, pivotLoc - 1);
            quickSort(arr, pivotLoc + 1, high);
        }
    }

    public int partition(int[] arr, int low, int high) {
        int pivot = arr[low];

        while (low < high) {
            while (low < high && arr[high] >= pivot)
                high--;
            swap(arr, low, high);

            while (low < high && arr[low] <= pivot)
                low++;
            swap(arr, low, high);
        }

        return low;
    }

外部排序

非基于比较的排序，时间复杂度可以达到 O(n)，其实是用空间换时间。

下面列举的都是线性时间排序法

1. 计数排序（Counting Sort）

  • 基本思想：

利用数组下标来排序。但只适合有限数值的数字，序列的数字最大值 k 如果太大，那么开的辅助数组 C[] 就会很大，占用太多空间。
这种思路经常被用到。

  • 时间复杂度： 最优也是平均 O(n + k) 最差 O(n^2) 即每次选的基准元素都是最大（小）值
  • 是否稳定：是
public int[] countingSort(int[] A, int k) {
        int n = A.length;
        int[] C = new int[k + 1];

        // counting the number of times each element appears in A
        for (int i = 0; i < n; i++) {
            C[A[i]]++;
        }

        // counting elements less than or equal to C[i]
        for (int i = 1; i <= k; i++) {
            C[i] = C[i] + C[i - 1];
        }

        // insert into result array
        int[] B = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            B[C[A[i]] - 1] = A[i];
            C[A[i]]--;
        }

        return B;
    }

2. 桶排序（Bucket Sort）

  • 基本思想：

把数组中数据放到有限个桶中，在每个桶中分别进行排序（可以采用任意排序方法）。

模拟画图 ≡ω≡

input:[12,22,2,13,23,3]

     |     |     |     |     |     |
     | 2,3 |     |12,13|     |22,23|
     |_____|     |_____|     |_____|
     bucket1     bucket2     bucket3
      (1-10)     (11-20)     (21-30)

      output:[2,3,12,13,22,23]
  • 时间复杂度： 最优近似 O(n) 最差 O(n^2) 即每次选的基准元素都是最大（小）值
  • 是否稳定：是
public void bucketSort(int[] arr){

        int n = arr.length;

        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num < min)
                min = num;
            if (num > max)
                max = num;
        }

        // create bucket
        int bucketNum = max / 10 - min / 10 + 1;
        List bucketList = new ArrayList<List<Integer>>();
        for (int i = 1; i <= bucketNum; i++) {
            bucketList.add(new ArrayList<Integer>());
        }

        // insert into bucket
        for (int i = 0; i < n; i++) {
            int index = (arr[i] - min) / 10;
            ((ArrayList<Integer>)bucketList.get(index)).add(arr[i]);
        }

        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>)bucketList.get(i);
            bucketInsertSort(bucket);
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public void bucketInsertSort(List<Integer> bucket) {
        for (int i = 0; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

3. 基数排序（Radix Sort）

  • 基本思想：

前面的计数和桶排序都是只能排一个关键字，而基数排序可以排多个关键字。

基数排序分为两种：假设有二元组 (a, b)，以 a 为首要关键字，b 为次要关键字排序

  1. MSD(Most Siginificant Digit) 先排 a，后排 b
  2. LSD(Least Siginificant Digit) 先排 b，后排 a

基数排序需要使用稳定的排序算法，一般用计数或者桶排序。

e.g. 采用 LSD

input: [170, 45, 75, 90, 802, 24, 2, 66]

1. 从最后一个关键字开始排：  
   170, 45, 75, 90, 802, 24, 2, 66
     0   5   5   0    2   4  2   6

   排序后（注意保持原来的相对顺序，802 仍然在 2 前面）：
   170, 90, 802, 2, 24, 45, 75, 66

2. 从次要关键字开始排
   170, 90, 802, 2, 24, 45, 75, 66
    7   9    0      2   4   7   6

   排序后（170 仍然在 75 前面）：
   802, 2, 24, 45, 66, 170, 75, 90

3. 从首要关键字开始排：
   802, 2, 24, 45, 66, 170, 75, 90
   8                   1

   排序后：
   2, 24, 45, 66, 75, 90, 170, 802

output: [2, 24, 45, 66, 75, 90, 170, 802]
  • 时间复杂度：

平均 O(d * (r + n))

d:digit 数字位数 r:radix 基数 n:number 关键字个数

  • 空间复杂度：

O(r + n)

  • 是否稳定：是
public void radixSort(int[] arr, int n) {

        // find max element
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        for (int k = 1; max / k > 0; k *= 10) {
            countingSort(arr, n, k);
        }
    }

    public void countingSort(int[] arr, int n, int k) {

        // max number is 9
        int C[] = new int[10];

        // counting occurrences
        for (int i = 0; i < n; i++) {
            C[(arr[i] / k) % 10]++;
        }

        // counting elements less than or equal to C[i]
        for (int i = 1; i < 10; i++) {
            C[i] = C[i] + C[i - 1];
        }

        // insert into result array
        int[] B = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            B[C[(arr[i] / k) % 10] - 1] = arr[i];
            C[(arr[i] / k) % 10]--;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = B[i];
        }

    }

总结

  • 关于稳定性：

    • 稳定的排序算法：冒泡、插入、归并、计数、桶和基数排序
    • 不稳定的排序算法: 选择、快速、希尔和堆排序

  • 排序算法的选择：

    • 如果数据有序或基本有序，冒泡和插入的时间复杂度可以降到 O(n)，而快排则相反。
    • 如果数据很大，需要考虑使用 O(nlgn) 的排序方法，如快排、归并排序、堆排。
    • 如果对空间限制不大，可以使用基数排序等方法降低时间复杂度，这些线性时间排序法是利用了数据的特性达到最佳的效果。

参考资料：

算法改变人生

算法改变人生

相关推荐

排序算法总结

int[] p = partition;//等于区域的左边界和右边界

troysps / 0评论 2020-06-05

【算法】排序问题总结

每次从待排序的数字中选择一个数字（基准），将其插入到数组合适的位置中。左边的数都比它小，右边都比它大。在对左右两边的元素执行相同的操作，直到整个数组有序。int x = a[ >> 1], i = l - 1, j = r + 1;int i

Oudasheng / 0评论 2020-05-29

常用排序算法总结（基于算法 第四版）

，其中每个元素有个主键，将主键按照某种方式排列。在java中元素通常都是对象，对主键描述往往通过comparable接口。即先找出最小元素调整位置，往复。private static boolean isSorted {//检测是否有序。public st

shawsun / 0评论 2020-01-12

算法之排序算法总结

这样比较一趟，可以把最大的数放在末尾。依次循环，直到排序完成。算法思想: 分解：1.将一个数组分成两个数组。

清溪算法 / 0评论 2019-12-06

前端的排序算法总结

典型的排序方法，命名来自鱼呼吸时吹出的气泡，上层的气泡总是最大的。思路：两层循环，内层循环对比相邻两个数据，假设j > j + 1则交换元素位置。外层循环为长度限制，在内层第一次循环完成后减少长度1. 加一个标志位flag，如果没有进行交换，将标志位

YUAN / 0评论 2019-11-17

三、排序算法总结（C++版本）

　　对于各种排序算法也算是有了一定的了解，所以这里做一个总结。这是比较经典的排序算法，主要是通过内外两层的循环比较，使得乱序变为顺序。cout << "the number is " << L[j] <&l

lixiaotao / 0评论 2019-11-15

各种排序算法总结

排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。今天，来总结下各种排序算法。冒泡排序冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间

风和日丽 / 0评论 2019-11-03

八大排序算法总结

先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。

HeavyIndustry / 0评论 2014-11-25

八大排序算法总结

先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。

风吹夏天 / 0评论 2014-04-07

八大排序算法总结

先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。

WalkMoreSlowly / 0评论 2012-10-25

排序算法总结

冒泡排序是一种简单的排序方法，算法如下：1.首先将所有待排序的数字放入工作列表中。用C语言实现如下：

rioalian / 0评论 2017-07-13

常用排序算法总结

排序定义排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。输入：n个数：a1,a2,a3,…,an输出：n个数的排列:a1’,a2’,a3’,…,an’，使得a1’<=a2’<=a3’<=…关于时

代码之神 / 0评论 2019-06-27

部分排序算法总结

关于排序通常所说的排序是指内部排序，即在内存里进行排序。相对应的有外部排序，当待排序数据比较多时，排序过程需要使用闪存。排序算法大体可分为两种：一种是比较排序，时间复杂度O ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序

代码之神 / 0评论 2019-06-25

Java排序算法总结（八）：基数排序

基数排序则是属于“分配式排序”，基数排序法又称“桶子法”或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O ，其中r为所采取的基数，而m为堆数，在某些时

韦一笑 / 0评论 2011-04-20

Java排序算法总结（七）：快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序

hang0 / 0评论 2011-04-20

Java排序算法总结（六）：堆排序

堆积排序是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O， 最坏时间复杂度为O，堆排序的堆序的平均性能较接近于最坏性能。堆排序利用了大根堆堆顶记录的关键字最大(或最小)这

WindChaser / 0评论 2011-04-20

Java排序算法总结（五）：归并排序

归并排序是将两个有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序

hugebawu / 0评论 2011-04-20

Java排序算法总结（四）：希尔排序

希尔排序 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，O的额外空间，时间复杂度为O。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。

RememberMePlease / 0评论 2011-04-20

Java排序算法总结（三）：冒泡排序

冒泡排序是计算机的一种排序方法，它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O，但是有两个优点：。冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大则交换两数。

MrA / 0评论 2011-04-20

Java排序算法总结（二）：选择排序

选择排序的基本操作就是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。算法不稳定，O的额外的空间，比较的时间复杂度为O(n^2)，交换的时间复杂度为O，并不是自适应的。在大多数情况下都不推

韦一笑 / 0评论 2011-04-20

Java排序算法总结（一）：插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。比较和交换的时间复杂度为O(n^2)，算法自适应，对于数据已基本有序的情况，时间复杂度为O，算法稳定，开销很低。算法适合于数据已基本有序或者数据量小的情况。

WindChaser / 0评论 2011-04-20

各种排序算法总结

排序 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。注意，选择排序并不是稳定的排序。25 }4、希尔排序　　希尔排序是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳

kdxhspp / 0评论 2016-04-03

排序算法总结

qizongshuai / 0评论 2014-11-17

python 排序算法总结及实例详解

归并排序也称合并排序，是分治法的典型应用。分治思想是将每个问题分解成个个小问题，将每个小问题解决，然后合并。然后将这些有序的子元素进行合并。合并的过程就是 对 两个已经排好序的子序列，先选取两个子序列中最小的元素进行比较，选取两个元素中最小的那个子序列并将

小菜鸟的代码世界 / 0评论 2019-04-25

排序算法总结之堆排序

下面的堆排序算法将数组中的元素从小到大排序，用大顶堆来实现。现给定了一维数组，需要将数组中的元素使用堆排序。堆排序具体的细节实现有两种方式：一种方式是将堆顶元素删除后，放到一个辅助数组中，然后进行堆调整使之成为一个新。public class HeapSo

danwenxuan / 0评论 2016-05-27

排序算法总结之归并排序

归并排序是一个典型的基于分治的递归算法。它不断地将原数组分成大小相等的两个子数组，最终当划分的子数组大小为1时 ，将划分的有序子数组合并成一个更大的有序数组。从公式中可以看出：将规模为 N 的原问题分解成两个规模 N/2 的两个子问题；并且，合并这两个子问

qizongshuai / 0评论 2016-05-27

排序算法总结之快速排序

快速排序与归并排序一样，也是基于分治的递归算法，体现在：在每一趟快速排序中，需要选出枢轴元素，然后将比枢轴元素大的数组元素放在枢轴元素的右边，比枢轴元素小的数组元素都放在枢轴元素的左边。然后，再对分别对 枢轴元素左边 和 枢轴元素右边的元素进行快速排序。③

hiKirin / 0评论 2016-05-27

JavaScript实现获取两个排序数组的中位数算法示例

本文实例讲述了JavaScript实现获取两个排序数组的中位数算法。分享给大家供大家参考，具体如下：。给定两个大小为 m 和 n 的有序数组nums1和nums2。要求算法的时间复杂度为O 。你可以假设nums1和nums2不同时为空。希望本文所述对大家J

fasterjie / 0评论 2019-02-26

三种非比较排序算法总结

同样是比较算法排序文章，一篇给过一篇不给过，安科网团队怎么评判的？？？之前一篇文章常用的比较算法排序总结介绍了几种常用的比较排序算法，下面介绍的是几种非比较排序算法，分别是：计数排序、基数排序以及桶排序。非比较排序算法内部引用的都是计数排序，当然你也可以将

ResysChina / 0评论 2018-04-12

排序算法总结

性能时间复杂度为$O(N^2)$，空间复杂度为$O$。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。插入排

BitTigerio / 0评论 2017-12-13