题记：
直接插入排序（稳定）-->希尔排序 ： 属于插入排序
简单选择排序（稳定）-->堆排序 ：属于选择排序
冒泡排序算法（稳定）-->快速排序 ：属于交换排序
归并排序（稳定）
一.直接插入排序----O(n^2)-----稳定的
直接插入排序：是一种将一个记录插入到已经安排好序的有序表中，从而得到一个新的记录数增1的有序表。
1.算法流程：
1）初始时， a[0]自成一个有序区， 无序区为a[1, ... , n-1], 令i=1;
2）将a[i]并入当前的有序区a[0, ... , i-1];
3）i++并重复2）直到i=n-1, 排序完成。
时间复杂度：O(n^2)。
示意图：初始无序数列为 49， 38， 65， 97， 76， 13， 27，49
2. C++实现
void InsertSort(SqList *L){
int i, j;
for( i=2;i<L->length;i++) {
if(L->r[i]<L->r[i-1) {
L->r[0]=L->r[i]; //L->r[0]是哨兵位置
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1]=L->r[j];
L->r[j+1]=L->r[0];
}
}
}
//插入排序，版本3：用数据交换代替版本2的数据后移(比较对象只考虑两个元素)
void StraightInsertionSort3(int a[],int n)
{
for(inti=1; i<n; i++)
for(int j=i-1; i=0 && a[j]>a[j+1] ; j--)
Swap(a[j], a[j+1]);
}
二、冒泡排序算法----O(n^2)---稳定的
冒泡排序：是一种交换排序，它基本思想是，两两比较相邻的关键字，如果反序则交换，直到没有反序的记录为止。
算法流程：
1）比较相邻的两个元素，如果前面的数据大于后面的数据，就将两个数据进行交换；这样对数组第0个元素到第n-1个元素进行一次遍历后，最大的一个元素就沉到数组的第n-1个位置；
2）重复第2）操作，直到i=n-1。
时间复杂度分析：O(n^2)，冒泡排序是一种不稳定排序算法。
冒泡排序的示例：
2. C++实现
void BubbleSort(int p[], int len){
int temp;
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++){
if (p[i]>p[j]){
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
三、简单选择排序-----O(n^2)-----稳定
简单选择排序算法：就是通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i(1<=i<=n)个记录作交换。
算法流程：
1）初始时，数组全为无序区a[0, ... , n-1], 令i=0;
2）在无序区a[i, ... , n-1]中选取一个最小的元素与a[i]交换，交换之后a[0, ... , i]即为有序区；
3）重复2），直到i=n-1，排序完成。
时间复杂度分析：O(n^2)。
直接选择排序的示例：
2. C++实现
void SelectSort(int *p, int len)
{
int minIndex, i, j;
for (i = 0; i < len; i++)
{
minIndex = i;//记录最小数值的下标
for (j = i + 1; j < len; j++)
{
if (p[minIndex]>p[j])
minIndex = j;
}
if (minIndex != i)
{
int temp;
temp = p[i];
p[i] = p[minIndex];
p[minIndex] = temp;
}
}
}
四、希尔排序算法------O(nlogn)~O(n^2)----不稳定
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
算法流程：
1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2）按增量序列个数k，对序列进行k 趟排序；
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
时间复杂度：O(n^(1+e))(其中0
希尔排序的示例：
2. C++实现
//希尔排序
void shellSort(int *p, int len){
int i, j, increment, temp;
for (increment = len / 2; increment > 0; increment /= 2){
for (i = increment; i < len; i++){
if (p[i] < p[i - increment]){
temp = p[i];
for (j = i - increment; j >= 0 && p[j] > temp; j -= increment)
p[j + increment] = p[j];
p[j + increment] = temp;
}
}
}
}
五、堆排序-----O(nlogn)-----不稳定
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
1.堆排序是利用堆（假设利用大顶堆）进行排序的方法；基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将它与堆数组的末尾元素交换，此时末尾元素就是最大值）。然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值，如此反复执行，便能得到一个有序序列了。
2. C++实现
//堆排序
void HeapSort(int a[], int n){
//初始化堆,从最后一个有孩子节点的位置开始调整，最后一个有孩子节点的位置为(n-1)/2或n/2
for (int i = n / 2; i >= 0; i--)
HeapAdjusting(a, i, n);
for (int i = n - 1; i>0; i--)//从最后一个节点开始进行调整
{
swap(a[0], a[i]); //每次交换后都要进行调整，交换堆顶元素和最后一个元素
HeapAdjusting(a, 0, i);
}
}
void HeapAdjusting(int a[], int root, int len) //大顶堆
{
int temp, child;
temp = a[root];
for (child = 2 * root + 1; child < len; child *= 2)
{
if (child + 1 < len&&a[child] < a[child + 1])
child++;
if (temp >= a[child])
break;
a[root] = a[child];
root = child;
}
a[root] = temp;
}
我们先看一个大数据top-K示例：
例子：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
首先，我们知道这是一个典型的top-K问题。
针对大数据问题进行统计首先应该想到的就是Hash_map。所以第一步就是先遍历全部的1千万Query，构建出一个大小为3百万的Hash_map，其中的key值为某条Query，对应的value值为该条Query的查询次数。
建好Hash_map以后，我们接下来的问题就是如何在3百万的Query中找出10个最热门的Query，也就是要用到排序算法。排序算法中效率最高的时间复杂度为O(n*log(n))，
这是最简单粗暴的方法，也是最直接的方法。或者我们进一步优化，该题目是要求寻找top-K问题，那么我们可以直接去前K个Query构建一个数组，然后
对其进行排序。遍历剩余的全部Query，如果某条Query的查询次数大于数组中最小的一个，将数组中最小的Query剔除，加入这条新的Query。
接着调整数组顺序，依次进行遍历，这样的最坏情况下的复杂度为O(n*K)。
但是还可以继续优化寻找top-K的操作，那就是借助小根堆来实现。基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？回答是肯定的，那就是堆。
具体过程是，堆顶存放的是整个堆中最小的数，现在遍历N个数，把最先遍历到的k个数存放到最小堆中，并假设它们就是我们要找的最大的k个数，X1>X2...Xmin(堆顶)，而后遍历后续的(n-K)个数，一一与堆顶元素进行比较，如果遍历到的Xi大于堆顶元素Xmin，则把Xi放入堆中，而后更新整个堆，更新的时间复杂度为logK，如果Xi
一个有关小根堆解决top-K问题的小动画，请点击这个链接。
思想与上述算法二一致，只是算法在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O(K)降到了O(logK)。那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了O(n*logK)，和算法二相比，又有了比较大的改进。
六、归并排序------O(nlogn)-------稳定
1. 归并排序：是将两个（或者两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列都是有序的。然后再把有序子序列合并为整体有序序列。
2. C++实现代码
//merge两个有序数列为一个有序数列
void MergeArr(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
//通过比较，归并数列a和b
while (i <= m && j <= n)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
//将数列a或者b剩余的元素直接插入到新数列后边
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i<k;i++)
a[first+i]=temp[i];
}
//归并排序
void MSort(int a[], int first, int last, int temp[])
{
if (first<last)
{
int mid=(first+last)/2;
MSort(a, first, mid, temp);
MSort(a, mid + 1, last, temp);
MergeArr(a, first, mid, last, temp);
}
void MergeSort(int a[], int len)//为了调用方便封装了一个函数接口
{
int *temp = new int[len];
MSort(a, 0, len - 1, temp);
delete temp;
}
七、快速排序------O(nlogn)-------不稳定
1. 快速排序：是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
2.C++实现代码
//快速排序
void QSort(int a[], int L, int R)
{
if (L<R)
{
int low = L, high = R, pivotkey = a[low];// pivotkey：枢轴
while (low<high)
{//从右向左找小于基准值a[i]的元素
while (low<high&& a[high]>=pivotkey)
high--;
if(low<high)
a[low++] = a[high];
//从左向右找大于基准值a[i]的元素
while (low<high&& a[high]<pivotkey)
low++;
if(low<high)
a[high--] = a[low];
}
//将基准值填入最后的坑中
a[low] = pivotkey;
//递归调用，分治法的思想
QSort(a, L, low - 1);
QSort(a, low + 1, R);
}
}
void QuickSort(int a[], int len) //封装函数接口
{
QSort(a, 0, len - 1);
}
后记：
1.
（1）当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
（2）而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n^2）；
（3）原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
2.
稳定性：排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另
一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会
改变的。另外，如果排序算法稳定，可以避免多余的比较。
稳定的排序算法：冒泡排序、插入排序、归并排序、选择排序。
不是稳定的排序算法：快速排序、希尔排序、堆排序。
3.
选择排序算法准则：
每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。
选择排序算法的依据：
影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：
（1）待排序的记录数目n的大小；
（2）记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
（3）关键字的结构及其分布情况；
（4）对排序稳定性的要求。
4.
设待排序元素的个数为n.
（1）当n较大，则应采用时间复杂度为O(n*logn)的排序方法：快速排序、堆排序或归并排序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序：如果内存空间允许且要求稳定性的；
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
（2）当n较大，内存空间允许，且要求稳定性：归并排序
（3）当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序：当元素分布有序，如果不要求稳定性，选择直接选择排序。
（4）一般不使用或不直接使用传统的冒泡排序。
Pitfall
2016.6
