希尔排序
2021-02-17 12:19
标签：cto tor while 基本 希尔排序 增量排序 vector 记录 分组 概念 同直接插入排序，多段后移。也叫增量排序。 基本思想 先取一个小于n的数d1作为第一个增量，把文件的全部记录分组 所有距离为d1的倍数的记录放在同一个组中 现在各组内进行直接插入排序 然后取第二个增量d2 实现代码 性能 最好：O(n) 最坏：O(n^2) 平均：不确定 空间复杂度：O(1) 稳定性：不稳定 希尔排序 标签：cto tor while 基本 希尔排序 增量排序 vector 记录 分组 原文地址：https://www.cnblogs.com/jpzhu/p/12697014.html 1 void ShellSort(vectorint> &nums)
2 {
3 int len = nums.size();
4 int increment = len;
5 while (increment > 1)
6 {
7 increment = increment / 3 + 1;
8 for (int i = increment; i )
9 {
10 int temp = nums[i];
11 if (nums[i] //比较同组内的数据
12 {
13 int j;
14 for (j = i - increment; j >= 0 && nums[j] > temp; j = j - increment)
15 nums[j + increment] = nums[j];
16 nums[j + increment] = temp;
17 }
18 }
19 }
20 }