快速排序算法原理及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)文章
Java EasyExcel導(dǎo)出報(bào)內(nèi)存溢出的解決辦法
使用EasyExcel進(jìn)行大數(shù)據(jù)量導(dǎo)出時(shí)容易導(dǎo)致內(nèi)存溢出,特別是在導(dǎo)出百萬(wàn)級(jí)別的數(shù)據(jù)時(shí),你有遇到過(guò)這種情況嗎,以下是小編整理的解決該問(wèn)題的一些常見(jiàn)方法,需要的朋友可以參考下2024-10-10
本篇文章主要介紹了mybatis中的緩存問(wèn)題解析，詳細(xì)的介紹了關(guān)于mybatis的一級(jí)緩存和二級(jí)緩存，具有一定的參考價(jià)值，有興趣的可以了解一下。2017-04-04
Spring Boot學(xué)習(xí)入門(mén)之表單驗(yàn)證
表單驗(yàn)證主要是用來(lái)防范小白搞亂網(wǎng)站和一些低級(jí)的黑客技術(shù)。Spring Boot可以使用注解 @Valid 進(jìn)行表單驗(yàn)證。下面這篇文章主要給大家介紹了關(guān)于Spring Boot學(xué)習(xí)入門(mén)之表單驗(yàn)證的相關(guān)資料，需要的朋友可以參考借鑒，下面來(lái)一起看看吧。2017-09-09
詳解如何用Java實(shí)現(xiàn)對(duì)m3u8直播流抽幀
抽幀（frame extraction）是指從視頻流中提取一些特定的幀，通常是關(guān)鍵幀或者隨機(jī)幀，以供后續(xù)處理。這篇文章主要為大家介紹了如何用Java實(shí)現(xiàn)對(duì)m3u8直播流抽幀，需要的可以參考一下2023-03-03
對(duì)于Java應(yīng)用程序來(lái)說(shuō)，熱部署就是在運(yùn)行時(shí)更新Java類文件。在基于Java的應(yīng)用服務(wù)器實(shí)現(xiàn)熱部署的過(guò)程中，類裝入器扮演著重要的角色。大多數(shù)基于Java的應(yīng)用服務(wù)器，包括EJB服務(wù)器和Servlet容器，都支持熱部署。,需要的朋友可以參考下2019-06-06
一文詳細(xì)講解Java時(shí)間格式轉(zhuǎn)換
這篇文章主要介紹了Java時(shí)間格式轉(zhuǎn)換的相關(guān)資料,文中詳細(xì)介紹了SimpleDateFormat（適用于Java8之前）和java.time（適用于Java8及之后）的用法,需要的朋友可以參考下2024-12-12
springboot?vue接口測(cè)試HutoolUtil?TreeUtil處理樹(shù)形結(jié)構(gòu)
這篇文章主要介紹了springboot?vue接口測(cè)試HutoolUtil?TreeUtil處理樹(shù)形結(jié)構(gòu)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
這幾天本人了解到了MyBatis-plus,一個(gè) Mybatis 增強(qiáng)工具包.經(jīng)過(guò)一番研究,發(fā)現(xiàn)這玩意真的好用,不用寫(xiě)任何 xml ,內(nèi)置通用的 Mapper,而且完全是面向?qū)ο缶幊?文檔給的示例代碼,跟之前用過(guò)的 sequelize (Node.js 的 ORM)非常像,因此本人也嘗試了一把, 需要的朋友可以參考下2021-05-05
Java工廠模式是一種創(chuàng)建對(duì)象的設(shè)計(jì)模式，它可以在不暴露對(duì)象創(chuàng)建邏輯的情況下，將對(duì)象的創(chuàng)建委托給子類或者其他對(duì)象。本文就來(lái)深入剖析一下Java工廠模式是如何讓你的代碼更靈活、可擴(kuò)展、易維護(hù)的2023-05-05
這篇文章主要介紹了Java Integer及int裝箱拆箱對(duì)比,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09