java實現(xiàn)快速排序算法
更新時間：2015年04月09日 11:29:14 投稿：hebedich
快速排序算法是基于分治策略的另一個排序算法。其基本思想是：對輸入的子數(shù)組a[p:r]，按以下三個步驟進(jìn)行排序。 1） 分解（Divide）（2） 遞歸求解（Conquer）
（3） 合并（Merge）
1、算法概念。
快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。
2、算法思想。
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
3、實現(xiàn)思路。
①以第一個關(guān)鍵字 K 1 為控制字，將 [K 1 ,K 2 ,…,K n ] 分成兩個子區(qū)，使左區(qū)所有關(guān)鍵字小于等于 K 1 ，右區(qū)所有關(guān)鍵字大于等于 K 1 ，最后控制字居兩個子區(qū)中間的適當(dāng)位置。在子區(qū)內(nèi)數(shù)據(jù)尚處于無序狀態(tài)。
②把左區(qū)作為一個整體，用①的步驟進(jìn)行處理，右區(qū)進(jìn)行相同的處理。（即遞歸）
③重復(fù)第①、②步，直到左區(qū)處理完畢。
public static void quickSortByMid(int[] a, int low, int high) {
if (low >= high)
return;
// 分割
int pivot = a[low];// 基準(zhǔn)值
int i = low, j = high;
while (i < j) {
while (i < j && a[j] >= pivot)
--j;
a[i]=a[j];
while (i < j && a[i] <= pivot)
++i;
a[j]=a[i];
}
a[i]=pivot;
quickSortByMid(a, low, i-1);
quickSortByMid(a, i+1, high);
}
快速排序算法示意圖：
以上所述就是本文的全部內(nèi)容了，希望對大家學(xué)習(xí)java快速排序算法有所幫助。
相關(guān)文章
這篇文章主要介紹了Java框架Swagger的使用詳解,在開發(fā)期間接口會因業(yè)務(wù)的變更頻繁而變動,如果需要實時更新接口文檔,這是一個費時費力的工作,Swagger應(yīng)運而生,他可以輕松的整合進(jìn)框架并通過一系列注解生成強(qiáng)大的API文檔,需要的朋友可以參考下2023-08-08
Java中的Map接口實現(xiàn)類HashMap和LinkedHashMap詳解
這篇文章主要介紹了Java中的Map接口實現(xiàn)類HashMap和LinkedHashMap詳解,我們常會看到這樣的一種集合,IP地址與主機(jī)名,等,這種一一對應(yīng)的關(guān)系,就叫做映射,Java提供了專門的集合類用來存放這種對象關(guān)系的對象,需要的朋友可以參考下2024-01-01
Swagger是一個規(guī)范和完整的框架,用于生成、描述、調(diào)用和可視化 RESTful風(fēng)格的Web服務(wù),這篇文章主要給大家介紹了關(guān)于Spring Boot中如何使用Swagger的相關(guān)資料,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了深入理解Spring AOP，詳細(xì)的介紹了spring aop的具體實現(xiàn)與理論2017-01-01
這篇文章主要介紹了完美解決request請求流只能讀取一次的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08
Java 替換字符串右側(cè)出現(xiàn)的第一個子串方式
這篇文章主要介紹了Java 替換字符串右側(cè)出現(xiàn)的第一個子串方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
MyBatis實現(xiàn)自定義MyBatis插件的流程詳解
MyBatis的一個重要的特點就是插件機(jī)制,使得MyBatis的具備較強(qiáng)的擴(kuò)展性,我們可以根據(jù)MyBatis的插件機(jī)制實現(xiàn)自己的個性化業(yè)務(wù)需求,本文給大家介紹了MyBatis實現(xiàn)自定義MyBatis插件的流程,需要的朋友可以參考下2024-12-12
SpringBoot指標(biāo)監(jiān)控功能實現(xiàn)
這篇文章主要介紹了SpringBoot指標(biāo)監(jiān)控功能實現(xiàn),本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
這篇文章主要介紹了關(guān)于Spring啟動流程及Bean生命周期梳理，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了Springboot集成swagger實現(xiàn)方式，通過簡單的示例代碼詳細(xì)描述了實現(xiàn)過程步驟，有需要的朋友可以借鑒參考下，希望可以有所幫助2021-08-08