快速排序算法原理及java遞歸實(shí)現(xiàn)
快速排序 對(duì)冒泡排序的一種改進(jìn)，若初始記錄序列按關(guān)鍵字有序或基本有序，蛻化為冒泡排序。使用的是遞歸原理，在所有同數(shù)量級(jí)O(n longn) 的排序方法中，其平均性能最好。就平均時(shí)間而言，是目前被認(rèn)為最好的一種內(nèi)部排序方法
基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
三個(gè)指針: 第一個(gè)指針?lè)Q為pivotkey指針（樞軸），第二個(gè)指針和第三個(gè)指針?lè)謩e為left指針和right指針，分別指向最左邊的值和最右邊的值。left指針和right指針從兩邊同時(shí)向中間逼近，在逼近的過(guò)程中不停的與樞軸比較，將比樞軸小的元素移到低端，將比樞軸大的元素移到高端，樞軸選定后永遠(yuǎn)不變，最終在中間，前小后大。
需要兩個(gè)函數(shù)：
① 遞歸函數(shù) public static void quickSort(int[]n ,int left,int right)
② 分割函數(shù)（一趟快速排序函數(shù)） public static int partition(int[]n ,int left,int right)
JAVA源代碼（成功運(yùn)行）：
package testSortAlgorithm;
public class QuickSort {
public static void main(String[] args) {
int [] array = {49,38,65,97,76,13,27};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
/*先按照數(shù)組為數(shù)據(jù)原型寫(xiě)出算法，再寫(xiě)出擴(kuò)展性算法。數(shù)組{49,38,65,97,76,13,27}
* */
public static void quickSort(int[]n ,int left,int right){
int pivot;
if (left < right) {
//pivot作為樞軸，較之小的元素在左，較之大的元素在右
pivot = partition(n, left, right);
//對(duì)左右數(shù)組遞歸調(diào)用快速排序，直到順序完全正確
quickSort(n, left, pivot - 1);
quickSort(n, pivot + 1, right);
}
}
public static int partition(int[]n ,int left,int right){
int pivotkey = n[left];
//樞軸選定后永遠(yuǎn)不變，最終在中間，前小后大
while (left < right) {
while (left < right && n[right] >= pivotkey) --right;
//將比樞軸小的元素移到低端，此時(shí)right位相當(dāng)于空，等待低位比pivotkey大的數(shù)補(bǔ)上
n[left] = n[right];
while (left < right && n[left] <= pivotkey) ++left;
//將比樞軸大的元素移到高端，此時(shí)left位相當(dāng)于空，等待高位比pivotkey小的數(shù)補(bǔ)上
n[right] = n[left];
}
//當(dāng)left == right，完成一趟快速排序，此時(shí)left位相當(dāng)于空，等待pivotkey補(bǔ)上
n[left] = pivotkey;
return left;
}
}
相關(guān)文章
SpringBoot基礎(chǔ)教程之集成郵件服務(wù)
這篇文章主要給大家介紹了關(guān)于SpringBoot基礎(chǔ)教程之集成郵件服務(wù)的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者使用SpringBoot具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了Java API操作Hdfs詳細(xì)示例,遍歷當(dāng)前目錄下所有文件與文件夾，可以使用listStatus方法實(shí)現(xiàn)上述需求，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2023-02-02
MybatisPlusException:Failed?to?process,Error?SQL異常報(bào)錯(cuò)的解決辦法
這篇文章主要給大家介紹了關(guān)于MybatisPlusException:Failed?to?process,Error?SQL異常報(bào)錯(cuò)的解決辦法,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2023-03-03
Java list利用遍歷進(jìn)行刪除操作3種方法解析
這篇文章主要介紹了Java list利用遍歷進(jìn)行刪除操作3種方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01
什么是ThreadLocal？顧名思義它是local variable（線(xiàn)程局部變量）。它的功用非常簡(jiǎn)單，就是為每一個(gè)使用該變量的線(xiàn)程都提供一個(gè)變量值的副本，是每一個(gè)線(xiàn)程都可以獨(dú)立地改變自己的副本，而不會(huì)和其它線(xiàn)程的副本沖突。從線(xiàn)程的角度看，就好像每一個(gè)線(xiàn)程都完全擁有該變量。2016-03-03
在IDEA中創(chuàng)建父工程和子模塊module的方法步驟
這篇文章主要介紹了在IDEA中創(chuàng)建父工程和子模塊module的方法步驟，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-02-02
intellij idea設(shè)置統(tǒng)一JavaDoc模板的方法詳解
這篇文章主要介紹了intellij idea設(shè)置統(tǒng)一JavaDoc模板的方法詳解,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
Java中對(duì)象快速?gòu)?fù)制的幾種方式詳解
這篇文章主要介紹了Java中對(duì)象快速?gòu)?fù)制的幾種方式詳解,對(duì)象的克隆是指創(chuàng)建一個(gè)新的對(duì)象，且新的對(duì)象的狀態(tài)與原始對(duì)象的狀態(tài)相同,當(dāng)對(duì)克隆的新對(duì)象進(jìn)行修改時(shí)，不會(huì)影響原始對(duì)象的狀態(tài),需要的朋友可以參考下2023-08-08
本文分步驟給大家講解IDEA2021常用優(yōu)化設(shè)置技巧，非常不錯(cuò)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2021-09-09
為zookeeper配置相應(yīng)的acl權(quán)限
這篇文章主要介紹了為zookeeper配置相應(yīng)的acl權(quán)限的相關(guān)實(shí)例，具有一定參考價(jià)值，需要的朋友可以了解下。2017-09-09