索引

交换排序: 冒泡, 快排
插入排序: 简单插入排序, 希尔排序
选择排序: 简单选择排序, 堆排序
归并排序: 归并排序
基数排序:

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

交换排序

冒泡排序(Bubble Sort)

使用冒泡排序为一列数字进行排序的过程

最原始的交换类排序方式。遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就交换位置。时间复杂度平均情况O(n^2)，最坏也是O(n^2)，最好时间复杂度是O(n)，解释一下最好时间复杂度：改进的冒泡算法增加一个标志位（是否发生了swap）,如果这次循环完毕检查标志仍是false，说明这次已经是排好序的，直接return。
当数组是已经排好序的，这种冒泡的时间复杂度是O(n)

i∈[0,N-1)       //循环N-1遍
  j∈[0,N-1-i)   //每遍循环要处理的无序部分
    swap(j,j+1) //两两排序（升序/降序）

冒泡示意图

优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了，结束。
优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

快排(Quick Sort)

快速排序

快速排序（QuickSort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要 (nlog n)次比较。在最坏状况下则需要 n^2次比较。

从数列中挑出一个元素，称为”基准”（pivot），
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

举例：对5，3，8，6，4这个无序序列进行快速排序(小→大)，右指针找比基准数小的，左指针找比基准数大的，然后交换位置。

用数组第一个元素最为基准值(pivotKey)
5，3，8，6，4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。
5，3，8，6，4 首先设置i，j两个指针分别指向左右两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i，j位置。
5，3，4，6，8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
4，3，5，6，8 一次划分后达到了左边比5小，右边比5大的目的。
以5 为分界点, 左序列 4, 3 和右序列 6, 8 递归的进行排序

上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

// 快速排序, 从小到大
public static void quickSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int pivotPos = partition(arr, left, right);
    quickSort(arr, left, pivotPos-1);
    quickSort(arr, pivotPos+1, right);
}

public static int partition(int[] arr, int left, int right) {
    int pivotKey = arr[left];
    int pivotPointer = left;

    while(left < right) {
        while(left < right && arr[right] >= pivotKey)
            right --;
        while(left < right && arr[left] <= pivotKey)
            left ++;
        swap(arr, left, right); //把大的交换到右边，把小的交换到左边。
    }
    swap(arr, pivotPointer, left); //最后把pivot交换到中间
    return left;
}

时间复杂度平均O(n log n)，最坏O(n^2)。因为快排的实现是递归调用的，而且每次函数调用中只使用了常数的空间，因此空间复杂度等于递归深度O(log n)。
分析过程参考快速排序 “正规分析”。

插入排序

插入排序(Insertion Sort)

insertion_sort

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

public static void insertSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    for(int i=1; i<arr.length; i++) { //假设第一个数位置时正确的；要往后移，必须要假设第一个。
        int j = i;
        int target = arr[i]; //待插入的
        //后移
        while(j > 0 && target < arr[j-1]) {
            arr[j] = arr[j-1];
            j --;
        }
        //插入
        arr[j] = target;
    }

}

时间复杂度最坏和平均坏都是O(n^2), 如果基本是已经排序的数列, 最好是O(n)

希尔排序(Shell Sort)

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。与插入排序一样，最好的复杂度可以达到O(n)。
原始的插入算法实现在最坏的情况下需要进行O(n^2)的比较和交换。
步长的选择直接决定了希尔排序的复杂度，如果用n/2^i作为步长，希尔排序可以使得最坏情况提升至O(n*log2n)。这比最好的比较算法的O(n*logn)要差一些。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）

public static void shellInsert(int[] arr, int d) {
    for(int i=d; i<arr.length; i++) {
        int j = i - d;
        int temp = arr[i];    //记录要插入的数据
        while (j>=0 && arr[j]>temp) {  //从后向前，找到比其小的数的位置
            arr[j+d] = arr[j];    //向后挪动
            j -= d;
        }

        if (j != i - d)    //存在比其小的数
            arr[j+d] = temp;

    }
}

public static void shellSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    int d = arr.length / 2;
    while(d >= 1) {
        shellInsert(arr, d);
        d /= 2;
    }
}

上面源码的步长的选择是从n/2开始，每次再减半，直至为0。步长的选择直接决定了希尔排序的复杂度。在维基百科)上有对于步长串行的详细介绍。

从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。
希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。

希尔排序

选择排序

选择排序(Selection Sort)

选择排序的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。
如果移动元素的代价非常大，使用选择排序可以保证最少次数的数据移动。
选择排序的时间复杂度为O(n^2)

public static void selectSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    int minIndex = 0;
    for(int i=0; i<arr.length-1; i++) { //只需要比较n-1次
        minIndex = i;
        for(int j=i+1; j<arr.length; j++) { //从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值，交换之。
            swap(arr, i, minIndex);
        }
    }

}

堆排序(Heap Sort)

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
首先，实现堆排序需要解决两个问题：

如何由一个无序序列键成一个堆？
如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。
第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。举例：
49,38,65,97,76,13,27,49 序列的堆排序建初始堆和调整的过程如下：

输出堆顶元素并调整建新堆的过程：

建初始堆过程：

/**
     * 堆筛选，除了start之外，start~end均满足大顶堆的定义。
     * 调整之后start~end称为一个大顶堆。
     * @param arr 待调整数组
     * @param start 起始指针
     * @param end 结束指针
     */
    public static void heapAdjust(int[] arr, int start, int end) {
        int temp = arr[start];

        for(int i=2*start+1; i<=end; i*=2) {
            //左右孩子的节点分别为2*i+1,2*i+2

            //选择出左右孩子较小的下标
            if(i < end && arr[i] < arr[i+1]) {
                i ++;
            }
            if(temp >= arr[i]) {
                break; //已经为大顶堆，=保持稳定性。
            }
            arr[start] = arr[i]; //将子节点上移
            start = i; //下一轮筛选
        }

        arr[start] = temp; //插入正确的位置
    }


    public static void heapSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;

        //建立大顶堆
        for(int i=arr.length/2; i>=0; i--) {
            heapAdjust(arr, i, arr.length-1);
        }

        for(int i=arr.length-1; i>=0; i--) {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i-1);
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

归并排序(Merge Sort)

一个归并排序的例子：对一个随机点的链表进行排序

如何合并两个有序数组？

首先申请一个空间大小等于两个数组大小的和；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针移动到下一个元素；
重复步骤直到某一指针达到序列尾；

归并排序就是用递归的方式，把待排序数组递归分解为left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

归并示意图

public static void mergeSort(int[] arr) {
    mSort(arr, 0, arr.length-1);
}

/**
 * 递归分治
 * @param arr 待排数组
 * @param left 左指针
 * @param right 右指针
 */
public static void mSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int mid = (left + right) / 2;

    mSort(arr, left, mid); //递归排序左边
    mSort(arr, mid+1, right); //递归排序右边
    merge(arr, left, mid, right); //合并
}

/**
 * 合并两个有序数组
 * @param arr 待合并数组
 * @param left 左指针
 * @param mid 中间指针
 * @param right 右指针
 */
public static void merge(int[] arr, int left, int mid, int right) {
    //[left, mid] [mid+1, right]
    int[] temp = new int[right - left + 1]; //中间数组

    int i = left;
    int j = mid + 1;
    int k = 0;
    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
        }
    }
    while(i <= mid) {
        temp[k++] = arr[i++];
    }

    while(j <= right) {
        temp[k++] = arr[j++];
    }

    for(int p=0; p<temp.length; p++) {
        arr[left + p] = temp[p];
    }
}

平均时间复杂度O(nlogn)，最好时间复杂度O(n)，同一时刻需要一个大小为n的额外空间, 空间复杂度O(n)

归并排序及其空间复杂度的思考 - CSDN博客

计数排序(Counting Sort)

用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。复杂度O(n)

桶排序(Bucket Sort)

先了解”桶”(Bucket)的概念, 有一个数组, 数组的每个元素都是一个线性链表, 那么这个数组被称为桶数组，数组里每个元素被称为”桶”。

假设有一组长度为N的待排关键字序列K[N]。申请一个M大小的数组B[M]作为“桶数组”。然后基于某种映射函数，将待排序列K[k]映射到桶B[i]中，
K[N]的规模是大于B[M]的，所以多个K中的元素可能放入B的一个桶位，放入时K的元素需要排序。
接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。
元素K[k]需要映射到桶数组B[i]的位置上，其中i=f(K[k])，并且如果有K[i] < K[j]，那么f(K[i]) < f[K[j]]，也就是说B[i]中的最小数据都要大于B[i-1]中最大数据。很显然，映射函数的选择非常重要。

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。　

复杂度分析:

循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni为第i个桶的数据量。

很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：

映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。
尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

O(N) + O(M*(N/M)*log(N/M)) = O(N + N*(logN-logM)) = O(N + N*logN - N*logM)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

基数排序(Radix Sort)

基数排序是非比较排序算法,算法的时间复杂度是O(n)。
基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。主要思路是，将所有待比较数值(注意,必须是正整数)统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始, 依次进行一次稳定排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

比如这样一个数列排序: 342 ，58， 576， 356, 以下描述演示了具体的排序过程

第一次排序(个位):

第二次排序(十位):

第三次排序(百位):

结果: 58 342 356 576

外部排序

http://data.biancheng.net/view/76.html

排序算法的比较

排序方法	平均时间	最坏情况	额外存储
插入排序	n^2	n^2	1
冒泡排序	n^2	n^2	1
快速排序	nlogn	n^2	logn
归并排序	nlogn	nlogn	n
堆排序	nlogn	nlogn	1
希尔(n/2步长)	nlogn	nlogn	1

从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择

排序算法的稳定性

稳定排序能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。
基数排序就是这样，先按低位排序，逐次按高位排序，那么，低位相同的数据元素其先后位置顺序即使在高位也相同时是不会改变的