快捷導航

C++實現(xiàn)希爾排序算法實例

更新時間：2022年01月07日 17:29:28 作者：恒天1020

大家好，本篇文章主要講的是C++實現(xiàn)希爾排序算法實例，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

1.代碼模板

// 希爾排序（Shell Sort）
void ShellSort(SqList *L)
{
    int i, j;
    int increment = L->length;  // 先讓增量初始化為序列的長度
    do {
        increment = increment / 3 + 1;   // 計算增量的值
        for (i = increment + 1; i <= L->length; i ++ ) { 
            if (L->arr[i] < L->arr[i - increment]) {   // 如果L->[i]需要插入有序增量子表
                L->arr[0] = L->arr[i];   // 暫存在哨兵位
                for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment) {  // 遍歷增量子表，尋找插入位置
                    L->arr[j + increment] = L->arr[j];
                }
                L->arr[j+increment] = L->arr[0];  // 插入
            }
        }
    } while (increment > 1);
}

2.算法介紹

希爾排序，又叫縮小增量排序，算法屬于插入類排序的進階算法，采取跳躍分割的策略，將關(guān)鍵字較小的元素跳躍式的往前挪，大大減小了交換比較的次數(shù)。使得序列整體基本有序 ，即大的元素基本在后面，小的元素基本在前面，不大不小的元素基本在中間。

希爾排序的關(guān)鍵在于將序列中相隔某個“增量”的元素組成一個子序列，且序列的最后一個增量必須為1，這樣才能保證最后的結(jié)果是有序且正確的。但增量如何選擇為最佳，至今仍無定論。且由于元素是跳躍式移動的，所有希爾排序是一個不穩(wěn)定的排序算法，其時間復雜度受到增量選擇的影響，最好為O(n^1.3) , 最壞為O(n*n)。

3.實例

#include <iostream>
using namespace std;

const int N = 100;

typedef struct
{
    int arr[N];    // 存儲待排序的序列
    int length;    // 存儲序列的長度
} SqList;

void ShellSort(SqList *L)
{
    int i, j;
    int increment = L->length;
    do {
        increment = increment / 3 + 1;
        for (i = increment + 1; i <= L->length; i ++ ) {
            if (L->arr[i] < L->arr[i - increment]) {
                L->arr[0] = L->arr[i];
                for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment)
                    L->arr[j + increment] = L->arr[j];
                L->arr[j + increment] = L->arr[0];
            }
        }
    } while (increment > 1);
}

int main()
{
    SqList L;
    L.arr[1] = 50;
    L.arr[2] = 10;
    L.arr[3] = 90;
    L.arr[4] = 30;
    L.arr[5] = 70;
    L.arr[6] = 40;
    L.arr[7] = 80;
    L.arr[8] = 60;
    L.arr[9] = 20;
    L.length = 9;

    ShellSort(&L);
    for (int i = 1; i <= L.length; i ++ )
        cout << L.arr[i] << " ";

}

到此這篇關(guān)于C++實現(xiàn)希爾排序算法實例的文章就介紹到這了,更多相關(guān)C++希爾排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: