上查看所有课程
希尔排序是 插入排序算法 的推广版本。它首先对相距较远的元素进行排序，然后逐渐减小要排序的元素之间的间隔。
元素之间的间隔根据所使用的序列减小。希尔排序算法可以使用的一些最优序列包括：
- 希尔原始序列：
N/2 , N/4 , …, 1 - 克努思增量：
1, 4, 13, …, (3k– 1) / 2 - Sedgewick 增量：
1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1 - Hibbard 增量：
1, 3, 7, 15, 31, 63, 127, 255, 511… - Papernov & Stasevich 增量：
1, 3, 5, 9, 17, 33, 65,... - Pratt：
1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....
注意： 希尔排序的性能取决于给定输入数组所使用的序列类型。
希尔排序的工作原理
- 假设我们需要对以下数组进行排序。
初始数组 - 我们在算法中使用了希尔原始序列
(N/2, N/4, ...1) 作为间隔。
在第一个循环中，如果数组大小为N = 8，则比较间隔为N/2 = 4的元素，如果它们顺序不正确则进行交换。- 将比较第 0 个元素与第 4 个元素。
- 如果第 0 个元素大于第 4 个元素，则第 4 个元素首先存储在
temp变量中，将第 0 个元素（即较大的元素）存储在第 4 个位置，并将存储在temp中的元素存储在第 0 个位置。
重新排列 n/2 间隔的元素
此过程将继续对所有其余元素进行。
重新排列 n/2 间隔的所有元素
- 在第二个循环中，取间隔
N/4 = 8/4 = 2，再次对位于这些间隔的元素进行排序。
重新排列 n/4 间隔的元素
这时您可能会感到困惑。
数组中位于当前间隔的所有元素都会被比较。
比较第 4 个和第2个位置的元素。也比较第 2 个和第 0 个位置的元素。数组中位于当前间隔的所有元素都会被比较。 - 相同的过程将继续对其余元素进行。
重新排列 n/4 间隔的所有元素 - 最后，当间隔为
N/8 = 8/8 = 1时，对位于间隔 1 的数组元素进行排序。此时数组已完全排序。
重新排列 n/8 间隔的元素
希尔排序算法
shellSort(array, size)
for interval i <- size/2n down to 1
for each interval "i" in array
sort all the elements at interval "i"
end shellSortPython、Java 和 C/C++ 中的希尔排序代码
# Shell sort in python
def shellSort(array, n):
# Rearrange elements at each n/2, n/4, n/8, ... intervals
interval = n // 2
while interval > 0:
for i in range(interval, n):
temp = array[i]
j = i
while j >= interval and array[j - interval] > temp:
array[j] = array[j - interval]
j -= interval
array[j] = temp
interval //= 2
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)// Shell sort in Java programming
import java.util.Arrays;
// Shell sort
class ShellSort {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
void shellSort(int array[], int n) {
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Driver code
public static void main(String args[]) {
int[] data = { 9, 8, 3, 7, 5, 6, 4, 1 };
int size = data.length;
ShellSort ss = new ShellSort();
ss.shellSort(data, size);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}// Shell Sort in C programming
#include <stdio.h>
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
printf("Sorted array: \n");
printArray(data, size);
}// Shell Sort in C++ programming
#include <iostream>
using namespace std;
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
cout << "Sorted array: \n";
printArray(data, size);
}希尔排序复杂度
| 时间复杂度 | |
|---|---|
| 最佳 | O(nlog n) |
| 最坏 | O(n2) |
| 平均 | O(nlog n) |
| 空间复杂度 | O(1) |
| 稳定性 | 否 |
希尔排序是一种不稳定的排序算法，因为该算法不检查位于间隔之间的元素。
时间复杂度
- 最坏情况复杂度：小于或等于
O(n2)
希尔排序的最坏情况复杂度始终小于或等于O(n2)。
根据 Poonen 定理，希尔排序的最坏情况复杂度为Θ(Nlog N)2/(log log N)2)或Θ(Nlog N)2/log log N)或Θ(N(log N)2)或介于其间的某个值。 - 最佳情况复杂度：
O(n*log n)
当数组已排序时，每个间隔（或增量）的总比较次数等于数组的大小。 - 平均情况复杂度：
O(n*log n)
大约是O(n1.25)。
复杂度取决于所选的间隔。上述复杂度对于选择的不同增量序列而异。最佳增量序列是未知的。
空间复杂度
希尔排序的空间复杂度为 O(1)。
希尔排序的应用
当以下情况时使用希尔排序：
- 调用堆栈开销较大。
uClibc库使用此排序。 - 递归超出限制。
bzip2压缩器使用它。 - 当相近的元素相距较远时，插入排序的效果不佳。希尔排序有助于减小相近元素之间的距离。因此，需要进行的交换次数会减少。