java數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
本文實例講述了java數(shù)據(jù)結(jié)構(gòu)與算法之快速排序。分享給大家供大家參考，具體如下：
交換類排序的另一個方法，即快速排序。
快速排序：改變了冒泡排序中一次交換僅能消除一個逆序的局限性，是冒泡排序的一種改進；實現(xiàn)了一次交換可消除多個逆序。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
步驟:
1、從數(shù)列中挑出一個元素，稱為 "基準"（pivot）；
2、重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
3、遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
算法實現(xiàn)代碼如下：
package exp_sort;
public class QuickSort {
public static void Qsort(int array[], int left, int right) {
int pos;
if (left < right) {
pos = quickSort(array, left, right);
//遞歸排序
Qsort(array, left, pos - 1);
Qsort(array, pos + 1, right);
}
}
/**
* 一趟快速排序
*
* @param array
* @param left
* @param right
* @return
*/
public static int quickSort(int array[], int left, int right) {
int low, high;
int temp = array[left]; // 選擇基準記錄（樞紐元）
low = left;
high = right;
while (low < high) {
// high從右到左找小于temp的記錄
while (low < high && array[high] >= temp) {
high--;
}
// 找到小于temp的記錄則交換
if (low < high) {
array[low] = array[high];
low++;
}
// low從左到右找到大于temp的記錄
while (low < high && array[low] < temp) {
low++;
}
// 找到大于temp的記錄，則交換
if (low < high) {
array[high] = array[low];
high--;
}
}
//將游標放在當前位置，此時low=high
array[low] = temp;
return low;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
Qsort(array, 0, 7);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
}
樞紐元的選?。?/strong>
1、基本的快速排序：選取地一個元素作為樞紐元。實際中應盡量避免將第一個元素作為樞紐元（極端情況是：初始狀態(tài)是已排好序或者反序的）。
2、隨機化快排序 : 隨機的選取樞紐元。
3、平衡快排 : 三數(shù)中值分割法：樞紐元的最好選擇是數(shù)組中的中值，該中值，即左端、右端和中心位置上的三個元素的中值（推薦）。
算法分析：該算法是在實踐中最快的一種排序算法，它的平均運行時間是O(N log N)，該算法之所以快，主要是由于非常精煉和高度優(yōu)化的內(nèi)部循環(huán)。它的最壞情況的性能是O(N^2)，但是這種情況可以改變?？焖倥判蚴且环N分治的遞歸算法。該算法比歸并排序算法排序快。
1、最壞情況的分析
當樞紐元是最小元素時，此時就相當于是對整個數(shù)組進行遞歸排序，時間復雜度為：O(N^2)
2、最好情況的分析
樞紐元正好位于中間，此時是對兩個子數(shù)組進行遞歸排序，時間復雜度是：O(N log N)，這和歸并排序的分析完全相同。
3、平均情況的分析
時間復雜度是：O( N log N)
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
相關(guān)文章
在Java中，類裝載器把一個類裝入Java虛擬機中，要經(jīng)過三個步驟來完成：裝載、鏈接和初始化,網(wǎng)上關(guān)于Java中對象初始化順序的文章很多，這篇文章我們將詳細介紹Java中對象初始化順序。有需要的可以參考學習。2016-10-10
Apache?Commons?BeanUtils:?JavaBean操作方法
這篇文章主要介紹了Apache?Commons?BeanUtils:?JavaBean操作的藝術(shù),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
在SpringMVC 中，不管是編譯異常還是運行時異常，都可以最終由 SpringMVC提供的異常處理器進行統(tǒng)一處理，這樣就避免了隨時隨地捕獲處理的繁瑣性，這篇文章主要介紹了Spring?MVC的三種異常處理方式?,需要的朋友可以參考下2024-01-01
如何利用Java8 Stream API對Map按鍵或值排序
這篇文章主要給大家介紹了關(guān)于如何利用Java8 Stream API對Map按鍵或值排序的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者使用Java8具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-11-11
MyBatis緩存分為一級緩存和二級緩存一級緩存，本文給大家介紹mybatis緩存知識，非常不錯具有參考借鑒價值，感興趣的朋友一起學習吧2016-05-05
這篇文章主要給大家介紹了如何通過一個命令輕松實現(xiàn)切換Java的版本，通過本文介紹的方法，大家就可以將jdk版本之間輕松切換，需要的朋友可以參考學習，下面跟著小編一起來看看吧。2017-05-05
在springboot的啟動類中可以看到@SpringBootApplication注解，它是SpringBoot的核心注解，也是一個組合注解。其中@SpringBootConfiguration、@EnableAutoConfiguration、@ComponentScan三個注解尤為重要。今天我們就來淺析這三個注解的含義2022-08-08
這篇文章主要介紹了Hadoop 中 HBase Shell命令的詳解的相關(guān)資料,需要的朋友可以參考下2017-10-10
本文給大家介紹Mybatis傳遞多個參數(shù)進行SQL查詢的用法的相關(guān)知識，本文還給大家介紹了mybatis通過Map傳遞多個參數(shù)和JavaBean傳遞多個參數(shù)，本文介紹的非常詳細，具有參考借鑒價值，感興趣的朋友一起學習吧2016-06-06
深入淺出講解Spring框架中依賴注入與控制反轉(zhuǎn)及應用
依賴注入(Dependency?Injection)和控制反轉(zhuǎn)(Inversion?of?Control)是同一個概念。具體含義是:當某個角色(可能是一個Java實例，調(diào)用者)需要另一個角色(另一個Java實例，被調(diào)用者)的協(xié)助時，在?傳統(tǒng)的程序設計過程中，通常由調(diào)用者來創(chuàng)建被調(diào)用者的實例2022-03-03