淺析java 希爾排序(Shell)算法
先取一個小于n的整數(shù)d1作為第一個增量,把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序;然后,取第二個增量d2<d1重復上述的分組和排序,直至所取的增量dt=1(dt<dt-l<;…<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。
該方法實質(zhì)上是一種分組插入方法。
原理圖:
源代碼
package com.zc.manythread;
/**
*
* @author 偶my耶
*
*/
public class ShellSort {
public static int count = 0;
public static void shellSort(int[] data) {
// 計算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 計算出下一個h值
h = (h - 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
public static void main(String[] args) {
int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };
print(data);
shellSort(data);
print(data);
}
}
運行結(jié)果:
Shell排序是不穩(wěn)定的,它的空間開銷也是O(1),時間開銷估計在O(N3/2)~O(N7/6)之間
相關(guān)文章
Java實現(xiàn)的生成二維碼統(tǒng)計掃描次數(shù)并轉(zhuǎn)發(fā)到某個地址功能詳解
這篇文章主要介紹了Java實現(xiàn)的生成二維碼統(tǒng)計掃描次數(shù)并轉(zhuǎn)發(fā)到某個地址功能,可實現(xiàn)生成帶統(tǒng)計功能的二維碼,涉及java二維碼的生成、參數(shù)傳遞、解析等相關(guān)操作技巧,需要的朋友可以參考下2018-07-07Java子線程調(diào)用RequestContextHolder.getRequestAttributes()方法問題詳解
這篇文章主要介紹了Java子線程調(diào)用RequestContextHolder.getRequestAttributes()方法問題處理,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-09-09SpringBoot和Vue.js實現(xiàn)的前后端分離的用戶權(quán)限管理系統(tǒng)
本文主要介紹了SpringBoot和Vue.js實現(xiàn)的前后端分離的用戶權(quán)限管理系統(tǒng),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-04-04從底層源碼深入分析Spring的IoC容器的實現(xiàn)原理
IoC容器負責管理對象的生命周期和依賴關(guān)系,大大簡化了應(yīng)用程序的開發(fā)和維,我們這篇文章將會從底層源碼的角度深入分析Spring的IoC容器實現(xiàn),探索它的工作原理和關(guān)鍵組件,需要的朋友可以參考下2023-07-07