數據結構希爾排序c語言

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分爲內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是希爾排序算法：

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；但插入排序一般來說是低效的，因爲插入排序每次只能將數據移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成爲若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。

1. 算法步驟

選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個數 k，對序列進行 k 趟排序；

每趟排序，根據對應的增量 ti，將待排序列分割成若干長度爲 m 的子序列，分別對各子表進行直接插入排序。僅增量因子爲 1 時，整個序列作爲一個表來處理，表長度即爲整個序列的長度。

2. 動圖演示

---

代碼實現

JavaScript

實例

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //動態定義間隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

Python

實例

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

Go

實例

func shellSort(arr []int) []int {
        length := len(arr)
        gap := 1
        for gap < length/3 {
                gap = gap*3 + 1
        }
        for gap > 0 {
                for i := gap; i < length; i++ {
                        temp := arr[i]
                        j := i - gap
                        for j >= 0 && arr[j] > temp {
                                arr[j+gap] = arr[j]
                                j -= gap
                        }
                        arr[j+gap] = temp
                }
                gap = gap / 3
        }
        return arr
}

Java

實例

public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

PHP

實例

function shellSort($arr)
{
    $len = count($arr);
    $temp = 0;
    $gap = 1;
    while($gap < $len / 3) {
        $gap = $gap * 3 + 1;
    }
    for ($gap; $gap > 0; $gap = floor($gap / 3)) {
        for ($i = $gap; $i < $len; $i++) {
            $temp = $arr[$i];
            for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
                $arr[$j+$gap] = $arr[$j];
            }
            $arr[$j+$gap] = $temp;
        }
    }
    return $arr;
}

C

實例

void shell_sort(int arr[], int len) {
        int gap, i, j;
        int temp;
        for (gap = len >> 1; gap > 0; gap >>= 1)
                for (i = gap; i < len; i++) {
                        temp = arr[i];
                        for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                                arr[j + gap] = arr[j];
                        arr[j + gap] = temp;
                }
}

C++

實例

template<typename T>
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

參考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/4.shellSort.md

https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

以下是熱心網友對希爾排序算法的補充，僅供參考：

熱心網友提供的補充1：

我看這個沒把 C# 版本寫出來，我寫了一下，下面是 C# 版本：

static void ShellSort(int[] arr){    int gap = 1;    while (gap < arr.Length)    {        gap = gap * 3 + 1;    }    while (gap > 0)    {        for (int i = gap; i < arr.Length; i++)        {            int tmp = arr[i];            int j = i - gap;            while (j >= 0 && arr[j] > tmp)            {                arr[j + gap] = arr[j];                j -= gap;            }            arr[j + gap] = tmp;        }        gap /= 3;    }}

以上爲希爾排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括：

關於時間複雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序算法：冒泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k："桶"的個數

In-place：佔用常數內存，不佔用額外內存

Out-place：佔用額外內存

穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同