【希尔排序】十大排序算法之希尔排序,属于不稳定的排序。
目录
一、希尔排序基本思想
二、希尔排序代码实现
2.1、希尔排序【折半缩小增量】
(1)实现代码一
(2)实现代码二
2.2、希尔排序【Sedgewick增量序列】
一、希尔排序基本思想
- 希尔排序,也叫做:【缩小增量排序】,属于直接插入排序的升级版。
- 希尔排序,属于插入类排序。
- 希尔排序,时间复杂度:【O(n*log(n))】,最好情况下,可以达到【O(n^3/2)】(需要根据增量序列决定)。
什么是稳定的排序???
稳定排序:
- 如果排序数组中,存在相同的元素,假设存在两个元素【3】。
- 为了标识两个元素【3】的先后顺序,我们假设给她命名为:【3(1)】、【3(2)】。
- 其中括号里面的表示元素3出现的先后顺序。
- 如果结果排序之后,两个元素还是保持相同的顺序,即:【3(1)、3(2)】,那么我们就称这个排序是稳定的,否则就是不稳定的排序。
希尔排序基本思想
希尔排序,最关键的在于每次缩小移动增量,将每次相差增量距离的元素进行直接插入排序,直到最后增量等于1的时候,结束最后一次插入排序,此时希尔排序完成。
希尔排序基本思路:
- 第一次:选择【n/2】作为增量,将相差【n/2】的每个元素看作是一组序列,采用直接插入排序,将各组序列排序完成。
- 第二次:选择【n/2/2】作为量,将相差【n/2/2】的每个元素看作是一组序列,采用直接插入排序,将各组序列排序完成。
- 直到最后增量等于【1】,完成最后一次直接插入排序,此时希尔排序结束。
为什么说希尔排序是不稳定的排序呢???
我们知道,直接插入排序是【稳定】的排序,并且希尔排序也是属于【插入类】排序,那为什么希尔排序属于不稳定的排序呢???
这是因为一次插入排序确实是稳定的排序,但是希尔排序需要进行多次插入排序,那么在多次插入排序里面,就有可能导致排序是不稳定的情况,下面举个栗子看看。
- 假设有待排序数组:【7,9(1),9(2),1】。
- 我们首先采用增量【d=2】,进行一次希尔排序,此时需要将数组变成:【7,1,9(2),9(1)】。
- 可以看到,我们上面的排序过程,已经将两个相同的数字【9】,改变了它们原先的先后顺序,所以希尔排序是不稳定的。
- 判断一个排序算法是不是稳定,你就看排序过程中,会不会把两个相同的数字改变出现的先后顺序,也可以找个特殊的案例试一试。
下面给出希尔排序大致过程思想。
可以从这个网站查看希尔排序的过程【数据结构和算法动态可视化 (Chinese) - VisuAlgo】。
二、希尔排序代码实现
2.1、希尔排序【折半缩小增量】
希尔排序基本思路:
- 外层循环:控制增量大小【d】,从【d = n/2】开始,每次缩小一半,直到【d = 1】为止。
- 内层循环:根据增量大小【d】,将数组中相差增量【d】的元素分为一组,对该组元素采用直接插入排序。
- 循环结束,希尔排序完成。
(1)实现代码一
public class ShellSort {
public static void shellSort(int[] nums) {
// 外层循环: 控制增量大小
for (int gap = nums.length / 2; gap >= 1; gap >>= 1) {
// 内层循环: 有多少组元素需要进行直接插入排序
for (int j = 0; j < gap; j++) {
// 这层循环: 对每一组元素进行直接插入排序
for (int k = j + gap; k < nums.length; k += gap) {
// 前一个位置
int index = k - gap;
// 比较数组前后两个元素大小, 满足条件则交换数组元素
while (index >= 0 && nums[index] > nums[index + gap]) {
int temp = nums[index];
nums[index] = nums[index + gap];
nums[index + gap] = temp;
index -= gap;
}
}
}
}
}
public static void main(String[] args) {
int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
System.out.println(Arrays.toString(nums));
shellSort(nums);
System.out.println(Arrays.toString(nums));
}
}
希尔排序基本思路:
- 外层循环:控制增量大小【d】,从【d = n/2】开始,每次缩小一半,直到【d = 1】为止。
- 内层循环:根据增量大小【d】,将数组中相差增量【d】的元素分为一组,对该组元素采用直接插入排序。
- 循环结束,希尔排序完成。
(1)实现代码一
public class ShellSort {
public static void shellSort(int[] nums) {
// 外层循环: 控制增量大小
for (int gap = nums.length / 2; gap >= 1; gap >>= 1) {
// 内层循环: 有多少组元素需要进行直接插入排序
for (int j = 0; j < gap; j++) {
// 这层循环: 对每一组元素进行直接插入排序
for (int k = j + gap; k < nums.length; k += gap) {
// 前一个位置
int index = k - gap;
// 比较数组前后两个元素大小, 满足条件则交换数组元素
while (index >= 0 && nums[index] > nums[index + gap]) {
int temp = nums[index];
nums[index] = nums[index + gap];
nums[index + gap] = temp;
index -= gap;
}
}
}
}
}
public static void main(String[] args) {
int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
System.out.println(Arrays.toString(nums));
shellSort(nums);
System.out.println(Arrays.toString(nums));
}
}
上面排序算法运行结果如下所示:
(2)实现代码二
public class ShellSort {
public static void shellSort(int[] nums) {
// 外层循环: 控制增量大小
for (int gap = nums.length / 2; gap >= 1; gap >>= 1) {
// 内层循环: 有多少组元素需要进行直接插入排序
for (int index = gap; index < nums.length; index++) {
// 保存当前元素
int temp = nums[index];
// 找到插入的位置
int pos;
for (pos = index; pos >= index && nums[pos - gap] > temp; pos -= gap) {
nums[pos] = nums[pos - gap]; // 移动数组元素,前一个元素覆盖当前元素
}
// 将当前元素插入正确位置
nums[pos] = temp;
}
}
}
public static void main(String[] args) {
int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
System.out.println(Arrays.toString(nums));
shellSort(nums);
System.out.println(Arrays.toString(nums));
}
}
2.2、希尔排序【Sedgewick增量序列】
Sedgewick增量序列:采用这个增量序列,据说平均情况下可以达到【O(N^7/6)】,最坏情况下,可以达到【O(N^4/3)】。
Sedgewick增量序列取值:【0,1,5,19,41,109,209,505,929】
public class ShellSort {
public static void shellSort(int[] nums) {
// 增量序列
int[] sedgewick = {929, 505, 209, 109, 41, 19, 5, 1, 0};
// 判断初始增量: 初始增量不能大于数组长度
int d = 0; // 增量
while (sedgewick[d] >= nums.length) {
d++;
}
// 开始希尔排序
for (int gap = sedgewick[d]; gap > 0; gap = sedgewick[++d]) {
for (int i = gap; i < nums.length; i++) {
int temp = nums[i]; // 保存当前元素
// 找到插入位置
int k;
for (k = i; k >= gap && nums[k - gap] > temp; k -= gap) {
nums[k] = nums[k - gap]; // 向后移动元素
}
// 把当前元素插入正确位置
nums[k] = temp;
}
}
}
public static void main(String[] args) {
int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
System.out.println(Arrays.toString(nums));
shellSort(nums);
System.out.println(Arrays.toString(nums));
}
}
综上,就是希尔排序相关思想,以及代码实现。
Sedgewick增量序列:采用这个增量序列,据说平均情况下可以达到【O(N^7/6)】,最坏情况下,可以达到【O(N^4/3)】。
Sedgewick增量序列取值:【0,1,5,19,41,109,209,505,929】
public class ShellSort {
public static void shellSort(int[] nums) {
// 增量序列
int[] sedgewick = {929, 505, 209, 109, 41, 19, 5, 1, 0};
// 判断初始增量: 初始增量不能大于数组长度
int d = 0; // 增量
while (sedgewick[d] >= nums.length) {
d++;
}
// 开始希尔排序
for (int gap = sedgewick[d]; gap > 0; gap = sedgewick[++d]) {
for (int i = gap; i < nums.length; i++) {
int temp = nums[i]; // 保存当前元素
// 找到插入位置
int k;
for (k = i; k >= gap && nums[k - gap] > temp; k -= gap) {
nums[k] = nums[k - gap]; // 向后移动元素
}
// 把当前元素插入正确位置
nums[k] = temp;
}
}
}
public static void main(String[] args) {
int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
System.out.println(Arrays.toString(nums));
shellSort(nums);
System.out.println(Arrays.toString(nums));
}
}
综上,就是希尔排序相关思想,以及代码实现。



