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

对数组p[n]排序1.插入排序1.1直接插入排序一趟排序：第i趟排序，此时其0...i-1个元素时有序的，相当于把p[i]插入前0...i-1个有序序列中，形成新的有序序列0...i。整个排序过程：对i从1...n-1重复执行上述一趟排序时间复杂度：O(n2)，稳定排序view plaincopy to clipboardprint?//straight insertion sort void straight_insertion_sort(int p[], int n) { int i = 0; for(i = 1; i n; ++i) { int tmp = p[i]; int j = 0; for( j = i; j = 1; --j) { if(tmp p[j-1]) { p[j] = p[j-1]; } else { break; } } p[j] = tmp; } } 1.2折半插入排序和直接插入排序唯一不同的是，第i趟排序中，因为0...i-1个元素有序，采用折半查找，来确定p[i]的插入位置时间复杂度：O(n2)，稳定排序view plaincopy to clipboardprint?//binary insertion sort void binary_insertion_sort(int p[], int n) { int i = 0; for(i = 1; i n; ++i) { int tmp = p[i]; int low = 0, high = i-1; while(low = high) { int mid = (low + high)/2; if(tmp p[mid]) high = mid - 1; else low = mid + 1; } //low = high + 1 printf(low=%d, high=%d, i=%d\n,low, high, i); int j = 0; for( j = i; (j low); --j) { p[j] = p[j-1]; } if( j== low) p[low] = tmp; } } 1.3希尔插入排序思想：在直接插入排序中，当待排元素基本有序时，直接插入排序的时间复杂度趋近去O(n)。所以先将整个待排序列分割成若干个子序列进行直接插入排序，但这个序列基本有序时，进行一次直接插入排序。一趟排序：按步长dk将待排元素分成若干子序列，对这些子序列直接插入排序整个排序过程：步长从n/2指数递减至1，结束时间复杂度：O(n*logn)，不稳定排序view plaincopy to clipboardprint?//shell insertion sort void one_way_shell_insertion_sort(int p[], int n, int dk) { int i = 0; for(i = dk; i n; ++i) { int tmp = p[i]; int j = 0; for( j = i; j = dk; j=j-dk) { if(tmp p[j-dk]) { p[j] = p[j-dk]; } else { break; } } p[j] = tmp; } } void shell_insertion_sort(int p[], int n) { int dk = 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)，稳定排序view plaincopy to clipboardprint?//bubble sort void bubble_sort(int p[], int n) { int i , j; for(i = 0; i n; ++i) { for(j = n-1; j i; --j) { if(p[j] p[j-1]) { int tmp = p[j]; p[j] = p[j-1]; p[j-1] = tmp; } } } } 2.2快速排序一趟排序：找一个关键字key，通过一趟排序将记录分成两部分，前部