Shell 排序
Shell 排序是一种高效的基于比较的排序算法。它被看作是冒泡排序算法的泛化,或者说是一种优化的插入排序算法。在插入排序算法中,我们将元素向前移动一个位置。但在 shell 排序的情况下,我们将元素 h
位置前移。它先对很远的元素进行排序,然后根据序列逐步缩小差距,对整个数组进行排序。使用的一些序列是:
Shell 的原始序列 | N/2,N/4,...,1 。 |
Papernov & Stasevich 增量 | 1, 3, 5, 9,... |
Hibbard 的增量 | 1, 3, 7, 15, 31, 63,... |
Knuth 的增量 | 1, 4, 13, ... , (3k – 1) / 2 |
Pratt | 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, .... |
Sedgewick 的增量 | 1, 8, 23, 77, 281, ... 4j+1+ 3-2j+ 1 。 |
Shell 排序算法
假设我们有一个未排序的数组 A[]
,包含 n
元素。我们将使用 shell 的原始序列对数组进行排序。
-
按照序列计算
gap
的值。 -
对每一个间隔等于
gap
的子数组进行如下操作。 -
用插入排序法进行排序。
-
重复上述过程,直到整个数组被排序。
Shell 排序示例
假设我们有一个数组:(9, 8, 3, 7, 5, 6, 4, 1)
。我们将使用 shell 排序算法对其进行排序,并使用 shell 的原始序列来减少间隙间隔。
- 第一次迭代
n/2
=4,位于区间 4
的元素进行比较和交换。
A[0]
> A[4]
→交换,(5,8,3,7,9,6,4,1)
。
A[1]
> A[5]
→交换,(5,6,3,7,9,8,4,1)
。
A[2]
< A[6]
。
A[3]
> A[7]
→交换,(5,6,3,1,9,8,4,7)
。
数组变成:(5,6,3,1,9,8,4,7)
。
- 第二次迭代
n/4
=2,位于区间 2
的元素进行比较和交换。
A[0]
> A[2]
→交换,(3,6,5,1,9,8,4,7)
。
A[1]
> A[3]
→交换,(3,1,5,6,9,8,4,7)
。
A[0]
< A[2]
< A[4]
。
A[1]
< A[3]
< A[5]
。
A[2]
>A[4]
和 A[4]
>A[6]
→交换,(3,1,4,6,5,8,9,7)
。
A[1]
<A[3]
<A[5]
,但 A[5]
>A[7]
→互换,(3,1,4,6,5,7,9,8)
。
数组变成:(3,1,4,6,5,7,9,8)
。
- 第三次迭代
n/8
=1 , 位于区间 1
的元素进行比较和交换。
A[0] > A[1]
→交换,(1,3,4,6,5,7,9,8)
。
A[0] ... A[2]
→排序
A[0] ... A[3]
→ 排序的。
A[0] ... A[3]
→ 排序,但 A[3] > A[4] →交换,(1,3,4,5,6,7,9,8)
。
A[0] ... A[5]
→ 排序完毕
A[0] ... A[6]
→ 排序的。
A[0] ... A[6]
→排序,但 A[6] > A[7] →交换,(1,3,4,5,6,7,8,9)
。
Shell 排序算法实现
#include<bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n)
{
for (int gap = n / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i += 1)
{
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
int main() {
int n = 8;
int arr[8] = {9, 8 ,3 ,7, 5, 6, 4, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
shellSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Shell 排序算法的复杂度
时间复杂度
- 平均情况
复杂度取决于选择的排序序列。时间复杂度为 [Big Theta]:O(nlog(n)2)。
- 最坏情况
Shell 排序的最坏情况下时间复杂度总是小于等于 O(n2)。更准确的说根据 Poonen 定理,它由Θ(nlogn)2/(log log n)2)或Θ(nlog n)2/log log n)或Θ(n(log n)2)或介于两者之间。最坏情况下的时间复杂度是 [Big O]:<= O(n2)。
- 最佳情况
最好的情况是当数组已经排序,并且每个间隔所需的比较与数组的大小相同。最佳情况下的时间复杂度为 [Big Omega]:O(nlogn)
。
空间复杂度
Shell 排序算法的空间复杂度为 O(n)
,因为除了一个临时变量外,不需要额外的内存。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn