活动地址:CSDN21天学习挑战赛
“九层之台,起于垒土”。学习技术须脚踏实地。
插入排序的概念插入排序是一种较基础的排序算法,原理也简单易懂,只要会玩扑克就应该能很快学会。
1.直接插入排序直接插入排序通过构建有序序列,依次扫描无序序列的每个元素,将其与有序序列比较,插入小于自身的元素后面,其余元素依次后移。
动图演示:
参考:菜鸟教程
c++实现:
template2.希尔排序void direct_insert_sort(T* arr, int len){ for(int i = 1;i < len;i++){ T temp = arr[i]; int j = i - 1; while(j != -1 && temp < arr[j]){ arr[j + 1] = arr[j]; --j; } arr[++j] = temp; } }
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
由于插入排序具有以下两点性质:
- 插入排序在对几乎已经排好序的数据操作时,需要的元素访问与元素移位操作少。
- 直接插入排序每次只能插入一位。
所以可以先把元素分成几组,在每一组内直接插入排序。然后减少间距,形成新的分组,进行排序,直到间距为1时停止,这个过程中数列逐渐趋于有序,操作次数也比直接插入操作少。
动图演示:
参考:菜鸟教程
算法步骤:
- 选择一个序列 stride1、stride2、… 、1,其中后一个元素比前一个小。
- 序列个数 k,对序列进行 k 趟排序;
- 每趟排序,根据对应的间距,将待排序列分割成若干子序列,分别对各子表进行直接插入排序。
c++实现:
templatevoid shell_sort(T* array, int length) { int h = 1; while (h < length / 3) { h = 3 * h + 1; } while (h >= 1) { for (int i = h; i < length; i++) { for (int j = i; j >= h && array[j] < array[j - h]; j -= h) { std::swap(array[j], array[j - h]); } } h = h / 3; } }