思路: 字面意義,插入是將某一元素依某種規則放入到特定集合中,因此我們需要將序列分割成為兩塊,一部分為有序集合, 另一部分為待排序集合
圖解:
為了方便理解,我們就按最最特殊的4321序列來舉例,
根據上述的思路,我們需要將序列劃分為兩部分, 為了編碼方便,我們將第一個元素假設為有序集合, 那麼我們的循環應當是從第2個元素開始的,也就是3
為避免後面操作把3覆蓋掉了, 我們選擇一個臨時變數來保存3.也就是上文的val=arr[1] ,
由於是對陣列繼進行運算, 我們同時也需要取得有序集合的最後一個元素的索引作為遊標
當遊標不越界 , 且待插入的值小於遊標指示位置時(上圖的4) , 我們將元素4後移, 遊標前移,繼續檢查集合中的其它元素是否也小於待插入的元素, 直到遊標越界
#上圖由於集合內只有一個4, 遊標前移越界了, 因此循環終止. 下一輪比較開始執行
public static void insertSort(int[]arr){
for(int i = 1 ; i < arr.length; i++){
int val = arr[i];
int valIndex = i - 1; //游标
while(valIndex >= 0 && val < arr[valIndex]){ //插入的值比游标指示的值小
arr[valIndex + 1] = arr[valIndex];
valIndex--; //游标前移
}
arr[valIndex+1] = val;
}
}
1234567891011實際運行80w個資料耗時1分4秒(非準確值,每台機器可能都不一樣)
直接插排在排序記錄較少, 關鍵字基本有序的情況下效率較高
時間複雜度:
關鍵字比較次數: KCN=(n^2)/2 總移動次數: RMN= (n^2)/2
因此時間複雜度約為O(N^2)
public static void shellSort(int[] arr){ //交换法
int tmp = 0;
for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2){
for(int i = gap ; i < arr.length ; i++){ //先遍历所有数组
for(int j = i - gap ; j >= 0 ; j -= gap){//开启插入排序
if(arr[ j ] > arr[ gap + j ]){ //可以根据升降序修改大于或小于
tmp = arr[gap + j];
arr[j+gap] = arr[j];
arr[j] = tmp;
}
}
}
System.out.println(gap);
System.out.println(Arrays.toString(arr));
}
}
12345678910111213141516這裡最難理解的應該是第三個for迴圈, j = i - gap, 表示小組內的第一個元素,即j=0,
當小組內的第一個元素大於第二個元素時(由於是邏輯上的分類,第二個元素的索引應當是第一個元素的所有值增量gap) , 交換兩者,反之j-=gap,繼續比較或跳出迴圈,
如此往復將所有小組都遍歷完之後, 縮小增量(即gap/=2) , 然後繼續上述步驟, 直到增量gap為1時, 序列排序結束
希爾排序的時間複雜度取決於增量序列的函數 , 需要具體問題具體分析,並不是一個確定的值,這也是第四點需要討論的問題
上述我們在做排序的時候增量縮減選用的時gap/=2的模型, 這並不是最優的選擇, 關於增量的選取, 屬於數學界尚未解決的一個問題
但是可以確定的是, 透過大量的實驗證明,當n->無窮大時, 時間複雜度可以減少到:
在下一點, 移位法中 , 我們也做了幾個實驗, 可以肯定的時,對於一定規模內(如800w~1億) 的計算, 希爾排序的速度遠遠超過了堆排序, 至少在筆者的電腦上是這樣的
#交換法的速度比移位法慢很多,因此更多的是使用地移位法,並且移位法相較於交換法, 更"像"插入排序
思路其實就是上述兩種排序的結合, 將分組 與插入的優點結合在一起, 效率非常高
體現的就是分治的思路,將一個較大序列切割成若干較小序列
public static void shellSort02(int[] arr){ //移位法
for(int gap = arr.length/2 ; gap > 0 ; gap /= 2){ //分组
for(int i = gap ; i < arr.length ; i++){ //遍历
int valIndex = i;
int val = arr[valIndex];
if(val < arr[valIndex-gap]){ //插入的值小于组内另一个值
while(valIndex - gap >=0 && val < arr[valIndex-gap]){ //开始插排
// 插入
arr[valIndex] = arr[valIndex-gap];
valIndex -= gap; //让valIndex = valIndex-gap (游标前移)
}
}
arr[valIndex] = val;
}
}
}
12345678910111213141516
以上是如何用Java對一億個隨機數字進行排序？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
