c++怎么實現希爾排序

這篇文章主要講解了“c++怎么實現希爾排序”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“c++怎么實現希爾排序”吧！

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

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 的元素編為一個組，掃描所有組
//            for (int i = gap; i < a.length; i++) {
//                int j;
//                int temp = a[i];

                  //對距離為 gap 的元素組進行排序
//                 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);
        }
    }

}

直接插入排序和希爾排序的比較
直接插入排序是穩定的；而希爾排序是不穩定的。
直接插入排序更適合于原始記錄基本有序的集合。
希爾排序的比較次數和移動次數都要比直接插入排序少，當N越大時，效果越明顯。
在希爾排序中，增量序列gap的取法必須滿足：最后一個步長必須是 1 。
直接插入排序也適用于鏈式存儲結構；希爾排序不適用于鏈式結構。

感謝各位的閱讀，以上就是“c++怎么實現希爾排序”的內容了，經過本文的學習后，相信大家對c++怎么實現希爾排序這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！