日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
說下希爾排序的過程？希爾排序的時間復(fù)雜度和空間復(fù)雜度又是多少？

1959年Shell發(fā)明，第一個突破 O(n^2^) 的排序算法，是簡單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠(yuǎn)的元素。

插入排序

插入排序的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入

代碼實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. function insertionSort(arr) {
    2. 
  
  
  
  
  2.     let n = arr.length;
    3. 
  
  
  
  
  3.     let preIndex, current;
    4. 
  
  
  
  
  4.     for (let i = 1; i < n; i++) {
    5. 
  
  
  
  
  5.         preIndex = i - 1;
    6. 
  
  
  
  
  6.         current = arr[i];
    7. 
  
  
  
  
  7.         while (preIndex >= 0 && arr[preIndex] > current) {
    8. 
  
  
  
  
  8.             arr[preIndex + 1] = arr[preIndex];
    9. 
  
  
  
  
  9.             preIndex--;
    10. 
  
  
  
  
  10.         }
    11. 
  
  
  
  
  11.         arr[preIndex + 1] = current;
    12. 
  
  
  
  
  12.     }
    13. 
  
  
  
  
  13.     return arr;
    14. 
  
  
  
  
  14. }
    15.

插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)這個過程，直到未排序區(qū)間中元素為空，算法結(jié)束。

復(fù)雜度分析：

  • 時間復(fù)雜度：O(n^2^)
  • 空間復(fù)雜度：O(1)

希爾排序

回顧一下上面的插入排序：

  • 第一趟插入排序后，我們得到的有效序列長度為 2
  • 第二趟插入排序后，我們得到的有效序列長度為 3
  • ...
  • 直到這個序列有序

所以，如果序列足夠亂的話，時間復(fù)雜度為 O(n^2^)

希爾排序又是如何優(yōu)化的喃?

希爾排序又叫縮小增量排序，就是把數(shù)列進(jìn)行分組(組內(nèi)不停使用插入排序)，直至從宏觀上看起來有序，最后插入排序起來就容易了(無須多次移位或交換)。

其中組的數(shù)量稱為 增量 ，顯然的是，增量是不斷遞減的(直到增量為1)

那我們有是如何進(jìn)行分組喃?

往往的： 如果一個數(shù)列有 8 個元素，我們第一趟的增量是 4 ，第二趟的增量是 2 ，第三趟的增量是 1 。如果一個數(shù)列有 18 個元素，我們第一趟的增量是 9 ，第二趟的增量是 4 ，第三趟的增量是2 ，第四趟的增量是 1

很明顯我們可以用一個序列來表示增量：n/2、(n/2)/2、...、1，每次增量都/2

例如：

 
 
 
 
    
  
  
  
  
  1. let arr = [4, 1, 5, 8, 7, 3]
    2.

排序前：

將該數(shù)組看成三組( Math.floor(arr.length/2) )，分別是：[4, 1] ， [5, 8] ， [7, 3]

第一趟排序：

對三組數(shù)據(jù)分別進(jìn)行插入排序，因此我們?nèi)齻€數(shù)組得到的結(jié)果為：[1, 4] ， [5, 8] ， [3, 7]

此時數(shù)組是這樣子的：[1, 4, 5, 8, 3, 7]

第二趟排序：

  • 增量減少了，上面增量是 3 ，此時增量應(yīng)該為 1 了，因此把 [1, 4, 5, 8, 3, 7] 看成一個數(shù)組(從宏觀上是有序的了)，對其進(jìn)行插入排序，直至有序

代碼實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. function shellSort(arr) {
    2. 
  
  
  
  
  2.     let n = arr.length;
    3. 
  
  
  
  
  3.     for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    4. 
  
  
  
  
  4.         for (let i = gap; i < n; i++) {
    5. 
  
  
  
  
  5.             let j = i;
    6. 
  
  
  
  
  6.             let current = arr[i];
    7. 
  
  
  
  
  7.             while (j - gap >= 0 && current < arr[j - gap]) {
    8. 
  
  
  
  
  8.                  arr[j] = arr[j - gap];
    9. 
  
  
  
  
  9.                  j = j - gap;
    10. 
  
  
  
  
  10.             }
    11. 
  
  
  
  
  11.             arr[j] = current;
    12. 
  
  
  
  
  12.         }
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     return arr;
    15. 
  
  
  
  
  15. }
    16.

復(fù)雜度分析：

  • 時間復(fù)雜度：O(nlogn)
  • 空間復(fù)雜度：O(1)

網(wǎng)頁名稱：說下希爾排序的過程？希爾排序的時間復(fù)雜度和空間復(fù)雜度又是多少？
網(wǎng)頁URL：http://www.5511xx.com/article/ccdddhs.html