柚子快報邀請碼778899分享：算法 Java：插入排序
柚子快報邀請碼778899分享：算法 Java：插入排序
目錄
排序的概念
插入排序
直接插入排序
哈希排序
排序的概念
排序：所謂的排序，就是使一串記錄，按照某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn) 定的；否則稱為不穩(wěn)定的。
?常見的排序算法有下面四種：
插入排序：直接插入排序，希爾排序選擇排序：選擇排序，堆排序交換排序：冒泡排序，快速排序歸并排序：歸并排序
這里主要介紹Java如何實現(xiàn)插入排序中的直接排序和希爾排序。
插入排序
基本思想：把待排序的記錄按照其關鍵碼值的大小逐個插入到一個已經(jīng)拍好的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。生活中的例子，就像我們在完撲克牌的時候機型排序一樣。
直接插入排序
思路：
直接插入排序的過程就像是有一組無序數(shù)據(jù)，用第二個元素先和第一個元素比較，如果第一個元素比第二個元素大，那么二者就交換位置，否則繼續(xù)往后推，隨著往后推，每一次前一個元素都要不斷和之前排序過的元素進行比較。
?Sort類
public class Sort {
/**
* 時間復雜度：O(N^2)
* 空間復雜度：O(1)
* 穩(wěn)定性：穩(wěn)定的排序
* @param array
*/
//直接插入排序
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i-1;
for (; j >= 0; j--) {
if(arr[j] > tmp){
arr[j+1] = arr[j];
}else{
arr[j+1] = tmp;
break;
}
}
//確保j位置的數(shù)，也就是前一個數(shù)能換位成功
arr[j+1] = tmp;
}
}
}
Test類 測試類
public class Test {
public static void main(String[] args) {
int[] arr = {12,6,59,45,73,26,2};
System.out.println("排序前：" + Arrays.toString(arr));
Sort.insertSort(arr);
System.out.println("排序前：" + Arrays.toString(arr));
}
}
輸出結果為：
?關于i=1，且i < arr.length思路，因為數(shù)組是從0開始的，所以arr[6]的位置剛好是最后一位。
通過上面的動圖我們不難發(fā)現(xiàn)，如果數(shù)組一開始越有序，直接插入排序的效率越高，這也為下面的哈希排序提供了思路。
穩(wěn)定性
直接插入排序是穩(wěn)定的，由上面圖片能看到它是具有穩(wěn)定性的，但如果是代碼部分的 arr[j] > tmp 改為：arr[j] >=? tmp，以上面的2a和2b為例，它們的順序就會發(fā)生變化。那么這還能說直接插入排序是穩(wěn)定的嗎？
當然能，因為 本身是一個穩(wěn)定的排序，那么可以實現(xiàn)為不穩(wěn)定的。
但是，如果一個排序 本身是不穩(wěn)定的，那就不能實現(xiàn)穩(wěn)定的排序。
哈希排序
哈希排序可以看作是直接插入排序的優(yōu)化，先通過 gap來不斷簡化 其中的有序性，然后再用直接插入排序，越有序，直接插入排序的時間復雜度越小，速度越快。
通過間隔分為不同的組，組內(nèi)進行排序，然后再縮短gap來進行再次排序。
代碼為
public static void shellInsert(int[] array){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array, gap);
}
}
private static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0; j-= gap) {
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
array[j+gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}
到這里，插入排序中的直接插入排序和希爾排序就結束了，接下來我會繼續(xù)給出剩下排序的思路和代碼。
柚子快報邀請碼778899分享：算法 Java：插入排序
文章鏈接
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權，聯(lián)系刪除。
Lowes優(yōu)選出海棧
