希爾排序（Shell Sort），是由Donald Shell在1959年提出的一種排序算法。它是插入排序的一種高效改進版，通過引入“增量”概念，將原本的線性查找轉換為分段查找，從而顯著提升了排序效率。本文將深入探討希爾排序的原理、步驟及其實現代碼。點贊加關注謝謝😜
希爾排序的基本原理? ? ? ? 源代碼在文章最后
希爾排序的核心在于它使用了不同的增量序列來分組元素，然后再對各組進行插入排序。初始時，增量較大，使得元素之間的距離遠大于1，這樣就可以對相隔較遠的元素進行排序，之后逐步減小增量，直到最后增量為1，此時算法退化為普通的插入排序。
算法步驟
1. 選擇增量：首先選擇一個增量序列t1, t2, ..., tk，其中ti > tj, tk = 1。
2. 分組并排序：按照增量ti，將所有元素分為ti個子序列，對每個子序列進行插入排序。
3. 減小增量：重復步驟2，但每次使用增量序列中的下一個值，直至增量為1。
4. 最終排序：當增量為1時，執行一次插入排序，完成整個排序過程。
C語言代碼實現
下面是一個使用希爾排序對整型數組進行排序的C語言代碼示例：
#include <stdio.h>
void shellSort(int arr[], int n) {
? ? int gap, i, j, temp;
? ? // 動態生成增量序列
? ? for (gap = n / 2; gap > 0; gap /= 2) {
? ? ? ? // 對每一個子序列進行插入排序
? ? ? ? for (i = gap; i < n; i++) {
? ? ? ? ? ? temp = arr[i];
? ? ? ? ? ? j = i;
? ? ? ? ? ? // 插入排序
? ? ? ? ? ? while (j >= gap && arr[j - gap] > temp) {
? ? ? ? ? ? ? ? arr[j] = arr[j - gap];
? ? ? ? ? ? ? ? j -= gap;
? ? ? ? ? ? }
? ? ? ? ? ? arr[j] = temp;
? ? ? ? }
? ? }
}
?
int main() {
? ? int arr[] = {64, 34, 25, 12, 22, 11, 90};
? ? int n = sizeof(arr)/sizeof(arr[0]);
?
? ? printf("Original array:\n");
? ? for (int i = 0; i < n; i++) {
? ? ? ? printf("%d ", arr[i]);
? ? }
? ? printf("\n");
?
? ? shellSort(arr, n);
?
? ? printf("Sorted array:\n");
? ? for (int i = 0; i < n; i++) {
? ? ? ? printf("%d ", arr[i]);
? ? }
? ? printf("\n");
?
? ? return 0;
}
總結
希爾排序通過引入增量序列，巧妙地提升了插入排序的效率。雖然其最壞情況下的時間復雜度仍為O(n^2)，但在實踐中，通過合理選擇增量序列，希爾排序通常能展現出接近O(n log n)的平均性能，使其成為處理大量數據時的一個實用選項。
)
)
