一文帶你讀懂java中的希爾排序

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)一文帶你讀懂java中的希爾排序，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

希爾排序：通過(guò)比較相距一定間隔的元素來(lái)工作；各趟比較所用的距離（增量）隨著算法的進(jìn)行而減小，直到只比較相鄰元素的最后一趟排序?yàn)橹埂Ｊ遣迦肱判虻囊环N，是針對(duì)直接插入排序算法的改進(jìn)。

算法思想：先將要排序的序列按某個(gè)增量d分成若干個(gè)子序列，對(duì)每個(gè)子序列中全部元素分別進(jìn)行直接插入排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行分組，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。注意：增量的取值——一般的初次取序列的一半為增量，以后每次減半，直到增量為1。

算法實(shí)現(xiàn)代碼如下：

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //設(shè)置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步長(zhǎng)
      for (int i = average; i < array.length; i++) { //子序列進(jìn)行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

算法分析：該算法是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開始元素很無(wú)序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以?strong>希爾排序的時(shí)間復(fù)雜度會(huì)比O(n^2)好一些，為O(n^1.5)，排序效率比插入排序高很多。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。希爾排序沒(méi)有快速排序算法快 O(N*(logN))，因此對(duì)中等大小規(guī)模的數(shù)據(jù)排序比較適用，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(N^2)復(fù)雜度的算法快得多。并且希爾排序非常容易實(shí)現(xiàn)，算法代碼短而簡(jiǎn)單。 此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時(shí)快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。

上述就是小編為大家分享的一文帶你讀懂java中的希爾排序了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。