排序（一）【数据结构】

如何判断排序是否稳定看其有没有跳跃交换直接插入排序稳定基本思路每一趟从待排序序列中取第一个值插入到已排序好的序列中特点1.数据越有序效率越高2.时间复杂度最好情况O(n),最坏情况O(n^2)当n比较小的时候n^2也大不到哪去代码实现voidInsert_Sort(intarr[],intlen){for(inti0;ilen-1;i)//控制执行的趟数{inttmparr[i1];intji;for(;j0;j--)//控制对其中某一趟已排序好的序列从右至左的遍历给待插入值留出空位{if(arr[j]tmp)arr[j1]arr[j];elsebreak;}//触底说明现有的已排序好的序列所有元素都大于tmparr[j1]tmp;}}优化将待插入的值插入到已排序好的序列中已排序好的序列是有序的可以用二分法代码实现voidInsert_Sort2(intarr[],intlen){for(inti1;ilen-1;i){inttmparr[i];//通过折半找到arr[i]这个值的合适的插入位置//有序序列范围[0i-]intleft0;intrighti-1;while(leftright){intmid(leftright)/2;if(tmparr[mid]){rightmid-1;}else{leftmid1;}}//此时left保存的是arr[i]应该插入的合适位置下标//先将[left,i-1]整体右移for(intji-1;jleft;j--){arr[j1]arr[j];}arr[left]tmp;}//再将arr[i]赋值给arr[left]结束}希尔排序不稳定也称为缩小增量排序缩小增量数组取值1.尽量互素2.最后一个增量必须是1时间复杂度希尔排序的时间复杂度和给定的缩小增量数组有关其时间复杂度是O(n1.3~n1.7) O(n^1.5)代码实现//希尔排序voidShell(int*arr,intlen,intgap){for(intigap;ilen-1;i)//控制的是当前要调整的元素的下标{inttmparr[i];intji-gap;for(;j0;j-gap)//控制的是对已排序好的序列从右至左的遍历给待插入值流出空位{if(arr[j]tmp)arr[jgap]arr[j];elsebreak;//找到了一个小于或等于tmp的值停下来了}arr[jgap]tmp;//触底了也停下来了说明现有的已排序好的序列中所以元素都大于tmp}}voidShell_Sort(intarr[],intlen){intgap[]{5,3,1};//缩小增量数组intlen_gapsizeof(gap)/sizeof(gap[0]);for(inti0;ilen_gap;i)Shell(arr,len,gap[i]);//按照给出的增量来单次处理的函数}