排序

代码位于：https://github.com/HurleyJames/DataStructure/tree/master/Sort

常见的稳定排序算法有：

• 冒泡排序（Bubble Sort） — $O(n^2)$
• 插入排序（Insertion Sort）— $O(n^2)$
• 桶排序（Bucket Sort）— $O(n)$; 需要$O(k)$额外空间
• 计数排序 (Counting Sort) — $O(n+k)$; 需要$O(n+k)$额外空间
• 归并排序（Merge Sort）— $O(nlogn)$; 需要$O(n)$额外空间
• 二叉排序树排序 （Binary tree sort） — $O(nlogn)$ 期望时间; $O(n^2)$最坏时间; 需要$O(n)$额外空间
• 基数排序（Radix sort）— $O(n·k)$; 需要 $O(n)$额外空间

常见的不稳定排序算法有：

• 选择排序（Selection Sort）— $O(n^2)$
• 希尔排序（Shell Sort）— $O(nlogn)$
• 堆排序（Heapsort）— $O(nlogn)$
• 快速排序（Quicksort）— $O(nlogn)$ 期望时间, $O(n^2)$ 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

冒泡排序

冒泡排序是最简单的也是最基础的排序之一。其大体思想就是通过与相邻元素的比较和交换来把较小的树都排到前面。

比如，一个无序序列5,3,8,6,4。首先从前向后冒泡，5和3比较，把3交换到前面，序变成3,5,8,6,4。5和8无需交换。同理8和6交换，变成3,5,6,8,4。8和4交换，变成3,5,6,4,8。这样一次冒泡就完了，把最大的数8排到最后面了。对剩下的序列依次冒泡就会得到一个有序序列。

$5,3,8,6,4\\ \downarrow\\ 3,5,8,6,4\\ \downarrow\\ 3,5,6,8,4\\ \downarrow\\ 3,5,6,4,8\\ \downarrow\\ 3,5,4,6,8\\ \downarrow\\ 3,4,5,6,8\\$

冒泡排序的时间复杂度为：$O(n^2)$。

选择排序

思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

举个例子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4。对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

$5,3,8,6,4\\ \downarrow\\ 3,5,8,6,4\\ \downarrow\\ 3,4,8,6,5\\ \downarrow\\ 3,4,5,6,8$

选择排序的时间复杂度为：$O(n^2)$。

插入排序

对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。

$5,3,8,6,4\\ \downarrow\\ 3,5,8,6,4\\ \downarrow\\ 3,5,6,8,4\\ \downarrow\\ 3,4,6,8,5\\ \downarrow\\ 3,4,5,8,6\\ \downarrow\\ 3,4,5,6,8$

简单插入排序的时间复杂度为：$O(n^2)$。

快速排序

比如5,3,8,6,4的无序序列，以5作为基准（单独拎出来放在顶上）。思路是右指针找比基准数小的，左指针找比基准数大的，交换之。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,3,8,6,4\\ \downarrow\\ 4,3,8,6,5\\ \downarrow\\ 3,4,5,6,8\\$

快速排序是不稳定的，其时间平均时间复杂度是：$O(nlogn)$。

希尔排序

归并排序

桶排序

基数排序

计数排序