做那种事免费网站,中国建设银行广西分行网站首页,免费营销,wordpress 广告插件#x1f966;前言: 希尔排序也称 “缩小增量排序”#xff0c;它也是一种插入类排序的方法,在学习希尔排序之前我们首先了解一下直接插入排序.
一: #x1f6a9;直接插入排序
1.1 #x1f31f;排序思路 直接插入排序的基本原理是将一条记录插入到已排好的有序表中#x…前言: 希尔排序也称 “缩小增量排序”它也是一种插入类排序的方法,在学习希尔排序之前我们首先了解一下直接插入排序.
一: 直接插入排序
1.1 排序思路 直接插入排序的基本原理是将一条记录插入到已排好的有序表中从而得到一个新的、记录数量增1的有序表,其思路就和我们摸扑克牌一样,每摸到一张牌按照大小把他插入到对应位置,这样等摸完全部的牌时,我们手里的牌就是有序的
⛲动态图解:
首先我们把数组的第一个元素看作有序的,将第二个元素插入到与第一个元素对应的位置,再将数组的第三个元素插入到相对于数组前两个元素对应的位置,直到最后一个元素插入到对应位置
⚡代码演示: (排升序)
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;//首先保存一下待插入的元素int tmp a[end 1];//比较的最坏情况时end0while (end 0){//若待排序元素比a[end]小,则让a[end]向后移动腾位置if (tmp a[end]){a[end 1] a[end];end--;}else{//由于本来数组就为有序数组,当不满足上述条件时,说明找到了待插入的位置break;}}//插入数据a[end 1] tmp;}
}
1.2 直接插入排序特点
直接插入排序的时间复杂度为O(N^2),若待排序表为有序的则时间复杂度为O(N)待排序表越接近有序则时间复杂度越小空间复杂度为O(1),是一个稳定的排序算法与同为时间复杂度为O(N^2)的冒泡排序相比,若待排序数组为有序的,虽然冒泡排序不需要挪动数据,但是其时间复杂度依旧为O(N^2),所以直接插入排序在特定情况下还是优于冒泡排序的
二: 希尔排序
2.1 排序思路
预排序:先将数组分组,将每个组排序,目的是让整个数组相对有序插入排序:待数组相对有序后,进行直接插入排序,这样效率比较高
⛲图解:
假设待排序数组为[9 8 7 6 5 4 3 2 1]
1.我们将他们每隔三个坐标分为一组,假设gap3 2.对三个数组分别进行直接插入排序,使数组整体相对有序 3.对数组整体进行插入排序 对于代码的理解我们一步一步来
首先我们先理解对红色的一组进行预排序
//希尔排序
void ShellSort(int* a, int n)
{int gap 3;//要注意i的范围要控制到n-gap以内,因为当end大于等于n-gap时,tmp会越界 for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
}
要对红蓝绿三组都进行排序的话,直接在外层套个循环即可,我们会发现定义gap为几最后数组就会被分割为几组
//希尔排序
void ShellSort(int* a, int n)
{int gap 3;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
上述代码是排完一组在排一组,其实也可以直接一次性把三组数据全部排好
//希尔排序
void ShellSort(int* a, int n)
{int gap 3;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
} 到了这里数组就预排好了,但是我们得思考一个问题: 由于我们排序的数组的长度都是不固定的,那直接把gap定死就是不合适的,gap越大,较大的数就能更快的排到后面,gap越小预排出来的数组就越接近有序,当gap1时就为直接插入排序,所以gap应该随n的大小而变化,并且gap最后应该为1. 对于希尔增量到底怎么取也没有一个最优的值刚开始有人认为gapgap/2,但是后来有人认为这样处理预排出来数组还是不够有序,后来又提出了gapgap/31 , (1)是为了确保gap最终能变为1 希尔排序完整代码:
void ShellSort(int* a, int n)
{//首先将gap定为nint gap n;/*while (gap 1){gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){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;}}}*/while (gap 1){gap gap / 3 1;for (int 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;}}
}
2.2 希尔排序特点
希尔排序其实是对直接插入排序的优化,其效率更高当gap1时,为预排序目的是让数组相对有序,当gap1时,为直接插入排序,目的是让数组有序希尔排序的时间复杂度不容易计算,但是有专业人士算出希尔排序的时间按复杂度大概为O(N^1.3)
