Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之排序算法
概述
從今天開始, 小白我將帶大家開啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.
冒泡排序
冒泡排序 (Bubble Sort) 是一種簡單的排序算法. 它重復地遍歷要排序的數(shù)列, 一次比較兩個元素, 如果他們的順序錯誤就把他們交換過來. 遍歷數(shù)列的工作是重復地進行直到?jīng)]有再需要交換, 也就是說該數(shù)列已經(jīng)排序完成. 這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢 “浮” 到數(shù)列的頂端.
冒泡排序流程:
- 通過比較相鄰的元素, 判斷兩個元素位置是否需要互換
- 進行 n-1 次比較, 結(jié)尾的元素就會是最大元素
- 重復以上冒泡過程 n 次
代碼實現(xiàn):
import java.util.Arrays; public class bubble { public static void main(String[] args) { // 創(chuàng)建數(shù)據(jù) int[] array = {426,375474,8465,453}; // 實現(xiàn)排序 System.out.println(Arrays.toString(array)); System.out.println(Arrays.toString(bubbleSort(array))); } public static int[] bubbleSort(int[] array) { // 如果數(shù)組為空, 返回 if (array.length == 0){ return array; } // 執(zhí)行冒泡過程n次, n為數(shù)組長度 for (int i = 0; i < array.length; i++) { // 冒泡過程 for (int j = 0; j < array.length - 1 - i; j++) { // 判斷j索引的元素是否比j+1索引的元素大 if (array[j+1] < array[j]) { // 交換位置 int temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } return array; } }
輸出結(jié)果:
[426, 375474, 8465, 453]
[426, 453, 8465, 375474]
插入排序
插入排序 (Insertion Sort) 是一種簡單直觀的排序算法. 它的工作原理是通過構(gòu)建有序序列, 對于未排序數(shù)據(jù), 在已排序序列中從后向前掃描,找到相應位置并插入. 插入排序在實現(xiàn)上, 在從后向前掃描過程中, 需要反復把已排序元素逐步向后挪位, 為最新元素提供插入空間.
插入排序流程:
- 從第二個元素開始, 從后往前掃描
- 逐個比較元素大小, 之道插入到合適的位置
- 重復以上步驟 n-1 次
代碼實現(xiàn):
import java.util.Arrays; public class insert { public static void main(String[] args) { // 創(chuàng)建數(shù)據(jù) int[] array = {426,375474,8465,453}; // 實現(xiàn)排序 System.out.println(Arrays.toString(array)); System.out.println(Arrays.toString(insertionSort(array))); } public static int[] insertionSort(int[] array) { // 如果數(shù)組為空, 返回 if (array.length == 0) return array; // 待排序元素 int current; // 執(zhí)行插入過程n-1次 for (int i = 0; i < array.length - 1; i++) { // 指定待排序元素 current = array[i + 1]; int preIndex = i; // 執(zhí)行插入過程, 往前一個個比對 while (preIndex >= 0 && current < array[preIndex]) { array[preIndex + 1] = array[preIndex]; preIndex--; } // 插入元素 array[preIndex + 1] = current; } return array; } }
輸出結(jié)果:
???[426, 375474, 8465, 453]
[426, 453, 8465, 375474]
歸并排序
歸并排序 (Merge Sort) 是一種建立在歸并操作上的算法, 是分治的一個經(jīng)典應用.
歸并排序流程:
- 把數(shù)組拆分成兩個 n/2 長度的子序列
- 對這兩個子序列分別采用歸并排序
- 將排序好的序列合并成最終序列
代碼實現(xiàn):
import java.util.Arrays; public class merge { public static void main(String[] args) { // 創(chuàng)建數(shù)據(jù) int[] array = {426,375474,8465,453}; // 實現(xiàn)排序 System.out.println(Arrays.toString(array)); System.out.println(Arrays.toString(mergeSort(array))); } public static int[] mergeSort(int[] array) { // 如果數(shù)組長度小于2, 返回 if (array.length < 2) { return array; } // 分治 int mid = array.length / 2; int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); return merge(mergeSort(left), mergeSort(right)); } public static int[] merge(int[] left, int[] right) { // 創(chuàng)建數(shù)組用于存放合并后的序列 int[] result = new int[left.length + right.length]; for (int index = 0, i = 0, j = 0; index < result.length; index++) { // 左序列取完 if (i >= left.length) result[index] = right[j++]; // 右序列取完 else if (j >= right.length) result[index] = left[i++]; // 左序列的第i個大于有序列的第j個 else if (left[i] > right[j]) result[index] = right[j++]; else result[index] = left[i++]; } return result; } }
輸出結(jié)果:
[426, 375474, 8465, 453]
[426, 453, 8465, 375474]
快速排序
快速排序 (Quicksort) 通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分, 其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小, 然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序, 整個排序過程可以遞歸進行, 以此達到整個數(shù)據(jù)變成有序序列.
??
快速排序流程:
- 從數(shù)組中挑出一個元素作為基準 (Pivot), 通常為第一個或者最后一個元素將比基準元素
- 小的值放到基準前面, 比基準元素大的值放到基準后面
- 遞歸進行分區(qū)操作
代碼實現(xiàn):
import java.util.Arrays; public class quick { public static void main(String[] args) { // 創(chuàng)建數(shù)據(jù) int[] array = {426, 375474, 8465, 453}; // 實現(xiàn)排序 System.out.println(Arrays.toString(array)); quickSort(array, 0, array.length - 1); System.out.println(Arrays.toString(array)); } public static void quickSort(int[] arr, int low, int high) { // 定義 int p, i, j, temp; if (low >= high) { return; } // p就是基準數(shù), 每個數(shù)組的第一個 p = arr[low]; i = low; j = high; while (i < j) { //右邊當發(fā)現(xiàn)小于p的值時停止循環(huán) while (arr[j] >= p && i < j) { j--; } //這里一定是右邊開始,上下這兩個循環(huán)不能調(diào)換(下面有解析,可以先想想) //左邊當發(fā)現(xiàn)大于p的值時停止循環(huán) while (arr[i] <= p && i < j) { i++; } temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } // 交換p和arr[i] arr[low] = arr[i]; arr[i] = p; // 分別進行快排 quickSort(arr, low, j - 1); quickSort(arr, j + 1, high); } }
輸出結(jié)果:
[426, 375474, 8465, 453]
[426, 453, 8465, 375474]
總結(jié)
算法 | 時間復雜度 | 穩(wěn)定性 | 適用場景 |
---|---|---|---|
冒泡排序 | O ( n 2 ) O(n^2) O(n2) | 穩(wěn)定 | 數(shù)組大致為從小到大 |
插入排序 | O ( n 2 ) O(n^2) O(n2) | 穩(wěn)定 | 適用于數(shù)組較小的場景 |
歸并排序 | O ( n l o g n ) O(nlogn) O(nlogn) | 穩(wěn)定 | 適用于數(shù)組較大的場景 |
快速排序 | O ( n l o g n ) O(nlogn) O(nlogn) | 不穩(wěn)定 | 適用于數(shù)組較大的場景 |
到此這篇關于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之排序算法的文章就介紹到這了,更多相關Java 排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Java數(shù)據(jù)結(jié)構(gòu)及算法實例:考拉茲猜想 Collatz Conjecture
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)及算法實例:考拉茲猜想 Collatz Conjecture,本文直接給出實現(xiàn)代碼,代碼中包含詳細注釋,需要的朋友可以參考下2015-06-06消息隊列 RabbitMQ 與 Spring 整合使用的實例代碼
本篇文章主要介紹了消息隊列 RabbitMQ 與 Spring 整合使用的實例代碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-08-08java讀寫ini文件、FileOutputStream問題
這篇文章主要介紹了java讀寫ini文件、FileOutputStream問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-04-04