C++常见面试题——内排序

《C++常见面试题——内排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对数组p[n]排序1.插入排序1.1直接插入排序一趟排序：第i趟排序，此时其0...i-1个元素时有序的，相当于把p[i]插入前0...i-1个有序序列中，形成新的有序序列0...i。整个排序过程：对i从1...n-1重复执行上述一趟排序时间复杂度：O(n2)，稳定排序viewplaincopytoclipboardprint?//straightinsertionsortvoidstraight_insertion_sort(intp[],intn){inti=0;for(i=1;i=1;--j){if(tmp

2、[j-1]){p[j]=p[j-1];}else{break;}}p[j]=tmp;}}1.2折半插入排序和直接插入排序唯一不同的是，第i趟排序中，因为0...i-1个元素有序，采用折半查找，来确定p[i]的插入位置时间复杂度：O(n2)，稳定排序viewplaincopytoclipboardprint?//binaryinsertionsortvoidbinary_insertion_sort(intp[],intn){inti=0;for(i=1;i

3、igh)/2;if(tmplow);--j){p[j]=p[j-1];}if(j==low)p[low]=tmp;}}1.3希尔插入排序思想：在直接插入排序中，当待排元素基本有序时，直接插入排序的时间复杂度趋近去O(n)。所以先将整个待排序列分割成若干个子序列进行直接插入排序，但这个序列基本有序时，进行一次直接插入排序。一趟排序：按步长dk将待排元素分成若干子序列，对这些子序列直

4、接插入排序整个排序过程：步长从n/2指数递减至1，结束时间复杂度：O(n*logn)，不稳定排序viewplaincopytoclipboardprint?//shellinsertionsortvoidone_way_shell_insertion_sort(intp[],intn,intdk){inti=0;for(i=dk;i=dk;j=j-dk){if(tmp

5、p[],intn){intdk=0;dk=n/2;while(dk>=1){one_way_shell_insertion_sort(p,n,dk);dk=dk/2;}}2.交换排序2.1冒泡排序一趟排序：第i趟，从n-1...i，比较相邻关键字，“逆序”时交换两者，一趟结束时，可以保证第i个最小完整排序过程：i从0...n-1，重复一趟排序时间复杂度：O(n2)，稳定排序viewplaincopytoclipboardprint?//bubblesortvoidbubble_sort(intp[],intn){inti,j;for(i=0;ii;-

6、-j){if(p[j]

7、high&&p[high]>tmp)--high;if(low