java排序算法圖文詳解
基本思想：
將一個記錄插入到已排序的有序表中，使插入后的表仍然有序
對初始關鍵字{49 38 65 97 76 13 27 49}進行直接插入排序
package Sort;//插入排序public class InsertSort { public static void main(String[] args) {int [] arr={49,38,65,97,76,13,27,49};sort(arr); print(arr); } private static void sort(int [] arr) {for (int i = 1; i < arr.length; i++) { for(int j=i;j>0;j--){ if(arr[j]<arr[j-1]){ swap(arr,j,j-1); } }} } private static void swap(int [] arr,int i,int j){int temp=0;temp=arr[i];arr[i]=arr[j];arr[j]=temp; } private static void print(int [] arr) {for (int i = 0; i <arr.length ; i++) { System.out.print(arr[i]+' ');} }}
13 27 38 49 49 65 76 97
Process finished with exit code 0
二、 希爾排序希爾排序又稱“縮小增量排序”（Diminishing Increment Sort)）屬于插入排序類。
基本思想：
先將整個待排序的記錄分割成若干子序列分別進行“直接插入排序”，待整個序列中的記錄”基本有序“時，再對全體記錄進行一次直接插入排序。
package Sort;//希爾排序是插入排序的改良public class ShellSort { public static void main(String[] args) {int [] arr={16,25,12,30,47,11,23,36,9,18,31};sort(arr);print(arr); } private static void sort(int [] arr) {//gap設置優化int h=1;while(h<arr.length/3){ h=h*3+1;} for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希爾排序的間距 for (int i = gap; i < arr.length; i++) { for (int j = i; j >gap-1; j-=gap) { if (arr[j] < arr[j - gap]) { swap(arr, j, j - gap); } } } } } private static void swap(int [] arr,int i,int j){int temp=0;temp=arr[i];arr[i]=arr[j];arr[j]=temp; } private static void print(int [] arr) {for (int i = 0; i <arr.length ; i++) { System.out.print(arr[i]+' ');} }}
9 11 12 16 18 23 25 30 31 36 47
Process finished with exit code 0
三、冒泡排序冒泡排序
四、快速排序對冒泡排序的一種改進
基本思想：
通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續分別進行排序，以達到整個序列有序。
package Sort;import java.util.Arrays;//快速排序public class QuickSort { public static void main(String[] args) {int[] arr={49,38,65,97,76,13,27,49};sort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr)); } private static void sort(int [] arr,int start,int end) { if(start<end){ //把數組的第0個數作為標準數 int stared=arr[start]; //記錄要排序的下標 int low=start; int height=end; //循環找出比標準數大和比標準數小的數 while(low<height){ //右邊數字比標準數大 while(low<height&&stared<=arr[height]){ height--; } //用右邊的數字替換左邊的數字 arr[low]=arr[height]; //左邊數字比標準數小 while(low<height&&stared>=arr[low]){ low++; } //用左邊的數字替換右邊的數字 arr[height]=arr[low]; } arr[low]=stared; sort(arr,start,low); sort(arr,low+1,height); } } }
[13, 27, 38, 49, 76, 97, 65, 49]
Process finished with exit code 0
五、選擇排序(Selection Sort)選擇排序
六、堆排序堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩定排序。
堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆, 注意 : 沒有要求結點的左孩子的值和右孩子的值的大小關系。
每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆
1、大頂堆舉例說明：
我們對堆中的結點按層進行編號，映射到數組中就是下面這個樣子:
大頂堆特點：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 對應第幾個節點，i從0開始編號
2、小頂堆舉例說明
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 對應第幾個節點，i從0開始編號
一般升序采用大頂堆，降序采用小頂堆
堆排序基本思想
一、堆排序的基本思想是：將待排序序列構造成一個大頂堆
此時，整個序列的最大值就是堆頂的根節點。
將其與末尾元素進行交換，此時末尾就為最大值。
然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列了。
二、代碼示例package Sort;import java.util.Arrays;/**構造大頂堆 * 1、原順序二叉樹 非葉子節點在數組中的索引i=1時；arr[i]=6 i=0時 * 4 i的右節點值比它大，交換得 ： 9 * / 4 / * 6 8 / 6 8 * / 9 8 / * 5 9/ 5 4 * 5 6 */public class HeapSort { public static void main(String[] args) {int [] arr={4,6,8,5,9};heapSort(arr); } //編寫一個堆排序的方法 public static void heapSort(int[] arr){int temp=0;for(int i=arr.length/2-1;i>=0;i--){ adjustHeap(arr,i,arr.length);}//將堆頂元素與末尾元素進行交換，此時末尾就為最大值，將最大值全放在數組最后//重新調整結構，使其滿足堆定義，繼續交換堆頂元素與當前末尾元素，反復執行調整交換步驟，使整個序列達到有序for(int j=arr.length-1;j>0;j--) { //交換 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j);}System.out.println('數組'+Arrays.toString(arr)); } //將數組調整為一個大頂堆 /** * 功能：完成將以i對應的非葉子節點的樹調整成大頂堆 * 舉例：int[]arr={4,6,8,5,9};=>i=1=>adjustHeap=>得到{4，9，8，5，6} * 如果再次調整adjustHeap傳入i=0,{4，9，8，5，6}=>得到{9，6，8，5，4} * @param arr 表示要調整的數組 * @param i 表示非葉子節點在數組中的索引 * @param length 表示對多少個元素進行調整，length在逐漸減少 */ public static void adjustHeap(int[]arr,int i,int length){ int temp=arr[i];//先取出當前元素的值，保存在臨時變量中//開始調整//k=i*2+1;k是i節點的左子節點for(int k=i*2+1;k<length;k=k*2+1){ if(k+1<length&&arr[k]<arr[k+1]){//說明左子節點的值小于右子節點的值 k++;//k指向右子節點 } if(arr[k]>temp){//如果子節點大于父節點 arr[i]=arr[k];//把較大的值賦給當前節點 i=k;//!!!i指向k，繼續循環比較 }else{ break; }}//當for循環結束后，已經將以i為父結點的最大值放在了堆頂上（局部） arr[i]=temp;//將temp的值放在調整后的位置 }}
堆排序結果：
數組[4, 5, 6, 8, 9]
七、歸并排序定義：
又一類不同的排序方法，將兩個或兩個以上的有序表合并成一個新的有序表。
需要輔助空間：O(n)
整個歸并需要 [log2n] 趟
時間復雜度：O(nlog2n)
缺點：歸并排序占用附加存儲較多, 需要另外一個與原待排序對象數組同樣大小的輔助數組。
優點：歸并排序是一個穩定的排序方法
思路可以推廣到“多路歸并”
常用于外部排序
package Sort;//歸并排序public class MergeSort { public static void main(String[] args) {int [] arr={4,5,7,8,1,2,3,6};sort(arr);print(arr); } private static void sort(int [] arr) {int mid=arr.length/2;int[]temp=new int[arr.length];int i=0;//標記左邊數組int j=mid+1;//標記右邊數組起始點int k=0;while(i<=mid&&j<arr.length){ if(arr[i]<=arr[j]){ temp[k]=arr[i]; i++; k++; }else{temp[k]=arr[j];j++;k++; }}while(i<=mid){temp[k++]=arr[i++];}//將左邊剩余的，復制到數組while(j<arr.length){temp[k++]=arr[j++];}//將右邊剩余的，復制到數組 } private static void print(int [] arr) {for (int i = 0; i <arr.length ; i++) { System.out.print(arr[i]+' ');} }}
1 2 3 4 5 6 7 8
Process finished with exit code 0
總結本篇文章就到這里了，希望可以給你帶來一些幫助，也希望您能夠多多關注好吧啦網的更多內容！
相關文章：
網公網安備