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