java中常用排序方法有哪些詳解
一、排序方法
Java中的常用排序方法有：直接插入排序，希爾排序，冒泡排序，遞歸排序，堆排序，快速排序，選擇排序。
二、分類
穩(wěn)定性：如果在一個待排序的序列中，有多個相同的元素，經(jīng)過各種排序方法排序后，該相同元素的相對位置沒有發(fā)生改變，則稱該排序算法是穩(wěn)定的，反正，則為不穩(wěn)定。
三.排序方法介紹
1.冒泡排序
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定
基本思想：
通過重復(fù)比較相鄰元素，并在順序錯誤時交換它們，將最大（或最?。┑脑刂鸩?ldquo;冒泡”到序列的一端。重復(fù)多輪后，整個序列即變得有序。
基本步驟：
1.從第一個元素開始，依次比較相鄰的兩個元素。
2.如果它們的順序錯誤（比如前大后?。?，就交換它們。
3.這樣一輪下來，最大（或最小）元素會“浮”到最后。
4.對剩余未排序的部分重復(fù)上述步驟，直到整個序列排序完成。
特點:
1.實現(xiàn)簡單，但效率較低，不適合大規(guī)模數(shù)據(jù)的排序。
2.可以通過加標(biāo)志優(yōu)化，提前結(jié)束排序。
代碼實現(xiàn)：
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flg = true;
}
}
if(!flg) {
return;
}
}
}2.選擇排序
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
基本思想：
每一輪從待排序的元素中找到最?。ɑ蜃畲螅┰?，然后將其放到已排序部分的末尾。
基本步驟：
1.在未排序部分中找到最?。ㄗ畲螅┰兀?/p>
2.將其與未排序部分的第一個元素交換；
3.將已排序部分?jǐn)U大一個元素，重復(fù)上述過程直到全部排序完成。
特點：
1.算法思路清晰，容易實現(xiàn)，適合學(xué)習(xí)排序基礎(chǔ)；
2.無論輸入數(shù)據(jù)的初始狀態(tài)如何，時間復(fù)雜度總是 O(n2)O(n2)，在大數(shù)據(jù)集上效率較低；
3.每輪只進行一次交換，最壞情況下雖然比較多，但移動次數(shù)較少，適合數(shù)據(jù)交換成本較高的場景；
4.效率低，不適合大規(guī)模數(shù)據(jù)排序。
代碼實現(xiàn)：
private static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array,i,minIndex);
}
}3.堆排序
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
基本思想：
堆排序利用堆（特別是最大堆或最小堆）這種數(shù)據(jù)結(jié)構(gòu)，將待排序數(shù)組變成一個堆。利用堆的性質(zhì)，堆頂元素（最大值或最小值）就是整個數(shù)組中的最大值或最小值。通過不斷將堆頂元素移到數(shù)組末尾，然后調(diào)整堆，使剩余元素仍滿足堆的性質(zhì)，從而實現(xiàn)排序。
基本步驟：
1.建堆：將無序數(shù)組構(gòu)建成一個大根堆（或小根堆）；
2.交換堆頂與末尾元素：將堆頂元素（最大或最小）與數(shù)組的最后一個元素交換位置。此時，堆的元素縮小一個容量（排好序的元素在最后）；
3.調(diào)整堆：對剩余的元素重新調(diào)整為堆，保持堆性質(zhì)；
4.重復(fù)步驟2和3：直到所有元素都已經(jīng)排好序。
特點：
1.原地排序，無需額外空間，時間復(fù)雜度穩(wěn)定在 O(nlog?n)O(nlogn)，適合大數(shù)據(jù)集。
2.不穩(wěn)定排序（相等元素可能改變原始相對位置），實際常數(shù)因堆調(diào)整略大于快速排序
3.不要求穩(wěn)定性，對空間效率要求較高時。
代碼實現(xiàn)：
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length-1;
while (end > 0) {
swap(array,0,end);
siftDown(array,0, end);
end--;
}
}
private static void createHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array,int parent,int len) {
int child = 2 * parent + 1;
while (child < len) {
if(child+1 < len && array[child] < array[child+1]) {
child++;
}
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2 * parent + 1;
}else {
break;
}
}
}
private static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}4.直接插入排序
時間復(fù)雜度：最好情況O(N),最壞情況O(N^2)
穩(wěn)定性：穩(wěn)定
基本思想：
將待排序序列劃分為已排序和未排序兩部分，逐步將未排序的元素插入到已排序部分的適當(dāng)位置，直到整個序列有序。
基本步驟：
1.從第一個元素開始，認(rèn)為已排序；
2.取下一個元素，將其與已排序部分的元素從后向前比較，找到合適的位置插入；
3.將該元素插入到正確位置后，已排序部分?jǐn)U大一位；
4.重復(fù)以上步驟，直到所有元素都插入完畢。
特點：
1.簡單直觀，易于實現(xiàn)。
2.在數(shù)據(jù)基本有序時表現(xiàn)較好。
3.適合單鏈表排序，不太適合大量數(shù)據(jù)的排序。
代碼實現(xiàn)：
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j > 0; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
//array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
5.希爾排序
時間復(fù)雜度：O(N^1.3) - O(N^1.5)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
基本思想：
希爾排序通過將待排序數(shù)組的元素按一定的間隔（稱為“步長”或“增量”）進行分組，對每組內(nèi)的元素進行插入排序。隨著排序逐步進行，步長逐漸縮小，直到最后步長為1，即對整個數(shù)組進行一次插入排序，從而實現(xiàn)整體排序。
基本步驟：
1.選擇一個初始增量（如數(shù)組長度的一半）；
2.將數(shù)組元素按增量分組，對每組進行插入排序；
3.縮小增量;
4.重復(fù)上述步驟，直到增量為1；
5.最后一次插入排序完成，數(shù)組即為有序。
特點：
1.改善了簡單插入排序在大規(guī)模數(shù)組中的效率，實現(xiàn)簡單，性能優(yōu)于簡單插入排序，對部分預(yù)排序的數(shù)組效果良好。
2.在最壞情況下性能仍不如歸并排序或快速排序，關(guān)鍵在于選擇合適的增量序列。
代碼實現(xiàn)：
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
gap = gap / 2;
shell(array,gap);
}
}
public 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 {
break;
}
}
array[j+gap] = tmp;
}
}6.歸并排序
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
基本思想：
歸并排序是一種經(jīng)典的分治算法，其基本思想是將待排序的數(shù)組分成兩個子數(shù)組，分別對這兩個子數(shù)組遞歸排序，然后再將排序好的子數(shù)組合并成一個有序數(shù)組。
基本步驟：
1.分解：將數(shù)組不斷二分，直到每個子數(shù)組只有一個元素（它本身是有序的）；
2.解決：遞歸排序左邊和右邊兩個子數(shù)組；
3.合并：將兩個有序的子數(shù)組合并成一個有序數(shù)組。
特點：
適合處理大數(shù)據(jù)，尤其是鏈表或者外部存儲時表現(xiàn)優(yōu)越。
代碼實現(xiàn)：
private static void mergeSortChild(int[] array,int left,int right) {
if(left >= right) {
return;
}
int mid = (left+right)/2;
mergeSortChild(array,left,mid);
mergeSortChild(array,mid+1,right);
merge(array,left,mid,right);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right-left+1];
int k = 0;
while (left <= mid && mid+1 <= right) {
if(array[left] <= array[mid+1]) {
tmp[k++] = array[left++];
}else {
tmp[k++] = array[mid++];
}
}
while (left <= mid) {
tmp[k++] = array[left++];
}
while (mid+1 <= right) {
tmp[k++] = array[mid++];
}
for (int i = 0; i < tmp.length; i++) {
array[i+left] = tmp[i];
}
}7.快速排序
時間復(fù)雜度：最好情況：O(N*logN)，最壞情況：O(N^2)
空間復(fù)雜度：最好情況：O(logN)，最壞情況：O(N)
穩(wěn)定性：不穩(wěn)定
基本思想：
一種非常高效且常用的排序算法，由英國計算機科學(xué)家托尼·霍爾于1960年提出。它的核心思想是分治策略，通過遞歸不斷將數(shù)組劃分為更小的部分，最終實現(xiàn)排序。
基本步驟：
1.選擇一個元素作為基準(zhǔn)（常用第一個、最后一個或隨機選?。?；
2.通過劃分實現(xiàn)：將數(shù)組調(diào)整為左邊的元素都較小，右邊的較大；
3.遞歸地對左右子數(shù)組排序，直到子數(shù)組長度為1或0。
特點：
1.實現(xiàn)簡單，排序快，不占用額外空間；
2.最佳情況下表現(xiàn)不佳。
代碼實現(xiàn)：
有兩種方法實現(xiàn)快速排序：
①將區(qū)間按照基準(zhǔn)值劃分成左右兩個部分，右邊的數(shù)據(jù)與左邊比較，如果右邊數(shù)據(jù)小于左邊，則兩個數(shù)據(jù)互換位置。
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
int par = parttion(array,start,end);
quick(array,start,par-1);
quick(array,par+1,end);
}
private static int parttion(int[] array, int low, int high) {
int p = array[low];
int i = low;
while (low < high) {
while (low < high && array[high] >= p) {
high--;
}
while (low < high && array[low] <= p) {
low++;
}
swap(array, low, high);
}
swap(array,i,low);
return low;
}
private static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}②將第一個數(shù)據(jù)存放在臨時變量tmp 中，形成一個坑位，然后進行右邊與tmp進行比較小于tmp就與tmp位置交換，同理左邊也是，與tmp進行比較，最好將空出來的坑位給tmp。
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
int par = parttion(array,start,end);
quick(array,start,par-1);
quick(array,par+1,end);
}
private static int parttion(int[] array, int low, int high) {
int tmp = array[low];
while (low < high) {
while (low < high && array[high] >= tmp) {
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp) {
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}快速排序的優(yōu)化：
三數(shù)取中：在每次劃分時，從待排序數(shù)據(jù)的第一個元素、最后一個元素和中間元素中，選擇中間值（即三者的中位數(shù)）作為樞軸（基準(zhǔn)值）。
基本步驟：
1.取待排序數(shù)組的左端、右端和中間元素；
2.求這三個元素的中位數(shù)（中值）；
3.將該中值作為樞軸放置到合適位置（通常是數(shù)組的最后或特定位置），然后進行快排的劃分操作。
特點：
1.避免在已排序或接近有序的數(shù)組中表現(xiàn)差的情況（如全局排序或逆序數(shù)組），降低退化為O(n²)的可能性。
2.提高劃分的平衡性，從而縮短遞歸深度，加快排序速度。
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
int index = threeMid(array,start,end);
swap(array,start,index);
int par = parttion(array,start,end);
quick(array,start,par-1);
quick(array,par+1,end);
}
private static int threeMid(int[] array,int low, int high) {
int mid = (low+high)/2;
if(array[low] < array[high]) {
if(array[mid] < array[low]) {
return low;
}else if(array[mid] > array[high]) {
return high;
}else {
return mid;
}
}else{
if(array[mid] < array[high]) {
return high;
}else if(array[mid] > array[low]) {
return low;
}else {
return mid;
}
}
}
private static int parttion(int[] array, int low, int high) {
int tmp = array[low];
while (low < high) {
while (low < high && array[high] >= tmp) {
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp) {
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}總結(jié)
到此這篇關(guān)于java中常用排序方法有哪些的文章就介紹到這了,更多相關(guān)java常用排序方法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java比較對象大小兩種常用方法,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-10-10
Spring Cloud Gateway 攔截響應(yīng)問題分析(數(shù)據(jù)截斷問題)
這篇文章主要介紹了Spring Cloud Gateway 攔截響應(yīng)問題分析(數(shù)據(jù)截斷問題),本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-01-01
Android 單例模式 Singleton 簡單實例設(shè)計模式解析
這篇文章主要介紹了單例模式 Singleton 簡單實例設(shè)計模式解析的相關(guān)資料,需要的朋友可以參考下2016-12-12
java 用redisTemplate 的 Operations存取list集合操作
這篇文章主要介紹了java 用redisTemplate 的 Operations存取list集合操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
Spring Cloud Hystrix實現(xiàn)服務(wù)容錯的方法
Hystrix是SpringCloud中重要的熔斷保護組件,由Netflix開源,主要提供延遲和容錯管理,以保障分布式系統(tǒng)的高可用性和魯棒性,通過封裝依賴項實現(xiàn)服務(wù)間隔離,引入回退邏輯應(yīng)對依賴服務(wù)故障,有效防止系統(tǒng)崩潰和服務(wù)級聯(lián)故障2024-10-10
這篇文章主要介紹了詳細(xì)介紹Java阿里云的短信驗證碼實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
SpringBoot?web靜態(tài)資源映射實現(xiàn)步驟詳解
在springBoot中的靜態(tài)資源的映射是通過SpringMVC中的resourceHttpRequestHandler來進行實現(xiàn)的。在該請求映射器中默認(rèn)規(guī)定了，SpringBoot會將classPath或者ServletContext下的/static?（/public、/resources?或?/META-INF/resources）目錄中，存放靜態(tài)資源2022-09-09
這篇文章主要介紹了關(guān)于Java輸入流與輸出流的相關(guān)資料,包括它們的定義、作用、最基礎(chǔ)的類和方法,以及如何以其他單位進行讀取,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-05-05
若已經(jīng)安裝好了jdk（java開發(fā)工具包）,也配置了環(huán)境變量,事后卻忘了安裝路徑在哪,如何查看jdk安裝路徑？本文給大家介紹了兩種查看jdk（java開發(fā)工具包）安裝路徑的方法,需要的朋友可以參考下2023-12-12
當(dāng)你調(diào)用SimpleService類的doSomething方法時,上述的PerformanceAspect會自動攔截此調(diào)用,并且記錄該方法的執(zhí)行時間,這樣你就完成了一個針對Spring的AOP入門級案例,感興趣的朋友一起看看吧2024-02-02