排序算法总结

排序算法有非常多种。有些排序算法的时间复杂度是O(n^2)，有一些是O(nlogn)，有些是O(n)；有些排序算法基于数据之间的比较而有些不基于。有些排序算法的空间复杂度是O(1)，有些是O(n)，有些排序算法是稳定的，而有些不是稳定的排序算法。本文将归纳一些经典的排序算法和其各自的特点。

本文要介绍的几种排序算法归纳在下图所示：

排序算法的执行效率

对于排序算法，我们可以从以下角度来分析其执行效率

Time Complexity

对于要排序的数据，有些数据本身已经接近有序，有些则是完全无序，对于有序程度不同的数据，对齐排序的时间执行效率是不同的，所以分析排序算法的时间复杂度我们需要分析最好情况、最坏情况、平均情况的时间复杂度。

而对于某些数据量不大的数据，n本身的值不大，所以有的时候我们还需要考虑到时间复杂度的系数、常数、低阶项。对于某些数据，比如n = 1000，可能会出现O(n^2)的排序算法比O(nlogn)的排序算法运行时间更短的情况。

Space Complexity

针对排序算法，还另外引入了一个叫原地排序(Sorted in place)的概念，原地排序就是指空间复杂度为O(1)的排序算法。要实现sorted in place的算法，一般要依赖两个指针，然后对数据进行交换，这样可以不借助其他数据结构。

排序算法的稳定性

针对排序算法，除了分析它的时间复杂度和空间复杂度，我们还需要考虑这个算法的稳定性。排序算法的稳定性是指如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间的原有的先后顺序不变。

为什么要考虑排序算法的稳定性？

如果要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，我们需要使用到稳定性的算法。例如：要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。

一些经典的排序算法

冒泡排序

冒泡排序的思想很简单，它基于相邻元素之间的两两比较。第一趟比较过程，将所有相邻元素比较一遍，把最小（大）的数放在最前面（最后面一样）。第二趟比较过程，把第二小的数放在第一小的数后面…依次类推。假设有k个对象要比较，就要比较k趟。

直接上代码:

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        boolean flag = false;
        for (int j = nums.length - 1; j >= i + 1; j--) {
            if (nums[j] < nums[j-1]) {
                int temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = temp;
                flag = true;
            }
            if (!flag) break;
        }
    }
}

这个实现是每次把最小的数、第二小的数…一趟趟地交换到前面。写的时候加了一个优化的步骤：当一趟下来，没有任何数据交换的时候说明已经排好序，可以直接退出循环。

下面分析冒泡排序的执行效率：

稳定性：冒泡排序是稳定算法。因为前后两个元素相等的时候，我们不会进行交换，保证相同元素排序前后的相对位置相同。
时间复杂度：最好情况是O(n)，此时已经排好序，只要比较一趟即可。最坏的情况是O(n)，此时是倒序排列，要 n 次冒泡操作。平均来说，冒泡排序的时间复杂度是O(n^2).
空间复杂度：O(1)

插入排序

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。

时间复杂度 O(n^2)，空间复杂度是O(1)，是稳定的算法。

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

时间复杂度是 O(n^2) ，空间复杂度是 O(1) ，不稳定。

快速排序

快排的思想：在一个数组中随便选定一个数target（比如固定选取第一个数，最后一个数，或者中间的数），将比target小的数分为一部分，比target大的数分为一部分。（注意：这个过程中target的位置并不确定会在哪里。）

下面是一个快速排序的实现：

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortArray(int[] A) {
        // write your code here
        quicksort(A, 0, A.length - 1);
    }
    
    public void quicksort(int[] nums, int start, int end) {
        if (start >= end) return;
        
        int left = start;
        int right = end;
        int pivot = nums[(left + right) / 2];
        
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
        
        quicksort(nums, start, right);
        quicksort(nums, left, end);
    }
}

说明：

看到这个实现的时候，我第一反应是, 为什么nums[left] < pivot和nums[right] > pivot 这两个判断不加等号？

其实，这个是为了处理一种极端情况，也就是nums中每个数都相同的情况。

举例说明，当nums = [1,1,1,1,1,1,1], 把这个情况带入上面的代码，此时有pivot = 1，如果有等号，比如nums[left] <= pivot，此时在循环内left每次加1，看上去没啥问题，但是如果nums很大的时候，这样做就会比较慢，而如果采用nums[left] < pivot，碰到这种情况，每次循环是left++和right--，在这种情况下，不加等号，循环可以快点结束。

归并排序

归并排序的思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并的空间复杂度是O(n)，但归并排序的时间复杂度不论什么情况都是O(nlogn)，而快排时间复杂度在极端情况下时间复杂度可能是O(n^2)

归并排序和快排思想上的差别：

归并排序，是先递归调用，再进行合并，合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上？就是先解决子问题，再解决父问题。
快速排序，是先分区，在递归调用，分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下？就是先解决父问题，再解决子问题。

一个归并排序的实现：

public class Solution {

    private static int[] aux;

    public static void sortIntegers2(int[] a) {
        aux = new int[a.length];
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    
    public static void merge(int[] a, int low, int mid, int high) {
        int i = low, j = mid + 1;
        
        for (int k = low; k <= high; k++) {
            aux[k] = a[k];
        }
        
        for (int k = low; k <= high; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > high) {
                a[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

}
``` 

### 堆排序

堆排序是原地排序算法，时间复杂度为O(nlogn)，但在实际的软件开发中，不如快速排序的性能，原因是堆本身是一种树状结构，维持这个结构也会额外消耗一些性能。

堆排序的过程大致分解成两个大的步骤，建堆和排序。

建堆时间复杂度：O(n)，排序时间复杂度：O(nlogn)。

从后往前的堆化：

```java
private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

排序过程时间复杂度是O(nlogn)。

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再分别排序。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间O(n)。但是如果所有的数都被分到了一个桶中，相当于对该桶的所有数又要进行排序。又回到了前面几种排序算法。而且桶排序耗空间。原因在于如果我们知道数据的范围，我们准备桶的数量要根据（MAX-MIN）/ 单个桶包含数据范围来判断桶的数量。

Arrays.sort用到的排序算法

jdk1.8中的Arrays.sort排序，在元素小于47的时候用插入排序，大于47小于286用双轴快排，大于286用timsort归并排序，并在timesort中记录数据的连续的有序段的的位置，若有序段太多，也就是说数据近乎乱序，则用双轴快排，当然快排的递归调用的过程中，若排序的子数组数据数量小，用插入排序。

目录