排序算法经过较长时间的演变，产生了很多不同的种类，每种算法都有它特定的使用场景，因此，我们很有必要对所有常见的排序算法进行归纳。排序算法分为内部排序和外部排序，在排序过程中，全部记录存放在内存中，则称为内排序，如果数据量很大，排序过程中需要使用外存，则称为外排序。
常见的内部排序算法，可以归纳为以下五大类：
(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
(2)、选择排序：直接选择排序、堆排序。
(3)、交换排序：冒泡排序、快速排序。
(4)、归并排序
(5)、基数排序
各种排序算法的时间复杂度、空间复杂度及稳定性比较：
在本文中主要分析的都是常见的内部排序算法，将会尽力用简短易于理解的语言来分析。
1、冒泡排序
基本思想
两个数比较大小，较大的数下沉，较小的数冒起来。
算法步骤
1. 从最后一个数开始，与前一个数两两比较，如果后者大于前者，就交换位置，循环n-1次，直至第2个数，与第1个数比较大小，最终最小数被交换到第一个位置，这样第一个最小数的位置就排好了。
2. 从最后一个数开始，重复同样的操作，循环n-2次，直至第3个数，与第2个数比较，这样第二个最小数的位置也排好了。
3. 依次类推。
代码实现
public static void BubbleSort(int [] arr){
int temp;//临时变量
for(int i=0; i<arr.length-1; i++){ //表示趟数，一共arr.length-1次。
for(int j=0; j<arr.length-i-1; j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
时间空间复杂度
冒泡排序不管序列是怎样，都是要比较n(n-1)/2 次的，最好、最坏、平均时间复杂度都为O(n²)，需要一个临时变量用来交换数组内数据位置，所以空间复杂度为O(1)。
2、选择排序
基本思想
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
…
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
算法步骤
首先初始化最小元素索引值为首元素，依次遍历待排序数列，若遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置，直至遇到尾元素，结束一次遍历，并将最小索引处元素与首元素交换；然后，初始化最小索引值为第二个待排序数列元素位置，同样的操作，可得到数列第二个元素即为次小元素；以此类推。
冒泡排序法与选择排序法的区别：
（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；
（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；
（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；
代码实现
public static void select_sort(int array[],int n){
for(int i=0;i<n-1;i++){
int minIndex = i;
for(int j=i+1;j<n;j++){
if(array[j]<array[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
时间空间复杂度
选择排序是冒泡排序的改进，同样选择排序无论序列是怎样的都是要比较n(n-1)/2次的，最好、最坏、平均时间复杂度也都为O(n²)，需要一个临时变量用来交换数组内数据位置，所以空间复杂度为O(1)。
3、插入排序
基本思想
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
算法步骤
代码实现
public static void insert_sort(int array[],int n){
int temp;
for(int i=0;i<n-1;i++){
for(int j=i+1;j>0;j--){
if(array[j] < array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}else{ //不需要交换
break;
}
}
}
}
时间空间复杂度
插入排序不同，如果序列是完全有序的，插入排序只要比较n次，无需移动时间复杂度为O(n)，如果序列是逆序的，插入排序要比较O(n²)和移动O(n²) ，所以平均复杂度为O(n²)，最好为O(n)，最坏为O(n²)，排序过程中只要一个辅助空间，所以空间复杂度O(1)。
4、快速排序
基本思想
通过一趟排序将要排序的数据分割为两部分，第一部分所有数据比第二部分的所有数据小，按照这种思路将两部分数据再次分别进行快速排序，可以使用递归完成，最终使得整个数据序列有序。这里用到了一个典型的分治思想。
算法步骤
在待排数据中找一个基准数据（通常取第一个数），接下来将待排数据中比基准数据小的放在待排数据的左侧，将比待排数据中比基准数据大的放在待排数据右侧。此时，左右两个分区的元素相对有序，接着采用上述思路继续对左右两个分区继续排序，直到各分区只有一个元素位置。
更多信息请参考： java快速排序法
代码实现
public static void quickSort(int[] a, int low, int high) {
if (low < high) { // 如果不加这个判断递归会无法退出导致堆栈溢出异常
int middle = getMiddle(a, low, high);
quickSort(a, 0, middle - 1);
quickSort(a, middle + 1, high);
}
}
private static int getMiddle(int[] a, int low, int high) {
int temp = a[low];// 基准元素
while (low < high) {
// 找到比基准元素小的元素位置
while (low < high && a[high] >= temp) {
high--;
}
a[low] = a[high];
while (low < high && a[low] <= temp) {
low++;
}
a[high] = a[low];
}
a[low] = temp;
return low;
}
时间空间复杂度
快速排序的时间复杂度最好是O(nlog2n)，平均也是O(nlog2n)，最坏情况是序列本来就是有序的，此时时间复杂度为O(n²)，快速排序的空间复杂度可以理解为递归的深度，而递归的实现依靠栈，平均需要递归logn次，所以平均空间复杂度为O(log2n)。
5、归并排序
基本思想
归并排序法是将两个有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。
算法步骤
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
归并排序算法遵循分治模式，操作如下：
分解：分解待排序的具有n个元素的序列，成为具有n/2个元素的两个子序列；
解决：使用归并排序递归地排序子序列；
合并：合并已排序的两个子序列产生已排序的答案。
代码实现
public static int[] mergeSort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSort(nums, low, mid);
// 右边
mergeSort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
时间空间复杂度
归并排序需要一个临时temp[]来储存归并的结果，空间复杂度为O(n)，时间复杂度为O(nlog2n)，可以将空间复杂度由 O(n) 降低至 O(1)，然而相对的时间复杂度则由 O(nlog2n) 升至 O(n²)。
6、希尔排序
基本思想
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小，并重复上述过程。直至增量为1，此时数据序列基本有序，最后进行插入排序。
算法步骤
代码实现
public static void shellSort(int a[]){
int temp = 0;
int d = a.length;
while(true){
d = d/2;
for(int k = 0;k<d;k++){ //根据增量分为若干子序列
for(int i=k+d;i<a.length;i+=d){
for(int j=i;j>k;j-=d){
if(a[j]<a[j-d]){
temp = a[j-d];
a[j-d] = a[j];
a[j] = temp;
}else{
break;
}
}
}
}
if(d == 1){
break;
}
}
}
时间空间复杂度
希尔排序的时间复杂度分析及其复杂，有的增量序列的复杂度至今还没人能够证明出来，只需要记住结论就行，{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n²)，Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n^1.5)，Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3），其中最好的一个序列是{1,5,19,41,109,…}，需要一个临时变量用来交换数组内数据位置，所以空间复杂度为O(1)。
7、堆排序
基本思想
堆即是一棵完全二叉树。堆排序的核心是堆调整算法。首先根据初始输入数据，利用堆调整算法shiftDown()形成最大堆；然后，将堆顶元素与堆尾元素交换，缩小堆的范围并重新调整为最大堆，如此往复。堆排序是一种不稳定的排序算法。
算法步骤
1. 将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。
代码实现
public static void minHeapSort(int a[],int n){
int temp = 0;
makeMinHeap(a,n);
for(int i=n-1;i>0;i--){
temp = a[0];
a[0] = a[i];
a[i] = temp;
MinHeapFixdown(a,0,i);
}
}
//构建最小堆
public static void makeMinHeap(int a[], int n){
for(int i=(n-1)/2 ; i>=0 ; i--){
minHeapFixdown(a,i,n);
}
}
//从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
public static void minHeapFixdown(int a[],int i,int n){
int j = 2*i+1; //子节点
int temp = 0;
while(j<n){
//在左右子节点中寻找最小的
if(j+1<n && a[j+1]<a[j]){
j++;
}
if(a[i] <= a[j])
break;
//较大节点下移
temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2*i+1;
}
}
时间空间复杂度
堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程，初始化建堆时的时间复杂度为O(n)，更改堆元素后重建堆的时间复杂度为O(nlog2n)，所以堆排序的平均、最好、最坏时间复杂度都为O(nlog2n)，堆排序是就地排序，空间复杂度为常数O(1)。
8、基数排序
基本思想
BinSort想法非常简单，首先创建数组A[MaxValue]；然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。
算法步骤
代码实现
public static void radixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
//A:原数组
//temp:临时数组
//n:序列的数字个数
//k:最大的位数2
//r:基数10
//cnt:存储bin[i]的个数
for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
//初始化
for(int j=0;j<r;j++){
cnt[j] = 0;
}
//计算每个箱子的数字个数
for(int j=0;j<n;j++){
cnt[(A[j]/rtok)%r]++;
}
//cnt[j]的个数修改为前j个箱子一共有几个数字
for(int j=1;j<r;j++){
cnt[j] = cnt[j-1] + cnt[j];
}
for(int j = n-1;j>=0;j--){ //重点理解
cnt[(A[j]/rtok)%r]--;
temp[cnt[(A[j]/rtok)%r]] = A[j];
}
for(int j=0;j<n;j++){
A[j] = temp[j];
}
}
}
时间空间复杂度
基数排序对于 n 个记录，执行一次分配和收集的时间为O(n+r)，如果关键字有 d 位，则要执行 d 遍，所以总的时间复杂度为 O(d(n+r))。该算法的空间复杂度就是在分配元素时，使用的桶空间，空间复杂度为O(r+n)=O(n)。
