排序分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，外部排序因为排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
这里说的排序算法都是内部排序。
排序算法的稳定性： 稳定的排序算法不会改变关键字相同时候两个元素的顺序，也就是所有稳定的排序算法将返回一个排序结构，而不稳定的排序算法对同一组数据排序后，可能产生多种结果，且可能打乱一些其他关键字的顺序。对于简单的元素，这一点并没有什么意义。而现实生活中，排序对象往往复杂，比如学生成绩排序，首先按总分排序，再按数学，语文高低排序，最后是按照名字排序。那么我们会先排名字，然后语文，然后数学，然后总分。这样，如果用了不稳定的排序算法后，前面排的有序的结果可能会被打乱。这样就无法完成这一工作了。
一般来说，若存在不相邻元素间交换，很可能是不稳定的排序.
基本排序
下面三种排序都是课本上一般有介绍的，比较的简单的三种排序算法，它们循环的次数都是(n*n)
在描述排序之前，先定义几个“操作符”：
typedef int Item ;
#define key(A) (A)
#define less(A,B) (key(A) < key(B))
#define exch(A,B) { Item t = A ; A = B ; B = t ; }
#define compexch(A,B) if (less(B,A)) exch(A,B)
冒泡排序
冒泡排序是我学的第一个排序算法，它很简单：遍历数组，如果相邻的两个元素大小不对，就交换两个元素，重复这样的操作直到数组有序。
假设从数组的右往左移动，第一次遍历中，遇到较小元素时，将它与左边元素交换，最后最小元素移到第一位，第二次遍历中，通过交换，将第二小的元素放在第二位，依次类推。
每一次遍历中的当前的最小元素都要向前移动，就想泡泡那样，“冒到”最前端。
代码如下：
void bubble(Item a[] , int l , int r ) {
for ( int i = l ; i < r ; i++ ) {
for ( int j = r ; j > r ; j-- )
compexch(a[j-i],a[j]) ;
}
}
时间复杂度： O(n^2)
空间复杂度： O(n) （用于储蓄这个数组）
冒泡排序是稳定的排序。
可以改进冒泡排序，若某一次遍历中没有发生交换，就说明，该数据已经有序，可以跳出外部循环：
void bubble(Item a[] , int l , int r ) {
for ( int i = l ; i < r ; i++ ) {
int flag = 0 ;
for ( int j = r ; j > r ; j-- ) {
compexch(a[j-i],a[j]) ;
flag = less(a[j-1],a[j]) ;
}
if ( !flag )
break ;
}
}
这种改进能将最好情况下的时间复杂度优化为O(n) （仅做一次外部循环）
选择排序
选择排序是我的学的第二个排序算法，我觉得选择排序是冒泡排序有异曲同工之妙。
冒泡排序将每次遍历交换得到的“最小项”放到相应的位置，而选择排序选出数组中的最小值，与数组的第一位交换，选出数组的次小值，与数组的第二位交换，以此类推。
冒泡排序和选择排序都是每次找出排序后应该第i项的的元素，将这个元素放在数组的第i位。选择排序通过对当前元素和先前找到的最小值相比的操作获取每次的第i项，不需要交换操作，而冒泡排序是通过一次一次的交换实现这一过程，需要更多的执行更多的步骤来将每个元素放在相应的位置。
代码如下：
void selection(Item a[], int l , int r ) {
for ( int i = l ; i < r ; i++ ){
int min = i ;
for ( int j = i + 1 ; j < r ; j++ ) {
if ( less(a[j],a[min]))
min = j ;
}
exch(a[i],a[min]) ;
}
}
时间复杂度： O(n^2)
空间复杂度： O(n)存储整个数列，O(1)储存辅助元素。
因为每次都是无序序列中的最小元素和第一个元素交换，是跨距离的交换，所以选择排序是不稳定的排序。
选择排序相比冒泡排序效率要高一些，因为冒泡排序每一轮的每一次比较之后，如果相邻两个元素大小关系不对，就要立即交换，而选择排序每一轮最多只进行一次交换。但是两者的循环次数是相等的。
但是选择排序也有一个缺点，就是对数组的有序部分利用较少，对排好序的数组排序所花的时间和对随机数组排序所花的时间基本相同，而改进后的冒泡排序，能有效的利用数据原有的有序性。
插入排序
理牌的时候，我们通常只考虑一张牌，每次将一张牌插入已经排好序的牌的适当位置，将原本在这张牌前面的牌挤到了后面的位置。这就是插入排序。
过程如下：
1) 将一个数组分为两部分，有序的和无序的（一个元素可以看作是有序的）
2）从无序部分中拿出一个元素，遍历有序部分，将这个元素插入到有序部分的合适位置
3）将有序部分中的插入元素之后的元素都向后移一位，得到新的有序部分。
4）重复1到3，直到无序部分为空
代码如下：
void insertion(Item a[] , int l , int r ) {
for ( int i = r ; i > l ; i-- )
compexch(a[i-1],a[i]) ; // 这个循环将最小值放到第一位
for ( int i = l+2 ; i < r ; i++ ) {
int j = i ;
Item v = a[i] ;
while (less(v,a[j-1])) { //从后往前遍历，遇到比当前值大的值，后移，反之，跳出循环
a[j] = a[j-1] ;
j-- ;
}
a[j] = v ;
}
}
插入排序是稳定的排序。
时间复杂度： O(n^2)，最好情况下为O(n) （数组已经排好序了）
空间复杂度： O(n)储存数组，O(1)储蓄辅助元素
高效排序
希尔排序
希尔排序是对插入排序的改进，对于大规模的乱序数组，插入排序速度很慢，因为它只能交换相邻元素，元素只能一点点移动到另一端。而希尔排序改进了插入排序，交换不相邻的数组对数组的局部进行排序，最后使用插入排序对局部有序的数组进行排序。
希尔排序的思想是让数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。下图就是h=4的h有序数组
如果h很大，就能在一次交换中，将元素交换到很远的地方，为实现更小的h有序创造条件。希尔排序需要一个递增序列，这个递增序列就是h每次的值。
实现插入排序的方式，就是对于每个h，用插入排序将h个子数组独立地进行排序，子数组之间是独立的，可以在h子数组中将每个元素交换到比它大的元素之前去，只需将插入排序中移动元素的距离由1改成h即可，这样就实现了一个类似于插入排序但是使用不同增量的过程，代码如下 ：
void shell_sort(Item a[], int N){
int h = 1 , i , j ;
while ( h < N/3 )
h = h*3 + 1 ;
while ( h >= 1 ){
for ( i = h ; i < N ; i++ ){
Item tmp = a[i] ;
for ( j = i ; j >= h && less(tmp,a[j-h]) ; j -= h )
a[j] = a[j-h] ;
a[j] = tmp ;
}
h /= 3 ;
}
}
以上代码中h从N／3递减至1。它的递增序列为1，4，13，40，121，363···
希尔排序是不稳定的排序算法。希尔排序是多次插入排序的结果，我们知道，一次插入排序是有序的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
时间复杂度：希尔排序的时间复杂度和递增序列有关，在上述递增序列（1，4，13，121）中，希尔排序的时间复杂度为O(n^(3/2))
空间复杂度：不需要额外的内存空间，o(n)储存数组，O(1)储存辅助元素。
希尔排序没有快速排序算法快O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n^2)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。
堆排序
堆排序是一种选择排序，它利用了完全二叉树中双亲节点和孩子节点之间的内在关系。堆是什么？
堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小顶堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大顶堆。
(1) R[i] <= R[2i+1] 且 R[i] <= R[2i+2] (小顶堆)
(2) R[i] >= R[2i+1] 且 R[i] >= R[2i+2] (大顶堆)
其中，R[2i+1]和R[2i+2]分别是R[i]的左右孩子。
具体过程：
首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
如此反复，直到交换了R[0]和R[1]为止。
以上思想可归纳为两个操作：
（1）根据初始数组去构造初始堆（以大顶堆为例）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大顶堆。
当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
代码如下：
void heap_adjust(Item a[], int s, int e) {
int parent = s , child = 2*s+1 ; // s是当前需要调整的节点，e是此时堆中需要排序的最后一个节点.
Item tmp = a[parent] ; // 存储双亲
while ( child <= e ){
if ( child < e && less(a[child],a[child+1]))
child++ ; // 此时child节点是左右孩子中的较大节点
if ( tmp >= a[child] ) // 双亲大于大孩子，直接退出循环
break ;
a[parent] = a[child] ; // 双亲小于大孩子，双亲和大孩子交换
parent = child ; // 把大孩子赋给双亲
child = child*2 + 1 ; // 选取大孩子的左孩子，继续查找
}
a[parent] = tmp ;
}
void heap_sort(Item a[], int n){
for (int i = n/2-1 ; i >=0 ; i-- ) // 此循环初始化一个大顶堆
heap_adjust(a,i,n-1) ;
for ( int i = n-1 ; i > 0 ; i-- ){ // 不断从堆顶获得最大值，构造新堆
exch(a[0],a[i]) ; // 交换堆顶元素（最大值）和最后一个元素
heap_adjust(a,0,i-1) ; // 调整堆顶元素，构造新堆，获得当前最大值
}
}
堆排序是一种不稳定的排序方法。(需要不断的调整堆不是相邻节点的交换，堆排序属于选择排序，选择排序不稳定)
时间复杂度： O(n*log(n))
空间复杂度： O(1)储存辅助元素
归并排序
归并是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
归并排序有两种实现方法，递归法和迭代法
递归法
归并法工作原理如下（假设序列共有n个元素）：
1）将序列每相邻两个数字进行归并操作（merge)，形成f=(n/2)个子序列，排序后每个序列包含两个元素
2）将上述序列再次归并，形成(n/4)个序列，每个序列包含四个元素
3）重复步骤2，直到所有元素排序完毕
代码如下：
void merge(vector<int> &arr, int l , int m , int r , vector<int> temp ){
int i = l , j = m + 1 , k = 0 ;
while ( i <= m && j <= r )
temp[k++] = (arr[i] < arr[j] ) ? arr[i++] : arr[j++];
while ( i <= m )
temp[k++] = arr[i++] ;
while ( j <= r )
temp[k++] = arr[j++] ;
k = 0 ;
while ( l <= r )
arr[l++] = temp[k++] ;
}
void Msort(vector<int> &arr, int l, int r, vector<int> temp ) {
if ( l < r ) {
int m = (l+r) / 2 ;
Msort(arr,l,m,temp) ;
Msort(arr,m+1,r,temp) ;
merge(arr,l,m,r,temp) ;
}
}
时间复杂度： O(nlog(n))
空间复杂度： O(n) 用于储存数组， O(log(n))用与储存辅助数组.
稳定性：排序过程中需要两两比较，不存在跳跃，所以是一种稳定的排序。
虽然递归法在代码上比较清晰，容易理解，但是归调用会造成时间和空递间上性能的损耗。
迭代法
迭代法没有显示地分割数组，但是它思想也是合并有序的子序列，得到有序序列。
步骤（假设有序列有n个元素）：
1）申请一个大小为n的辅助数组，step从1开始，每次乘二
2）从头开始每两个step长的子序列进行归并，使其有序，将其存在辅助数组（如果是对辅助数组进行排序，就存在原数组里）
3）重复步骤2，直到step 大于数组长度
其中需要注意的问题是在遍历的过程中要防止下表越界。
void merge_sort(vector<int> &arr ) {
int i = 1 , len = arr.size() ;
vector<int> tmp (len) ;
while ( i < len ) {
mergepass(arr,tmp,i) ;
i *= 2 ;
if ( i >= len ) {
for ( int j = 0 ; j < len ; j++ )
arr[j] = tmp[j] ;
return ;
}
mergepass(tmp,arr,i) ;
i *= 2 ;
}
}
void mergepass(vector<int> &s, vector<int> &d , int step ) {
int i = 0 , len = s.size() ;
while ( i < len - step + 1 ) {
int tmp = min(len-1,i+2*step-1) ; // 防止下标越界
merge(s, d,i,i+step-1,tmp) ;
i = 2*step + i ;
}
for ( int j = i ; j < len ; j++ ) // 剩下的长度不足一个step，直接复制
d[j] = s[j] ;
}
void merge(vector<int>&s,vector<int>&d,int l,int m, int r) {
int i = l , j = m+1 , k = l ;
while ( i <= m && j <= r )
d[k++] = (s[i]>s[j]) ? (s[j++]) : s[i++] ;
while ( i <= m )
d[k++] = s[i++] ;
while ( j <= r )
d[k++] = s[j++] ;
}
时间复杂度： O(nlog(n))
空间复杂度： O(n) 用于存储数组和辅助数组。
稳定性：排序过程中需要两两比较，不存在跳跃，所以是一种稳定的排序。
迭代法避免了递归时深度为logn的栈空间，在空间上，只利用了长度与原数组相同的辅助数组，避免递归也在时间性能上有一定提升。
综合来说，归并排序是比较占内存空间，但是高效稳定的排序算法，其中迭代法在时间和空间上一定程度上优于递归法。
快速排序
快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，最后获得一个有序的序列。 步骤：
1） 从数列中挑出一个元素，称为”基准元素”。
2） 排序数列，所有元素比基准元素值小的摆放在基准元素前面，所有元素比基准元素值大的摆在基准的后面（相同的数可以到任一边）。结束之后，该基准元素就处于数列的中间位置。
3） 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码：
void quicksort(vector<int> &arr, int left , int right ) {
if ( left < right ) {
int l = left , r = right , tmp = arr[left] ;
while ( l != r ) {
while ( l < r && arr[r] >= tmp )
r-- ;
arr[l] = arr[r] ;
while ( l < r && arr[l] <= tmp )
l++ ;
arr[r] = arr[l] ;
}
arr[l] = tmp ;
quicksort(arr,left,l-1) ; // 将两边的子序列排序
quicksort(arr,l+1,right) ;
}
}
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。
快速排序之所以叫快速排序，是因为快速排序在最好情况和一般情况下的时间复杂度都是最低的。
时间复杂度：最好和平均情况下，O(nlog(n)) ， 最坏情况下：O(n^2)
空间复杂度：O(n)储存数组，在最好和平均情况下O(log(n))储存辅助数组，最坏情况下O(n)储存数组
非比较排序
前面说的排序都要通过比较完成，下面的排序算法都不是基于比较的。
基数排序
基数排序中，通常将数的不同的位看作是不同的属性（也就是每一轮排序中的基数），也就是依次根据各个位上数字的大小进行排序。
基数排序的基本思想是根据元素中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
基数排序根据先根据高位还是低位开始分为高位排序和低位排序。
人的习惯是高位排序，某两个数只要高位不同就可以直接比较出大小，不用比较低位。
下面用链表实现基数排序的两种。
在描述高位排序和低位排序之前，先声明结构体和一些必要的函数:
struct node {
struct node *next ;
int data ;
node() : data(0), next(NULL) {}
} ;
int num , bit = 4 ; // num为链表中节点个数，bit表示比较4位数
struct node * InitNode(struct node * head , int & num ) ; // 输入num个整型，构造链表，返回链表的头指针（头指针中没有数据）
struct node * GetFirstNode(struct node *head) ; // 返回头节点，并在原链表中删除这个节点
void AppendNode(struct node *head,struct node *tmp) ; // 在head链表的尾部加上tmp指向的指针，并把tmp的next指针指向NULL
void Total(struct node *L, struct node *tmp ) ; // 把tmp链表链接到L链表的末尾
int GetNum(struct node *p , int pos ) ; // 返回p节点的data中的第pos位的整型，若pos等于1，就返回个位上的数字
低位排序
对于n位整数，从整型的低位到高位为基数，依次排序，因为高位的数字比低位的数字对排序的影响大，所以只要通过k次分配收集操作就可以完成排序，k是取决于关键字的多少。用链表实现的代码如下：
void radix_sort(struct node *head) {
struct node *p[10] , *q ;
int i , j , k ;
for( j = 1 ; j <= bit ; j++ ){
for( i = 0 ; i < 10 ; i++ )
p[i] = new node() ;
while( head->next!= NULL ) {
q = GetFirstNode(head) ;
k = GetNum(q,j) ;
AppendNode(p[k],q) ;
}
for( i = 0 ; i < 10 ; i++)
Total(head,p[i]) ;
}
for( i = 0 ; i < 10 ; i++ )
delete(p[i]);
}
高位排序
从整型的高位到低位为基数，依次排序，高位的数字比低位的数字对排序的影响大，后面较低位的排序结果会对已有的高位排序的结果产生错误影响，所以不能直接像低位优先那样依次比较。
高位排序的基本思想是，对排序的到的子集按照相同方法进行排序，是一个递归的过。代码如下：
void radix_sort(struct node *head ,int pos ) {
struct node *p[10] , *q ;
int i , j ,k ;
for ( i = 0 ; i < 10 ; i++ )
p[i] = new node() ;
for ( i = pos ; i >= 1 ; i-- ) {
while ( head->next != NULL ) {
q = GetFirstNode(head) ;
k = GetNum(q,i) ;
AppendNode(p[k],q) ;
}
if ( i == 1 ) {
for ( j = 0 ; j < 10 ; j++ ) {
if ( p[j]->next )
AppendNode(result,p[j]->next) ;
}
return ;
}
for ( j = 0 ; j < 10 ; j++ )
radix_sort(p[j],pos-1) ;
}
for ( i = 0 ; i < 10 ; i++ )
delete(p[i]) ;
return ;
}
递归调用：
以 1114-> 3217-> 5488 -> 6-> 891-> 1->1435-> 23-> 2540-> 9999
第一次调用（千位为0）： 6->891->1->23 (p[0]指向的链表）
第二次调用（百位为0）： 6->1->23
第三次调用（十位为0）： 6->1 此时 (i==1)
就以个位从0到9的顺序依次把p[j]指向的链表链接上去 ，获得1->6
每次i == 1 时就说明排序已经排到个位，根据此时的链表中的数据的个位大小就可以判断（因为其他位数相同）
若。I ！= 1 则说明排序还未到个位，要继续递归调用下去，直到 i == 1
一般来说低位优先法要比高位简单。高位排序是大桶里面分小桶的思想，用递归实现本身会对时间和空间性能上造成损耗，低位排序在代码上比较直观易懂。
时间复杂度：O(kn) k是比较的位数
空间复杂度：O(k+n)
计数排序
计数排序专注于关键字在排序后的序列中应该存在的位置。
步骤：
1） 一次遍历找出待排序序列中的最大元素max和最小元素min。
2） 建立长度为（max-min+1）的辅助数组C，遍历序列，统计序列中每个值为i的元素出现的次数，存入数组C的第（i-min) 项
3） 对辅助数组累加（从C中的第二个元素开始，每一项和前一项相加）
4） 反向填充目标序列：将每个元素i放在新数组的第(i-min)项，每放一个元素就将C(i-min)减去1
代码如下：
void countsort(vector<int> &arr ) {
int len = arr.size() , minn = arr[0] , maxx = arr[0] , i ;
vector<int> temp (len) ;
for ( i = 1 ; i < len ; i++ ) {
maxx = max(maxx,arr[i]) ;
minn = min(minn,arr[i]) ;
}
vector<int> tmp(maxx-minn+1,0) ; // 这样设置辅助数组长度可以节省空间
for ( i = 0 ; i < len ; i++ )
tmp[arr[i]-minn]++ ;
for ( i = 1 ; i < tmp.size() ; i++ )
tmp[i] += tmp[i-1] ;
for ( i = len-1 ; i>=0 ; i-- ) {
temp[tmp[arr[i]-minn]-1] = arr[i] ;
tmp[arr[i]-minn]-- ;
}
arr.assign(temp.begin(),temp.end()) ;
}
值得一提的是，设置辅助数组的长度为(max-min+1)可以节省空间，计数时辅助数组从0开始（arr[i]-min)，反向填充时，只要相应加上min即可。
时间复杂度：O(k+n) k是区间长度（最大元素减去最小元素） ， n是排序的元素个数
空间复杂度：O(k+n
计数排序的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，对于数据范围很大的数组，需要大量时间和内存。