直接插入排序、希尔排序、选择排序-育师

直接插入排序和希尔排序

直接插入排序

编辑

单趟

全过程

希尔排序

简单版本希尔排序

完整版希尔排序

选择排序

算法简介

代码实现

直接插入排序和希尔排序

直接插入排序实际上可以视作是希尔排序的组件，所以我这里将直接插入排序和希尔排序放到一起了

直接插入排序

下面是直接插入排序的升序例子

我们可以看到，直接插入排序就是将一个值“拿出来”，将他和他将要插入的值的前一个值依次对比

如果拿出来的值小于该值，就将拿出来的值插入到前面比较过的位置，此时break

如果拿出来的值大于该值，就将对比后的值向后挪，继续向前遍历

单趟

void InsertSort(int* arr, int n) { int end;//按下不表，芝士拿出来的值的上一个值的下标 int temp = arr[end + 1]; while (end >= 0) { //当arr[end]大于temp是继续遍历 if (arr[end] > temp) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = temp; }

这里我将最后插入做了统一处理

当在end>=0时找到了合适的插入位置，此时end+1位置上的数已经移动到了上一个end+1的位置上（按照此时的位置就是end+2）,相当于是此时end+1上的值是无效的，此时我们将temp赋值给arr[end+1]

当在end>=0的范围内都没有找到合适得插入位置，此时end=-1(刚刚跳出循环)，end+1正好是0，没有越界，也符合实际：此时temp是最小的，插到最前面。

全过程

void InsertSort(int* arr, int n) { for (int begin = 0; begin < n - 1; begin++) { int end = begin; int temp = arr[end + 1]; while (end >= 0) { //当arr[end]大于temp是继续遍历 if (arr[end] > temp) { arr[end + 1] = arr[end]; //这一步是挪动arr中的值 end--; } else { break; } } arr[end + 1] = temp; //这里将所有的情况统一处理，并处理了end = -1的边界情况 } }

这里相当于是每次都对begin+1(也是end+1)的数据进行排序

所以for循环是这样写的：

for (int begin = 0; begin < n - 1; begin++)

这里的直接插入排序实际上改几下就是希尔排序

希尔排序

希尔排序（Shell Sort），全称“缩小增量排序”（Diminishing Increment Sort），是插入排序的一种更高效的改进版本

直接插入排序在碰到全是逆序的数据使会变得非常的坑，这时，希尔排序就通过将数据大踏步的向后调整的预排序使数据更趋向于有序，从而大大减少了计算量

希尔排序的本质是分组。它不再把数组看作一个整体，而是根据一个“增量”（gap）将数组分割成若干个子序列，这个过程中所有的值都被遍历了一遍。

希尔排序通过让元素“跳跃式”地向最终位置移动，大幅减少了数据交换和移动的次数

简单版本希尔排序

我们先写一个gap=3的，只进行一次预排序的希尔排序

void ShellSort(int* arr, int n) { int gap = 3; for(int i = 0; i <gap; i++)//分组写法 { for (int begin = i; begin < n - gap; begin += gap) { int end = begin; int temp = arr[end + gap]; while (end >= i) { if (arr[end] > temp) { arr[end + gap] = arr[end]; end--; } else { break; } } arr[end + gap] = temp; } } for (int begin = 0; begin < n - 1; begin++) { int end = begin; int temp = arr[end + 1]; while (end >= 0) { if (arr[end] > temp) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = temp; } }

这个希尔排序只进行了一次粗排，而且gap也是写死的，这实际上是不够完善的，对于大量的数据，只进行这一次预排序显然是不够的

这时我们就应该将gap写成动态的

完整版希尔排序

这里的gap取值也是有讲究的

gap取得大一点跳得更快，但是排的数据有序性较差
gap取得小一点跳得更慢，但是排的数据有序性较好

学术界经过研究得出：每次gap除3是最好的，整个排序算下来的时间复杂度是O(n^1.3)

void ShellSort(int* arr, int n) { int gap = n / 3 + 1; //这里的do_while是一个小巧思，当gap==1时可以只进行一次排序,在首个gap do { //先使用再改变gap for (int j = 0; j < gap; j++) { for (int i = j; i < n - gap; i += gap) { int end = i; int temp = arr[end + gap]; while (end >= j)//这里是一个边界条件，我们应该将预排序视作是划分了一个新的组 { if (arr[end] > temp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = temp; } } gap = gap / 3 + 1; } while (gap > 1); }

选择排序

算法简介

选择排序是一种简单直观的排序算法。它的工作原理是：

在未排序序列中找到最小（或最大）元素
将其存放到排序序列的起始位置
然后，再从剩余未排序元素中继续寻找最小（或最大）元素
放到已排序序列的末尾
重复以上步骤，直到所有元素均排序完毕

代码实现

void SelectSort(int* arr, int n) { int begin = 0, end = n - 1; while (begin < end) { int max = begin, min = begin; for (int i = begin + 1; i <= end; i++) { if (arr[max] < arr[i]) { max = i; } if (arr[min] > arr[i]) { min = i; } } Swap(&arr[begin], &arr[min]); if (begin == max) max = min; Swap(&arr[end], &arr[max]); begin++; end--; } }

这里有一步需要解释一下