活动地址:CSDN21天学习挑战赛
“九层之台,起于垒土”。学习技术须脚踏实地。
插入排序是一种较基础的排序算法,原理也简单易懂,只要会玩扑克就应该能很快学会。
直接插入排序通过构建有序序列,依次扫描无序序列的每个元素,将其与有序序列比较,插入小于自身的元素后面,其余元素依次后移。
动图演示:
参考:菜鸟教程
c++实现:
template<typename T>
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时停止,这个过程中数列逐渐趋于有序,操作次数也比直接插入操作少。
动图演示:
参考:菜鸟教程
算法步骤:
c++实现:
template<typename T>
void 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;
}
}