插入排序：算法简介：接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。时间复杂度为O(n^2)。最稳定的排序算法但是效率很低代码实现：voidInsertSort(int*arr,intn){for(intindex=0;index<n-1;++index){intend=index+1;inttmp=arr[end];while(end>0&&tmp<arr[end-1]){arr[end]=arr[end-1];end--;}arr[end]=tmp;}}显然当最小的数字在数组的最右端时，此时需要将整个数组进行移位，效率很低，而希尔排序可以有效的改善这个问题希尔排序：希尔排序(ShellSort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。代码实现：voidShellSort(int*arr,intn)//希尔排序{intgap=n;while(gap>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(intindex=0;index<n-gap;++index){intend=index;inttmp=arr[end+gap];while(end>=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世纪经典算法之一，原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,再进行第二趟冒泡，由此我们可以写出以下代码：voidBubbleSort(int*arr,intn){for(inti=0;i<n;++i){for(intj=0;j<n-i-1;++j){if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);}}}这里我们设立一个标记变量flag用来标记数列中的数是否在循环结束前就已经排好序代码改进如下：voidBubbleSort(int*arr,intn){boolflag=true;intk=n;while(flag){flag=false;for(inti=1;i<k;++i){if(arr[i-1]<arr[i]){swap(arr[i-1],arr[i]);flag=true;//有发生交换继续冒泡否则说明已经有序}}k--;}}如果这一趟发生了交换，这flag为rrue，则还需要继续进行冒泡，否则说明数组已经有序，后面的不必进行下去。那么这里给出这样一种情况：（2，1，3，4，5，6，7，8，9，10）第一次循环交换之后我们会发现，后面的数组已经有序，不再需要我们进行冒泡，后面的操作都是不必要的这里我们只需要记录下最后一次进行交换的位置，那么下次遍历只要遍历到这个位置就可以结束。代码进一步优化如下：voidBubbleSort(int*arr,intn){intflag=n;//第一次遍历终点为数组尾while(flag>0){intk=flag;flag=0;for(intj=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；代码实现如下：voidAdJust_down(int*arr,intparent,intsize){intchild=2*parent+1;while(child<size){if(child+1<size&&arr[child+1]>arr[child]){++child;}if(arr[parent]>arr[child])break;swap(arr[parent],arr[child]);parent=child;child=2*parent;}}voidHeapSort(int*arr,intn){for(inti=n/2-1;i>=0;--i){AdJust_down(arr,i,n);}for(inti=n-1;i>=1;--i){swap(arr[0],arr[i]);AdJust_down(arr,0,i);}}思路分析：1.如果要对数字进行升序，我们首先首先将数组初始化为原始大堆for(inti=n/2-1;i>=0;--i){AdJust_down(arr,i,n);//从最后一个非叶子节点开始调整}2.进行排序（以升序为例）大堆的性质为：最大的数据一定在堆顶将堆顶和堆最后一个元素进行交换，则最大的数字此时在数字尾部，再将堆顶元素下调，且堆的大小减1，知道堆大小为1循环结束，排序完成。代码如下：for(inti=n-1;i>=1;--i){swap(arr[0],arr[i]);AdJust_down(arr,0,i);}选择排序选择排序（Selectionsort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法为了减少比较的次数，我们一次遍历同时选出最大值和最小值，代码实现如下：voidSelectSort(int*arr,intn){inti=0,j=n-1;intmax=j;intmin=i;intleft=0;intright=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．再对左右区间重复第二步，直到各区间只有一个数。代码实现如下：intPartSort(int*arr,intleft,intright){intkey=arr[right];//{10,2,8,9,6,1,3,4,5,7,0,-1,-2,-100};intbegin=left;intend=right-1;while(begin<end){while(begin<end&&arr[begin]<=key){begin++;}while(begin<end&&arr[end]>=key){end--;}if(begin<end)swap(arr[begin],arr[end]);}if(arr[begin]>arr[right]){swap(arr[begin],arr[right]);returnbegin;}returnright;}voidQuickSort(int*arr,intleft,intright){if(left>=right)return;intdiv=PartSort(arr,left,right);QuickSort(arr,div+1,right);QuickSort(arr,left,div-1);}