• 排序是將一串數(shù)據(jù)按照其某個或者某些關鍵字的大小進行遞增或遞減排列的操作我，通常指的排序是升序，排序方式是原地排序
• 下面介紹下希爾排序

希爾排序

• 原理：
  • 指定一個值gap，將待排序區(qū)間分成gap個組，每個組相鄰元素的下標差值是gap。將每個組元素進行排序
  • 減小gap的值，重復進行排序直到gap等于1
  • 當gap等于1的時候，數(shù)組變成有序數(shù)組
• 實質：
  • 希爾排序是對直接插入排序的優(yōu)化
  • 當gap>1時都是進行序排序，當gap=1時，數(shù)組已接近有序
• 希爾排序是一個不穩(wěn)定的排序

實現(xiàn)方式

   public void shellSort(int[] array) {
       int gap = array.length;
       while(gap > 1) {
           insertSortGap(array, gap);
           //gap的縮小方式決定了性能提升的程度
           gap = gap / 3 + 1;
       }
       insertSortGap(array, 1);
   }

   private void insertSortGap(int[] array, int gap) {
       for(int i = 0; i < array.length; i++) {
           int tmp = array[i];
           int j = i - gap;
           for(;j > 0 && array[j] > tmp; j -= gap) {
               array[j + gap] = array[j];
           }
           array[j + gap] = tmp;
       }
   }

性能分析

• 時間復雜度
  • 最好情況：數(shù)組有序時時間復雜度是O(N)
  • 最快情況：時間復雜度是O(N^2)，很難構造出實例
  • 平均情況：時間復雜度是O(N^1.3)
• 空間復雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定

墾利網(wǎng)站建設公司創(chuàng)新互聯(lián),墾利網(wǎng)站設計制作，有大型網(wǎng)站制作公司豐富經驗。已為墾利1000多家提供企業(yè)網(wǎng)站建設服務。企業(yè)網(wǎng)站搭建\外貿網(wǎng)站制作要多少錢，請找那個售后服務好的墾利做網(wǎng)站的公司定做！

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

當前名稱：java實現(xiàn)希爾排序完整代碼-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://jinyejixie.com/article0/dseeoo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、電子商務、品牌網(wǎng)站建設、服務器托管、小程序開發(fā)、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)