「数据结构」八大排序(超详解 附动图 源码)(4)

代码如下：
// 希尔排序void ShellSort(int* a, int n){ assert(a); int gap = n; while (gap > 1) { //gap /= 2; gap = gap / 3 1; for (int i = 0; i < n - gap; i ) { int end = i; int x = a[end gap]; while (end >= 0) { if (a[end] > x) { a[end gap] = a[end]; end -= gap; } else { break; } } a[end gap] = x; } }}
希尔排序的特性总结：
希尔排序是对直接插入排序的优化。 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。 时间复杂度O(N^1.5) 空间复杂度O(1) 稳定性：不稳定。

3.选择排序

基本思想：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，
然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，
重复这样的步骤直到全部待排序的数据元素排完 。
动图演示：

代码入下：
这里我们可以进行一个优化，最小值和最大值同时选，然后将最小值与起始位置交换，将最大值与末尾位置交换。
// 选择排序void SelectSort(int* a, int n){ assert(a); int begin = 0;//保存数组的起始位置 int end = n - 1;//保存换数组的末尾位置 while (begin < end) { int maxi = begin;//保存最大元素下标 int mini = begin;//保存最小元素下标 //遍历数组寻找最小和最大元素 for (int i = begin; i <= end; i ) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //将最小元素交换到起始位置 Swap(a begin, a mini); //判断最大值的位置是否在起始位置 if (maxi == begin) { maxi = mini; } //将最大元素交换到末尾位置 Swap(a end, a maxi); //移动数组起始和末尾位置 begin ; end--; }}