插入排序：算法简介：接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。时间复杂度为O(n^2)。 最稳定的排序算法但是效率很低代码实现：void InsertSort(int *arr,int n){ for (int index = 0; index < n-1; ++index) { int end = index+1; int tmp = arr [end]; while (end>0&&tmp 1)//由于gap=gap/3+1 最小值为1 则在gap=1时跳出循环 { gap = gap / 3 + 1; //{ 2, 8, 9, 6, 1, 3, 4, 5, 7, 0 ,-1,-2}//注意这里的＋1 当gap=1时此时排序等同于插入排序 但是由于之前将最小的数据已经移到最左边所以效率//高于插入排序 for (int index = 0; index = 0 && arr [end]>tmp) { arr[end+gap] = arr [end]; end -=gap;//此时插入间距为end } arr[end+gap] = tmp; } }}附注：上面希尔排序的步长选择都是从n/3+1开始，每次再取上一次的三分之一加1，直到最后为1。关于希尔排序步长参见维基百科：http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F冒泡排序：20世纪经典算法之一，原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,再进行第二趟冒泡，由此我们可以写出以下代码：void BubbleSort(int *arr, int n){ for (int i = 0; i < n; ++i) { for (int j = 0; j < n - i - 1; ++j) { if (arr [j]>arr[j + 1]) swap( arr[j], arr [j + 1]); } }}这里我们设立一个标记变量 flag用来标记数列中的数是否在循环结束前就已经排好序代码改进如下：void BubbleSort(int *arr, int n){ bool flag = true ; int k = n ; while (flag) { flag = false; for (int i = 1; i < k; ++i) { if (arr [i - 1] 0) { int k = flag; flag = 0; for (int j = 1; j < k; ++j) { if (arr [j - 1] > arr[j]) { swap( arr[j - 1], arr [j]); flag = j;//后面的已经排序好 记录下下一次排序的终点 } } }}虽然有了这么多优化，但是冒泡排序总体还是一种效率很低的排序，数据规模过大时不适合使用这种排序堆排序：堆的定义： 1.堆是一颗完全二叉树 2.父结点总是大于或等于（小于或等于）任何一个子节点 3每个结点的左子树和右子树都是一个二叉堆 当父结点总是大于或等于任何一个子节点值时为最大堆。反之则为最小堆堆的结构示意图如下：存储方式：我们使用数组来存储一个堆，可以看出设父节点下标值为i 其左孩子下标值为2*i+1,右孩子为2*1+2；代码实现如下：void AdJust_down(int *arr, int parent, int size ){ int child = 2 * parent +1; while (child arr[child]) { ++child; } if (arr [parent]> arr[child]) break; swap( arr[parent ], arr[child]); parent = child; child = 2 * parent; }}void HeapSort(int *arr,int n){ for (int i = n/2-1; i >= 0; --i) { AdJust_down( arr, i, n ); } for (int i = n - 1; i >= 1; --i) { swap( arr[0], arr [i]); AdJust_down( arr, 0, i); }}思路分析：1.如果要对数字进行升序，我们首先首先将数组初始化为原始大堆 for (int i = n/2-1; i >= 0; --i) { AdJust_down( arr, i, n );//从最后一个非叶子节点开始调整 }2.进行排序（以升序为例）大堆的性质为：最大的数据一定在堆顶将堆顶和堆最后一个元素进行交换，则最大的数字此时在数字尾部，再将堆顶元素下调，且堆的大小减1，知道堆大小为1循环结束，排序完成。代码如下： for (int i = n - 1; i >= 1; --i) { swap( arr[0], arr [i]); AdJust_down( arr, 0, i); }选择排序选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法为了减少比较的次数，我们一次遍历同时选出最大值和最小值，代码实现如下：void SelectSort(int *arr, int n){ int i = 0, j = n - 1; int max = j; int min = i; int left = 0; int right = n - 1; while (left<=right) { min = left; max = right; ///！！！！！！！！！！！重点 for (i = left, j = right; i <= j; i++) { if (arr [min]>arr[i]) min = i; if (arr [max] < arr[i]) { 2, 9, 6, 1, 3, 4, 5, 7, 0 ,-8,1,-2} max = i; } if (left != min) { swap( arr[left], arr [min]); if (max == left) max = min; } if (right != max) swap( arr[right], arr [max]); left++; right--; }}这里我们必须注意到，以升序为例，如果一次遍历找到的最大值刚好在数组左边，此时肯定会先被移走，此时就最大值得下标就得更新为转移后的位置快速排序：该方法的基本思想是：1．先从数列中取出一个数作为key。2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3．再对左右区间重复第二步，直到各区间只有一个数。代码实现如下：int PartSort(int *arr, int left, int right){ int key = arr [right]; //{ 10,2, 8, 9, 6, 1, 3, 4, 5, 7, 0 ,-1,-2,-100}; int begin = left ; int end = right - 1; while (begin <=key) { begin++; } while (begin =key) { end--; } if (begin < end) swap( arr[begin], arr [end]); } if (arr [begin]>arr[right]) { swap( arr[begin], arr [right]); return begin; } return right ;}void QuickSort(int *arr, int left,int right){ if (left >= right) return; int div = PartSort(arr , left, right); QuickSort( arr, div + 1, right ); QuickSort( arr, left , div - 1);}