希爾排序（Java）
原理：
希爾排序法又稱縮小增量法，希爾排序法的基本思想是：先選定一個整數，把待排序檔案中所有記錄分 成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取，重復上述分組和 排序的作業，當到達=1時，所有記錄在統一組內排好序，- 希爾排序是對直接插入排序的優化，
- 當gap > 1時都是預排序，目的是讓陣列更接近于有序，當gap == 1時，陣列已經接近有序的了，
這樣就會很快，這樣整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比，
性能分析：
時間復雜度：
空間復雜度：O(1)
實作：
public static void shellSort(int[] arr){
//指定 gap 序列，len/2, len/4, len/8,...,1
int gap = arr.length / 2;
while(gap >= 1){
_shellSort(arr, gap);
gap = gap / 2;
}
}
public static void _shellSort(int[] arr, int gap){
//進行分組插排，分組依據就是 gap
//gap 同時也表示分的組數
//同組的相鄰的元素，下標的插值就是 gap
//下面的代碼其實和插入排序是一樣的，尤其是把 gap 設為 1
int bound = gap;
for(; bound < arr.length; bound++){
int v = arr[bound];
int cur = bound - gap;
for(; cur >= 0; cur -= gap){
if(arr[cur] > v){
arr[cur + gap] = arr[cur];
}else{
break;
}
}
arr[cur + gap] = v;
}
}
驗證main函式
public static void main(String[] args) {
int[] arr = {1,3,2,4,3,7,8,54,3,2,12};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275557.html
標籤：其他
上一篇：C語言 | 字符陣列