java實(shí)現(xiàn)希爾排序完整代碼-創(chuàng)新互聯(lián)

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

希爾排序

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

實(shí)現(xiàn)方式

   public void shellSort(int[] array) {
       int gap = array.length;
       while(gap > 1) {
           insertSortGap(array, gap);
           //gap的縮小方式?jīng)Q定了性能提升的程度
           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;
       }
   }

性能分析

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

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

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

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

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

廣告

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