作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
本文介绍一种排序算法——希尔排序,是常用的排序算法之一。以下是本篇文章正文内容,包括算法简介、算法特点、算法实现和C++示例。
希尔排序法是一种改进版的插入排序。众所周知,插入排序在排序的过程中要一个个向前比较,这样耗费了大量的时间,比如一个最小值插入到最前排,要进行n-1次比较,那如果有一种方法能让其大步伐跨越并快速到达指定位置,不就能大幅缩短排序时间了嘛,希尔排序就干了这么件事。
希尔排序也可以称为增量递减排序,核心理念就是让数值先以较大的增量快速靠近目标位置,比如共n个数值,起始增量可以设为n/2,这样一个最小值到第一个位置,第一步就跨越了数据集的一半,这比一个个往前插可快多了;随后,增量再递减为n/4,以此类推;等增量递减为1了,数据集就相当于再执行一次常规的插入排序,且这次排序本身就基本排好了,最多只需要和左右交换一下即可。
1)时间复杂度与增量的选取相关。
2)稳定性与增量选取相关。
3)只需要一个额外空间,空间复杂度很低。
4)此排序法适用于大部分数据已经排过序的情况。
代码实现逻辑:
- // 希尔排序
- vector<int> ShellSort(vector<int> data)
- {
- // 拷贝
- vector<int> result = data;
-
- // 排序过程:
- // jump表示步进量,相较插入排序而言,希尔排序可以让较小的数值以较大的步子快速接近目标位
- int size = static_cast<int>(data.size());
- int jump = size / 2;
- while (jump != 0)
- {
- // 以jump为步进量,进行插入排序
- for (int i = jump; i < size; ++i)
- {
- int temp = result[i];
- int j = i - jump;
- while (result[j] > temp && j >= 0)
- {
- result[j + jump] = result[j];
- j -= jump;
- }
- result[j + jump] = temp;
- }
- // 缩小步进量,当步进量为0时,即完成排序
- jump /= 2;
- }
-
- return result;
- }
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <string>
-
- using namespace std;
-
- // 展示当前顺序
- void Show(vector<int> data)
- {
- size_t size = data.size();
- for (size_t i = 0; i < size; ++i)
- cout << setw(4) << data[i];
- cout << endl;
- }
-
- // 希尔排序
- vector<int> ShellSort(vector<int> data)
- {
- // 拷贝
- vector<int> result = data;
-
- cout << "希尔排序:\n原始数据:\n";
- Show(result);
-
- // 排序过程:
- // jump表示步进量,相较插入排序而言,希尔排序可以让较小的数值以较大的步子快速接近目标位
- int size = static_cast<int>(data.size());
- int jump = size / 2;
- int k = 1;
- while (jump != 0)
- {
- // 以jump为步进量,进行插入排序
- for (int i = jump; i < size; ++i)
- {
- int temp = result[i];
- int j = i - jump;
- while (result[j] > temp && j >= 0)
- {
- result[j + jump] = result[j];
- j -= jump;
- }
- result[j + jump] = temp;
- }
- cout << "第" << k << "次排序结果:\n";
- Show(result);
- k++;
- // 缩小步进量,当步进量为0时,即完成排序
- jump /= 2;
- }
- cout << "排序后结果:\n";
- Show(result);
- return result;
- }
-
-
- // 主函数
- int main()
- {
- vector<int> data = { 9,11,567,0,-2,4,2 };
-
- // 希尔排序
- vector<int> result4 = ShellSort(data);
-
- system("pause");
- return 0;
- }
效果图:
综上所述,希尔排序法是个比较好用的排序法,优点是相较插入排序,它的插入速度更快,缺点就是对那些已经排序完毕的数组,也要将不同增量都遍历一遍~
如果文章帮助到你了,可以点个赞让我知道,我会很快乐~加油!