前言

1、排序分类

2、排序比较

3、各种排序介绍

1. 简单排序算法包括选择排序、插入排序、冒泡排序等，高级排序算法包括归并排序、快速排序、推排序等等。
2. 冒泡排序和选择排序用的不是很多，因为时间复杂度高，但是因为常数项少，小规模排序执行时间不一定比其他排序长。
3. 插入排序 虽然时间复杂度高，但是因为常数项比较小，通常用在大致排序完成后最后的调整阶段。比如Java中Array.sort()的底层实现便用了二分插入排序（长度小于32的Tim sort算法）。
4. 快速排序和归并排序是最常用的。堆排序的思想比较重要，涉及到优先队列的问题。
5. 基数排序能够解决一些特定的问题。

一、冒泡排序

平均时间复杂度：O(n^2)； 最优时间复杂度：O(n)，最差时间复杂度：O(n^2)

思想： 冒泡排序是最慢的排序算法。从第一个开始，相邻两个数进行比较，如果前1个数大于后一个数，则进行调换，这样换到最后，最大的那个就会在最后面，重复这个过程，较大的就会逐个累积在后面，本质思想就是大的在一轮中会逐渐冒泡到后排。

步骤：

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

运行过程如图所示：

代码如下：

//从小到大排序
void BubbleSort(int arr[], int length){
	for (int i=0; i<length-1; i++){
		for (int j=0; j<length-i-1; j++){
			if (arr[j] > arr[j+1]){
				int temp;
				temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

二、选择排序

时间复杂度：O(n^2)

思想： 最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度。从第一个开始，然后从下一个开始遍历一遍找到最小的，然后跟第一个进行交换，这样就完成一轮，然后选择第二个，开始第二轮，直到n-1轮。

步骤：

1. 遍历一遍，找到整个数组中最小的数，与位置0的数交换位置。
2. 从1位置开始，继续遍历，找到最小的数，与1位置交换。以此类推。

运行过程如图所示：

代码如下：

void SelectSort(int arr[], int length){
	for (int i=0;i<length-1;i++) {
		int minn=i;
        for (int j=i+1;j<length;j++){
        	if(arr[j]<arr[minn])
        		minn=j;
        }
        int t=arr[i];
        arr[i]=arr[minn];
        arr[minn]=t;
    }
}

三、插入排序

平均时间复杂度：O(n^2)； 最优时间复杂度：O(n)，最差时间复杂度：O(n^2)

思想： 插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。类似于打扑克牌拿牌的时候，拿到第一张，然后拿第二张，如果第二张小于第一张则放到第一张的前面，拿到第三张，如果小于第二张，则第三张放到第二张的位置，原本的第二张及以后的都往后退一步。

步骤：

1. 从1位置开始，比较与前面数的大小，如果小于前面的数，则交换位置，直到不再小于停止。
2. 接着从2位置开始，重复这个过程。直到最后位置为止。
3. 时间复杂度取决于数组的排序情况。当数组基本有序时候，复杂度很低，接近O（n）。当数组完全无序时，每个数都要经过多次移动，复杂度趋近于O（n²）。

运行过程如图所示：

代码如下：

void InsertSort(int arr[], int length){
	for (int i=1; i<length; i++) {
            for (int j=i-1; j>=0&&arr[j]>arr[j+1]; j--) {
                int t;
                t=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=t;
            }
     }
}

四、希尔排序

平均时间复杂度：O(n^1.3)； 最优时间复杂度：O(n)，最差时间复杂度：O(n^2)

思想： 希尔排序是借鉴了插入排序在基本有序下非常高效的特点，是插入排序的一种优化。先将整个待排序的元素序列分割为若干个子序列（由相隔某个“增量”的元素组成）分别进行插入排序，然后依次缩减增量进行排序，等到整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

步骤：

1. 选择增量 ：gap=length/2，不断缩小增量：gap = gap/2，最后用序列表示增量选择，{n/2, (n/2)/2, …, 1}
   （此处选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。）

2. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

3. 按增量序列个数k，对序列进行k趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序;

4. 当增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

运行过程如图所示：

代码如下：

//注意从0开始到n-1 
void shell_sort(int a[], int n){  //a[]待排序的数组, n为数组的长度
    for (int gap=n/2;gap>0;gap/=2){ // gap为步长，每次减为原来的一半。
        // 共gap个组，对每一组都执行直接插入排序
        for (int i=0;i<gap;i++){
            for (int j=i+gap;j<n;j+=gap){ 
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
                if (a[j]<a[j-gap]){
                    int tmp = a[j];
                    int k;
                    for(k=j-gap;k>=0 && a[k]>tmp;k-=gap)
                        a[k+gap]=a[k];
                    a[k+gap]=tmp;
                }
            }
        }
    }
}

五、归并排序

时间复杂度：O(nlog2n)

思想： 归并排序是建立在归并操作上的一种排序算法，是一种分治思想，归并的归是递归分解数列，并是合并有序数列。它是稳定排序，时间复杂度：O(nlog2n)，同时相对于快排，它占用较多的空间。

步骤：

1. 划分问题： 把序列分成元素个数尽量相等的两半。

2. 递归求解： 把两半元素分别排序。

3. 合并问题： 把两个有序表合并成一个。

运行过程如图所示：

代码如下：

int a[1010],t[1010];
void MergeSort(int l,int r){
	if(l==r)	return;
	int mid=(l+r)>>1;
	MergeSort(l,mid);
	MergeSort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid && j<=r){
		if(a[i]<=a[j]){
			t[k]=a[i];
			k++,i++;
		}
		else{
			t[k]=a[j];
			k++,j++;
		}
	}
	while(i<=mid){
		t[k]=a[i];
		k++,i++;
	}
	while(j<=r){
		t[k]=a[j];
		k++,j++;
	}
	for(int i=l;i<=r;i++)
		a[i]=t[i];
}

六、快速排序

平均时间复杂度：O(nlog2n)； 最优时间复杂度：O(nlog2n)，最差时间复杂度：O(n^2)

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

步骤：

1. 先从数列中取出一个数作为基准数

2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3. 再对左右区间重复第二步，直到各区间只有一个数

推荐一篇关于快速排序原理详解的博客：白话经典算法系列之六 快速排序 快速搞定

运行过程如图所示：

代码如下：

void quick_sort(int a[],int l,int r){
	if(l<r){
		int i=l,j=r,x=a[l];
		while(i<j){
			while(i<j && a[j]>=x) // 从右向左找第一个小于x的数
				j--;
			if(i<j)
				a[i++]=a[j]; //将a[j]填到a[i]中，a[j]就形成了一个新的坑,并右移一位 
			while(i<j && a[i]<x) // 从左向右找第一个大于等于x的数
				i++;
			if(i<j)
				a[j--]=a[i]; //将a[i]填到a[j]中，a[i]就形成了一个新的坑，并左移一位 
		}
		a[i]=x;
		quick_sort(a,l,i-1);	// 递归调用
		quick_sort(a,i+1,r);
	} 
} 

后续待更新