1.插入排序算法
跟我们平时打扑克时排序相似，左手先拿起一张牌，不需要比较，当拿起第二张牌时需要和之前的牌进行比较，如果小于之前的牌i,并且有大于牌i-1时，i就是该张牌要插入的位置，牌i及其以后的牌需要给它腾位置 a[k+1] = a[k];腾好位置之后就把它插入到i的位置即可。
实现算法：
void InsertSort(int s[],int n) { int i, j, k; for(i = 1;i<n;i++) { //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置（从前到后） for(j=i-1;j>=0;j--) if(s[j]<s[i]) break; //如找到了一个合适的位置 if(j != i-1) { //将比a[i]大的数据向后移 int temp = s[i]; for(k = i-1;k>j;k--) s[k+1] = s[k]; //将a[i]放到正确位置上 此时的k = j，故s[j+1] = temp更方便理解 s[k +1] = temp; } } }
2.快速排序
分区排序思想，首先选取一个元素，把所有元素分成比它小（左边）和比它大（右边）两部分，然后再对左右两边进行递归。
算法实现：
void QuickSort(int s[], int l, int r) { if (l < r) { int i = l, j = r, x = s[l]; while (i < j) { while (i < j && s[j] >= x) j--; if (i < j) s[i++] = s[j]; while (i < j && s[i] < x) i++; if (i < j) s[j--] = s[i]; } s[i] = x; QuickSort(s, l, i - 1); QuickSort(s, i + 1, r); } };
3.归并排序
递归合并排序。
首先怎么把两个已经有序的序列合并呢？谁小取谁，如果一个序列已经取完，另一个序列还有就直接插在后面就可以。
void MermoryArray(int s[],int first, int mid ,int last,int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (s[i] <= s[j]) temp[k++] = s[i++]; else temp[k++] = s[j++]; } while (i <= m) temp[k++] = s[i++]; while (j <= n) temp[k++] = s[j++]; for (i = 0; i < k; i++) s[first + i] = temp[i]; };
核心步骤：进行递归调用
void mergesort(int s[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(s, first, mid, temp); mergesort(s, mid + 1, last, temp); MermoryArray(s, first, mid, last, temp); } }
最后就水到渠成了：
bool MergeSort(int s[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(s, 0, n - 1, p); delete[] p; return true; }
效率是挺高的，就是需要额外同等的空间。
4.堆排序 时间复杂度和快速,归并一样 ，为nlogn.
堆排序一般指的是二叉树堆，二叉堆是完全二叉树或近似完全二叉树。
二叉堆满足两个条件：
1.父节点总是大于等于（或者是小于等于）任何一个子节点的键值。
2.每个节点的左子树或者右子树都是一个二叉堆（最大堆或者是最小堆）
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：
