Shell 排序算法 · Programiz 中文系列教程

# Shell 排序算法 > 原文： [https://www.programiz.com/dsa/shell-sort](https://www.programiz.com/dsa/shell-sort) #### 在本教程中，您將學習 shell 排序的工作方式。此外，您還將找到使用 C，C++ ，Java 和 Python 進行 shell 排序的工作示例。 Shell 排序是一種算法，該算法首先對彼此分開的元素進行排序，然后依次減小要排序的元素之間的間隔。它是插入排序的通用版本。在 Shell 排序中，將按特定間隔對元素進行排序。元素之間的間隔根據使用的順序逐漸減小。 shell 排序的性能取決于給定輸入數組使用的序列類型。使用的一些最佳順序是： * Shell 的原始順序：`N/2 , N/4 , …, 1` * Knuth 的增量：`1, 4, 13, …, (3k – 1) / 2` * Sedgewick 的增量：`1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1` * 希伯德的增幅：`1, 3, 7, 15, 31, 63, 127, 255, 511…` * Papernov & Stasevich 增量：`1, 3, 5, 9, 17, 33, 65,...` * 普拉特：`1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....` * * * ## Shell 排序如何工作？ 1. 假設我們需要對以下數組進行排序。 ![Shell sort step](https://img.kancloud.cn/e3/98/e398462e412775c997b9aefcd3b60a03_1144x196.png "Input Array") 初始數組 2. 我們在算法中使用了外殼的原始序列`(N/2, N/4, ...1)`作為間隔。在第一個循環中，如果數組大小為`N = 8`，則比較`N/2 = 4`間隔的元素，如果順序不對則交換它們。 1. 將第 0 個元素與第 4 個元素進行比較。 2. 如果第 0 個元素大于第 4 個，則首先將第 4 個元素存儲在`temp`變量中，并將第 0 個元素（即更大的元素）存儲在第 4 個位置和存儲在`temp`中的元素存儲在第 0 個位置。 ![Shell Sort step](https://img.kancloud.cn/4b/d2/4bd2cda893dd7205ee72482404f2f09d_1292x590.png "First loop of Shell Sort") 以`n / 2`的間隔重新排列元素。對于所有其余元素，此過程將繼續進行。 ![Shell Sort steps](https://img.kancloud.cn/af/e7/afe72c16b6387de076ea85b5d1344df7_1144x640.png "First loop of Shell Sort") 以`n / 2`間隔重新排列所有元素 3. 在第二個循環中，采用`N/4 = 8/4 = 2`的間隔，并再次對位于這些間隔的元素進行排序。 ![Shell Sort step](https://img.kancloud.cn/56/0a/560a2eb25afcc7ce37a338b5be63caaf_1144x344.png "Second Loop") 以`n / 4`的間隔重新排列元素此時，您可能會感到困惑。 ![Shell Sort step](https://img.kancloud.cn/b8/bd/b8bda0263b0ffe4530afb29b2c8a4810_1144x344.png "Shell Sort steps") 比較當前間隔中數組中的所有元素。比較第 4 個和第 2 個位置的元素。還比較了第 2 個和第 0 個位置的元素。比較當前間隔中數組中的所有元素。 4. 其余元素的處理相同。 ![Shell Sort step](https://img.kancloud.cn/a1/5e/a15ed93c1bcd75f54210950f1a2c932b_1144x640.png "Shell Sort steps") 以`n / 4`間隔重新排列所有元素 5. 最后，當間隔為`N/8 = 8/8 =1`時，將對間隔為 1 的數組元素進行排序。數組現在已完全排序。 ![Shell Sort step](https://img.kancloud.cn/af/1b/af1b6173bcee603f0a4c6f03b95d999a_1144x1380.png "Shell Sort steps") 以`n / 8`間隔重新排列元素 * * * ## Shell 排序算法 ``` 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 shellSort ``` * * * ## Python，Java 和 C/C++ 示例 ```py # 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) ``` ```java // 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)); } } ``` ```c // 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); } ``` ```cpp // 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); } ``` * * * ## 復雜度 Shell 排序是一種不穩定的排序算法，因為該算法不會檢查間隔之間的元素。 ### 時間復雜度 * **最壞情況復雜度**：小于或等于`O(n^2)` 外Shell 排序的最壞情況復雜度始終小于或等于`O(n^2)`。根據 Poonen 定理，Shell 排序的最壞情況復雜度是`Θ(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(n^1.25)`附近。復雜程度取決于選擇的間隔。對于選擇的不同增量序列，上述復雜度有所不同。最佳遞增順序未知。 ### 空間復雜度：外Shell 排序的空間復雜度為`O(1)`。 * * * ## Shell 排序應用在以下情況下使用 Shell 排序： * 調用棧是開銷。 uClibc 庫使用這種排序。 * 遞歸超出限制。 bzip2 壓縮器使用它。 * 當接近的元素相距很遠時，插入排序的效果不佳。 Shell 排序有助于縮短封閉元素之間的距離。因此，將執行的交換次數將更少。