排序 ------1

time,srand,rand,clock函数接口为 数组首元素指针变量(整型类型)数组元素个数void ShellSort(int* a, int n)希尔排序1.预排序预排序一次分成若干组分别插入排序让整个数组接近有序。多次预排序2.插入排序以以下数组为例实现分为gap组各组的每一段的间隔为gap假设是3如下图单趟1.预排序分成若干组分别插入排序让整个数组接近有序先排红色这组,n要防止越界再排其他两组优化成两个循环时间复杂度不变整体因为所以gap要取多次多次预排序即gap是变化的。gap的取值公式是gapn/3 1, 其中n是数组元素个数为了让gap是变化的所以多次循环取gap即有 int gapn;while(gap1){gapgap/3 1;...}任何数循环除以三后就三种结果012。gap1时是预排序1是为了让数组整体按gap1时进行一次插入排序此时希尔排序结束。完整代码如下接口为 数组首元素指针变量(整型类型)数组元素个数void ShellSort(int* a, int n) { int gap n; while (gap1) { gap gap / 3 1; for (size_t i 0; i n - gap; i) { int end i; int tmp a[end gap]; while (end 0) { if (tmp a[end]) { a[end gap] a[end]; end - gap; } else { break; } } a[end gap] tmp; } } }选择排序接口为 数组首元素指针变量(整型类型)数组元素个数void SelectSort(int* a, int n)从小到大排单趟取数组首尾元素下标int begin0,int endn-1。我们分别用mini,maxi表示最小与最大值的下标从第二个元素开始依次循环遍历数组找出mini,maxi找出mini,maxi方法mini,maxi分别指向首元素从第二个元素开始依次与mini,maxi比较若第二个元素比maxi大将第二个元素对应下表赋给maxi若第二个元素比mini小将第二个元素对应下表赋给mini因为mini,maxi都从首元素开始值相同直到end为止。int begin 0, int end n - 1; int mini begin, maxi begin; for (int i begin 1; i end; i) { if (a[i] a[maxi]) { maxi i; } if (a[i] a[mini]) { mini i; } }找到mini,maxi后mini,maxi与begin,end分别进行对应位置元素交换begin,end--注意一种bug情况当首位置是最大值时找出的mini对应的最小值与首元素交换最大值换到了mini对应位置begin位置是最小值最大值与最后元素值交换最大值对应的下标现在依旧认为是maxi(也就是begin位置的最小值)相当于把最小值交换到尾位置。所以在Swap(a[begin] a[mini])后判断begin是否等于maxi若等于, 需将maxi更新为miniSwap(a[begin], a[mini]);if (beginmaxi){maxi mini;}int begin 0, int end n - 1; int mini begin, maxi begin; for (int i begin 1; i end; i) { if (a[i] a[maxi]) { maxi i; } if (a[i] a[mini]) { mini i; } } Swap(a[begin], a[mini]); if (beginmaxi) { maxi mini; } Swap(a[end], a[maxi]); begin; --end;整体此时遍历了一遍数组找出了一组begin,end。现在要让begin,end不断向中间靠拢beginend直至相遇或相交(beginend)时停止void SelectSort(int* a, int n) { int begin 0, end n - 1; while (begin end) { int mini begin, maxi begin; for (int i begin 1; i end; i) { if (a[i] a[maxi]) { maxi i; } if (a[i] a[mini]) { mini i; } } Swap(a[begin], a[mini]); if (beginmaxi) { maxi mini; } Swap(a[end], a[maxi]); begin; --end; } }