初学排序算法，我觉得只需要掌握算法的精髓，没必要把所有算法都实现一遍，下面我会实现一些经典的排序算法。（均采用C++实现）
学习的排序算法包含：
1》插入排序(直接插入排序、希尔排序)
2》选择排序（简单选择排序、堆排序）
3》交换排序（快速排序、冒泡排序）
4》归并排序
我认为初学者掌握基本的排序算法的思想即可，其他排序算法基于特定的数据结构和存储结构，遇到具体的实例再学习即可。
前三中排序是最基础的排序，后面两种是其他排序，这篇不做介绍。
下面就开始学习了。
插入排序
插入排序：把一个数插入到一个有序的序列中，并要求插入后此数据序列仍然有序。这种排序思想就是插入排序。
直接插入排序：把余下元素一个一个插入有序表中，每次都从有序表的最后一个元素开始比较，若是小于该元素:data<a[i]，则再与前一个元素比较data[i-1]，...直到找到合适位置，最后把该位置及其以后的元素都向后移动:a[j]=a[j-1]，腾出一个位置让新元素插入。这也是最简单的插入排序算法。
下面是直接插入排序的简单实现：
void insert_sort(int *a,int n) { if(a == NULL || n <= 1) return; for(int i=1;i<n;i++) { /* 存放当前无序的初始序号， *初始先将数组的第一个元素构成有序序列， *将数组的后面的序列看成无序序列， *从数组的第二个元素开始做插入排序 *注意：有序序列已经是从大到小排好的 */ int j=i; int temp=a[i]; while(j && temp<a[j-1]) //一直找到在有序序列中的位置，记录在j中 { a[j]=a[j-1]; //不断将数组元素往后移动，腾出位置 j--; } a[j]=temp; //插入temp，即存放的无序序列中的第一个值 } }
交换插入排序：可以在比较的过程中，直接交换前后位置的元素，一步一步地把插入的元素交换到合适的位置。
void insert_sort(int *a,int n) { if(a == NULL || n <= 1) return; for(int i=1;i<n;i++) { int j=i; //一边插入一边比较交换排序，不需要元素后移腾出空间。 while(j && temp<a[j-1]) { int temp=a[i]; a[j] = a[j-1]; a[j-1] = temp; j--; } } }
折半插入排序：在直接插入中，我们每次都是把一个元素插入到一个有序的序列中。为了使找到位置更高效，我们可以借鉴二分查找的方法，减少比较次数，快速找到合适的插入位置。这就是折半插入的来历。
void binary_insert_sort(int *a,int n) { if(a == NULL || n <= 1) return; int low,high,mid; for(int i=1;i<n;i++) { low = 0; high = i-1; while(low <= high) //采用左闭右闭的区间 { mid = low + (high - low)>>1; //不写成/2是为了防止溢出 if(a[i]>a[mid]) //不断的判断条件，来改变low,mid,high low = mid + 1; else high = mid - 1; } //循环结束的low值就是这个元素插入的位置，至于为什么，自己画个程序的流程就明白了。值就是这个元素插入的位置，至于为什么，自己画个程序的流程就明白了。 int temp = a[i]; //不断的将元素后移 for(int j=i;j>low;j--) a[j] = a[j-1]; a[low] = temp; } }
希尔排序
我们知道当一个序列基本有序时，直接插入会变得很高效。因为此时只需少量的移动元素，操作集中在元素的比较上。基于这种想法，我们就试图把一个序列在进行直接插入前调整得尽量有序。这就是希尔排序(Shell Sort)的核心思路。(Shell只是算法发明者的名字，无特殊含义)
那到底该怎么做呢？
希尔排序一反以前的做法，插入为何只在相邻的元素之间进行，不相邻的同样可以进行。于是，希尔排序也被形象地称为”跳着插“。
那应该隔几个元素进行插入呢？
这就说到希尔排序的另一个名字：缩小增量排序(Diminishing Increment Sort)。实际上这个增量序列或者说步长序列是可以提前指定的。不同的序列可以极大地影响到算法效率，至于最好的步长序列貌似还在研究。不过可以肯定的是最后的一个步长一定是1。因为最后一次是直接插入。
先来看一种最简单、也最常用的步长序列：n/2、n/2/2、... 1 (n是待排序的元素个数)。也是就说，初始步长是n/2，以后每次减半，直到步长为1。
利用这种步长序列，举一个例子：开始序列中加下划线的字体表示每一趟待排序的数字。
原序列: 21 12 4 9 9 5 78 1 (n=8)
下标: 0 1 2 3 4 5 6 7
第一趟：步长step=4，0、4号元素直接插入排序
开始 21 12 4 9 9 5 78 1
结束 9 12 4 9 21 5 78 1
第二趟：步长step=2, 0、2、4、6号元素直接插入排序
开始 9 12 4 9 21 5 78 1
结束 4 12 9 9 21 5 78 1
第三趟：步长step=1，0、1、2、3、4、5、6、7、8号元素直接插入排序(显然这是整体直接插入排序)
开始 4 12 9 9 21 5 78 1
结束 1 4 5 9 9 12 21 78
如何理解每一趟排序：
- 步长序列的长度决定了排序的趟数。
- 每一趟排序，并不是所有元素都参与。参与排序的只能是下标为 0、step、2*step...的元素。
- 插入排序时，采用何种策略。如直接插入、交换插入、折半插入、表插入或者表折半插入，这可任意选择。
- 最后一趟排序的步长一定是1。由第二点可知，最后一趟，全体元素都参与排序。
排序结果中红色9出现在了黑色9的前面，表明希尔排序是不稳定的。
希尔排序的简单实现：
void ShellSort(int *a,int n) { if(a == NULL || n <= 1) return; for(int step = n/2;step >= 1;step = step/2) //规定步长 { //下面采用交换插入排序算法 for(int i=step;i<n;i+=step) for(int j=i;j>0;j-=step) if(a[j]<a[j-step]) swap(a[j],a[j-step]); } }
插入排序算法的个人感受：整体来说，直接插入排序的算法时间复杂度最坏情况下为O（n^2），空间复杂度可以忽略不计。而采用改进后的插入排序算法（包括希尔排序）只是减少元素移动的个数，提高排序的效率。
选择排序（select sort）
简单选择排序
经过一趟排序，可以从n-i+1(i=1,2...)个记录中选取关键字最小的记录作为有序序列中第i个记录。也就是说，每一趟排序，都会排好一个元素的最终位置。
最简单的是简单选择排序。
简单选择排序(Simple Selection Sort，也叫直接选择排序)
简单选择排序的思想：在每一趟排序中，通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换，以此确定第i个记录的最终位置。简单说，逐个找出第i小的记录，并将其放到数组的第i个位置。
下面是简单交换排序的算法实现：
void SimpleSelectSort(int *a,int n) { if(a == NULL && n <= 1) return; int index; //用来记录关键字最小的数组元素的下标 for(int i=0;i<n;i++) { index = i; for(int j=i+1;j<n;j++) //遍历数组的后面的元素找到关键字最小的元素的下标 { if(a[j]<a[index]) index = j; } if(i != index) //当最小关键字的元素的下标和当前的元素不同的时候进行交换 { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } }
堆排序
堆排序(Heap Sort)：使用堆这种数据结构来实现排序。
先看下堆的定义：
最小堆(Min-Heap)是关键码序列{k0,k1,…,kn-1}，它具有如下特性：
ki<=k2i+1，
ki<=k2i+2(i=0,1,…)
简单讲：孩子的关键码值大于双亲的。
同理可得，最大堆(Max-Heap)的定义：
ki>=k2i+1，
ki>=k2i+2(i=0,1,…)
同样的：对于最大堆，双亲的关键码值大于两个孩子的(如果有孩子)。
堆的特点：
- 堆是一种树形结构，而且是一种特殊的完全二叉树。
- 其特殊性表现在：它是局部有序的，其有序性只体现在双亲节点和孩子节点的关系上(树的每一层的大小关系也是可以体现的)。兄弟节点无必然联系。
- 最小堆也被称为小顶堆(根节点是最小的)，最大堆也被称为大顶堆(根节点是最大的)。我们常利用最小堆实现从小到大的排序，最大堆实现从大到小的排序。
这里只讲“堆”这种数据结构的应用之一-------堆排序，而不展开讲“堆”这种数据结构的内部实现的细节。
堆排序的基本原理：大体来说就是根据数组元素建立一个最小堆（从小到大排序）或者最大堆（从大到小排序），然后不断的返回堆顶的元素，删除堆顶的元素后堆内部的结构会发生一些改变，改变结构是为了满足堆的性质，从而不断输出堆顶的元素就是排好序的序列。
堆排序步骤：
- 先建好堆。
- 不断地删除堆顶即可(删除前记得打印堆顶元素)，直到只剩下一个元素。
堆排序的简单实现如下所示：
void HeapSort(int *a,int n) { if(a == NULL && n <= 1) return; createHeap(a,n); //创建堆 while(n > 1) //不断删除堆顶的元素，删除前打印。即是堆排序的顺序。 { cout<<a[0]; deleteAt(a,n,0); } cout<<a[0]; }
具体的原理以及实现的细节可以参考：http://blog.csdn.net/zhangxiangdavaid/article/details/30069623
交换排序：两两比较待排序记录的关键码，若是逆序，则交换，直到无逆序。
其中最简单的交换排序是：冒泡排序。冒泡排序法很稳定，但是不够高效，时间复杂度是O（n^2）。
效率比较高的交换排序法有快速排序。
冒泡排序(Bubble Sort，也叫起泡排序)：
不断地比较相邻的记录，若是不满足排序要求，则交换。
交换时，可从前向后，也可从后向前。
看一个从前向后的排序过程：
原序列 12 3 45 33 6
下标 0 1 2 3 4
第一趟：
3 12 45 33 6 (3,12交换)
3 12 45 33 6 (12,45不用交换)
3 12 33 45 6 (45,33交换)
3 12 33 6 45 (45,6交换)
第二趟：
3 12 33 6 45 (3,12不用交换)
3 12 33 6 45 (12,33不用交换)
3 12 6 33 45 (33,6交换)
第三趟：
3 12 6 33 45 (3,12不用交换)
3 6 12 33 45 (12,6交换)
第四趟：
3 6 12 33 45 (3,6不用交换)
结束。
冒泡排序法的实现（未经优化）：
void swap(int &a,int& b) //交换函数 { int temp = a; a = b; b = temp; } void swap(int& a,int& b) //交换函数也可以这样写，可以自己验证下 { if(a!=b) { a^=b; b^=a; a^=b; } } /*冒泡排序法 *从左到右：遍历的数组下标从0--n-1、0--n-2、...、0--1 *可以看作是将最大元素冒泡到最右边 *从右到左：遍历的数组下标从n-1--0、n-1--1、...、n-1--n-2 *可以看作是将最大元素冒泡到最左边 */ void BubbleSort1(int *a,int n) //冒泡排序法，从左往右 { for(int i=1;i<n;i++) for(int j=0;j<n-i;j++) { if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } void BubbleSort2(int *a,int n) //冒泡排序法，从右往左 { for(int i=1;i<n;i++) for(int j=n-1;j>=i;j--) { if(a[j]>a[j-1]) swap(a[j],a[j-1]); } }
现在可以进行一下优化：
如果在某趟排序的时候没有进行数据的交换，那么就表明已经是有序排列的了，此时就不需要进行排序了，结束程序就可以了。
改进的冒泡排序如下：
void swap(int& a,int& b) { a ^= b; b ^= a; a ^= b; } void BuubbleSort(int* a,int n) { if(a == NULL && n >= 1) return; bool flag = true; //设置一个标志位，当标志位为true才会循环 while(flag == true) { for(int i=1;i<n;i++) for(int j=0;j<n-i;j++) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } else flag = false; //当某一趟循环中没有数据交换的时候，就会将标志位置false } } }
再度优化：下一趟排序向右(或向左)的最远位置，只是简单的减一吗？可否更高效？
可以更加高效，记录上一趟排序时交换元素的最远距离，下一趟排序最远只到这个位置即可。
下面是改进后：
void swap(int& a,int& b) { a ^= b; b ^= a; a ^= b; } void BuubbleSort(int* a,int n) { if(a == NULL && n >= 1) return; bool flag = true; //仍然设置标志位 int j = n-1; //初始的循环上限 while(flag) { for(int i=0;i<j;i++) { if(a[i]>a[i+1]) { swap(a[i],a[i+1]); j = i; //每次记录交换的下标 ,最后一次的j值就是最远交换的下标，也就是下次的循环上限 } else flag = false; //如果某一趟遍历中没有数据的交换，那么就表明已经是排好序的了，可以结束程序了 } } }
快速排序(Quick Sort)也是一种交换排序，它在排序中采取了分治策略。
- 从待排序列中选取一元素作为轴值(也叫主元)。
- 将序列中的剩余元素以该轴值为基准，分为左右两部分。左部分元素不大于轴值，右部分元素不小于轴值。轴值最终位于两部分的分割处。
- 对左右两部分重复进行这样的分割，直至无可分割。
- 如何选择轴值？(轴值不同，对排序有影响吗？)
- 如何分割？
void swap(int& a,int& b) { a ^= b; b ^= a; a ^= b; } //以第一个元素为枢轴。 void QuickSort(int* a,int n) { //第一次分区开始 int i=0,j=n-1; int pivotkey = a[0]; //枢轴的值 int pivot = 0; //枢轴的位置 while(i<j) { while(i<j && a[j]>=a[0]) j--; if(i<j) swap(a[i],a[j]); while(i<j && a[i]<=a[0]) i++; if(i<j) swap(a[i],a[j]); } a[i] = pivotkey; //到这里，第一次分区结束 QuickSort(a,i); //递归枢轴左半部分 QuickSort(a+i+1,n-i-1); //递归枢轴右半部份 } //以最后一个元素作为枢轴 void QuickSort(int* a,int n) { int pivot = n-1; //以最后的一个元素作为枢轴 int pivotkey = a[n-1]; int i=0,j=n-1; while(i<j) { while(i<j && a[i]<=pivotkey) i++; if(i<j) swap(a[i],a[j]); while(i<j && a[j]>=pivotkey) j--; if(i<j) swap(a[i],a[j]); } a[i] = pivotkey; QuickSort(a,i); QuickSort(a+i+1,n-i-1); }
枢轴的选取策略：为了让轴值pivot不至于无效(不让pivot出现最值的情况)。我们可以使用一些策略来改进pivot的选取
例如：可以通过随机数来选取pivot：
int SelectPivot(int a[], int low, int high) { int size = high - low + 1; srand((unsigned)time(0)); return a[low + rand()%size]; }
也可以 通过其他方式来取值。
快速排序的非递归实现可以参考：http://blog.csdn.net/zhangxiangdavaid/article/details/25436609
小结：进阶版的插入排序法是希尔排序法，进阶版的选择排序法是堆排序法，进阶版的交换排序法是快速排序法。快排是公认的效率最高的排序法，最好的情况是O(nlogn)，最坏情况才是O(n^2)。
其他排序法（例如简单的归并排序法）会在我的下一个博文中介绍。