希爾排序:
希爾排序又叫縮小增量排序，是插入排序的一種（或者說是插入排序的改進版），
演算法描述:希爾排序通過將一組資料按照一定的增量對資料進行分組,對分組后的每組資料進行插入排序，實作了相隔較遠的資料之間的排序，在不斷進行插入排序的程序中，整組資料越來越接近有序，最后增量為1時，就是一次完整的插入排序了，可能有人會問，既然都是插入排序，為什么還要特地將希爾排序分出來呢?這是因為插入排序在對一組有序程度越高的資料進行排序時效率越高,所以希爾排序的時間復雜度突破了O(n2)，而且希爾排序的時間復雜度會隨著增量取值的不同而不同，
代碼實作:（以常用的增量設定舉例）
public class ShellSort {
// 希爾排序(縮小增量排序):將整組資料按照增量分組,對每一組資料進行插入排序,使得整組資料越來越接近有序,增量為1作為結束的標志,執行最后一次插入排序后結束希爾排序
public static int[] shell(int[] arr) {
// 如果陣列是null或者陣列元素只有一個直接回傳
if (arr == null || arr.length == 1) {
return arr;
}
// 設定希爾增量
int len = arr.length / 2;
while (len > 0) {
for (int i = len; i < arr.length; i++) {
// 標記要插入的新資料
int temp = arr[i];
int j;
// j是按照希爾增量分組后i之前的資料
// 當j<0或者遇到比新元素temp小的資料時回圈結束
for (j = i - len; j >= 0 && arr[j] >= temp; j -= len) {
if (arr[j] > temp) {
arr[j + len] = arr[j];
}
}
arr[j + len] = temp;
}
len /= 2;
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[] { 1, 6, 4, 8, 3, 10 };
int[] arr1 = new int[arr.length];
arr1 = shell(arr);
for(int i=0;i<arr.length;i++) {
System.out.print(arr1[i]+" ");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/273709.html
標籤：java
上一篇：字符流、列印流、轉換流、檔案流