c++怎么實(shí)現(xiàn)希爾排序

這篇文章主要講解了“c++怎么實(shí)現(xiàn)希爾排序”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“c++怎么實(shí)現(xiàn)希爾排序”吧！

初始時(shí)，有一個(gè)大小為 10 的無(wú)序序列。
在第一趟排序中，我們不妨設(shè) gap1 = N / 2 = 5，即相隔距離為 5 的元素組成一組，可以分為 5 組。
接下來，按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序。
在第二趟排序中，我們把上次的 gap 縮小一半，即 gap2 = gap1 / 2 = 2 (取整數(shù))。這樣每相隔距離為 2 的元素組成一組，可以分為 2 組。
按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序。
在第三趟排序中，再次把 gap 縮小一半，即gap3 = gap2 / 2 = 1。 這樣相隔距離為 1 的元素組成一組，即只有一組。
按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序。此時(shí)，排序已經(jīng)結(jié)束。
需要注意一下的是，圖中有兩個(gè)相等數(shù)值的元素 5 和 5 。我們可以清楚的看到，在排序過程中，兩個(gè)元素位置交換了。
所以，希爾排序是不穩(wěn)定的算法。

package com.lifeibigdata.fight;

/**
 * Created by lifei on 16/10/24.
 */
public class ShellSort {

    static int[] shellSort(int[] a){
        int gap = a.length / 2;
        while (gap >= 1){
            // 把距離為 gap 的元素編為一個(gè)組，掃描所有組
//            for (int i = gap; i < a.length; i++) {
//                int j;
//                int temp = a[i];

                  //對(duì)距離為 gap 的元素組進(jìn)行排序
//                 for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {//TODO   j - gap
//                     a[j + gap] = a[j];//TODO i - gap + gap
//                 }
//                 a[j + gap] = temp;//TODO   j - gap + gap = j
//             }

            for (int i = gap; i < a.length; i++) {
                if (a[i] < a[i - gap]){// 2 0; 3  1;4  2;
                    int tmp = a[i];
                    a[i] = a[i - gap];
                    a[i - gap] = tmp;
                }
            }

            gap = gap /2;
        }
        return a;
    }

    public static void main(String[] args) {
        int[] a = new int[]{9  ,  1   , 2  ,  5  ,  7  ,  4  ,  8  ,  6  ,  3   , 5};
        int[] r = shellSort(a);
        for (int x:r) {
            System.out.println(x);
        }
    }

}

直接插入排序和希爾排序的比較
直接插入排序是穩(wěn)定的；而希爾排序是不穩(wěn)定的。
直接插入排序更適合于原始記錄基本有序的集合。
希爾排序的比較次數(shù)和移動(dòng)次數(shù)都要比直接插入排序少，當(dāng)N越大時(shí)，效果越明顯。
在希爾排序中，增量序列g(shù)ap的取法必須滿足：最后一個(gè)步長(zhǎng)必須是 1 。
直接插入排序也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；希爾排序不適用于鏈?zhǔn)浇Y(jié)構(gòu)。

感謝各位的閱讀，以上就是“c++怎么實(shí)現(xiàn)希爾排序”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)c++怎么實(shí)現(xiàn)希爾排序這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！