Java快速排序的實(shí)現(xiàn)方法示例
前言
快速排序是一種常用的基于比較的排序算法,其時(shí)間復(fù)雜度為 O(nlogn),并且具有穩(wěn)定性和廣泛的應(yīng)用場(chǎng)景。本文將全面詳細(xì)的講解一下 Java 中快速排序算法的原理、實(shí)現(xiàn)以及時(shí)間復(fù)雜度等問(wèn)題。
一、快速排序的原理
快速排序是一種分治思想的排序算法,其基本原理可以概括為以下三步:
選取一個(gè)基準(zhǔn)元素,將待排序數(shù)組劃分為左右兩個(gè)子數(shù)組;
將比基準(zhǔn)元素小的數(shù)都移到左子數(shù)組中,將比基準(zhǔn)元素大的數(shù)都移到右子數(shù)組中;
對(duì)左右兩個(gè)子數(shù)組遞歸執(zhí)行上述操作,直到每個(gè)子數(shù)組只剩下一個(gè)元素為止。
具體來(lái)說(shuō),快速排序的過(guò)程如下:
首先選取待排序數(shù)組中一個(gè)元素作為基準(zhǔn)元素,通常選擇第一個(gè)元素或最后一個(gè)元素作為基準(zhǔn)元素。
遍歷數(shù)組,將小于基準(zhǔn)元素的元素放到左邊,大于等于基準(zhǔn)元素的元素放到右邊,此時(shí)數(shù)組被劃分成了兩個(gè)部分。
對(duì)左半部分和右半部分分別遞歸執(zhí)行上述操作,直到排序完成。
需要注意的是,在遍歷數(shù)組時(shí),一般采用雙指針?lè)▉?lái)實(shí)現(xiàn)。具體來(lái)說(shuō),我們使用一個(gè)左指針指向數(shù)組的第一個(gè)元素,用一個(gè)右指針指向數(shù)組的最后一個(gè)元素,然后從左到右依次遍歷數(shù)組中的元素,如果當(dāng)前元素小于基準(zhǔn)元素,就將它和左指針?biāo)傅脑亟粨Q,然后將左指針向右移動(dòng)一位;如果當(dāng)前元素大于等于基準(zhǔn)元素,就將它和右指針?biāo)傅脑亟粨Q,然后將右指針向左移動(dòng)一位。重復(fù)上述操作直到左指針和右指針相遇為止。
二、快速排序的實(shí)現(xiàn)
在 Java 中,我們可以使用以下代碼來(lái)實(shí)現(xiàn)快速排序算法:
public static void quickSort(int[] arr, int left, int right) { if (left < right) { // 當(dāng)數(shù)組只有一個(gè)元素時(shí)結(jié)束遞歸 int partitionIndex = partition(arr, left, right); // 對(duì)數(shù)組進(jìn)行劃分,獲取基準(zhǔn)元素位置 quickSort(arr, left, partitionIndex - 1); // 對(duì)左子數(shù)組遞歸執(zhí)行快速排序 quickSort(arr, partitionIndex + 1, right); // 對(duì)右子數(shù)組遞歸執(zhí)行快速排序 } } public static int partition(int[] arr, int left, int right) { int pivot = arr[left]; // 將數(shù)組的第一個(gè)元素設(shè)置為基準(zhǔn)元素 int i = left; // 初始化左指針 int j = right; // 初始化右指針 while (i < j) { // 當(dāng)左指針和右指針沒(méi)有相遇時(shí)循環(huán) while (i < j && arr[j] >= pivot) { // 右指針從右向左遍歷,找到第一個(gè)小于基準(zhǔn)元素的元素 j--; } if (i < j) { // 如果左指針和右指針沒(méi)有相遇,將右指針?biāo)傅脑刭x值給左指針?biāo)傅奈恢? arr[i] = arr[j]; i++; } while (i < j && arr[i] < pivot) { // 左指針從左向右遍歷,找到第一個(gè)大于等于基準(zhǔn)元素的元素 i++; } if (i < j) { // 如果左指針和右指針沒(méi)有相遇,將左指針?biāo)傅脑刭x值給右指針?biāo)傅奈恢? arr[j] = arr[i]; j--; } } arr[i] = pivot; // 將基準(zhǔn)元素放到最終位置 return i; // 返回基準(zhǔn)元素的位置 }
在上述代碼中,quickSort() 方法是快速排序算法的入口,它采用遞歸的方式對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序。partition() 方法則是用來(lái)對(duì)數(shù)組進(jìn)行劃分的,它使用雙指針?lè)▉?lái)實(shí)現(xiàn)。
具體來(lái)說(shuō),我們首先將數(shù)組的第一個(gè)元素作為基準(zhǔn)元素 pivot,然后初始化左指針 i 和右指針 j。接著,我們先讓右指針 j 從右向左遍歷數(shù)組,找到第一個(gè)小于基準(zhǔn)元素的元素,并將其賦值給左指針?biāo)傅奈恢茫蝗缓笞屪笾羔?i 從左向右遍歷數(shù)組,找到第一個(gè)大于等于基準(zhǔn)元素的元素,并將其賦值給右指針?biāo)傅奈恢?。重?fù)上述操作直到左指針和右指針相遇。
最后,將基準(zhǔn)元素 pivot 放到最終位置,即左指針?biāo)傅奈恢茫@樣就完成了對(duì)數(shù)組的一次劃分。在 partition() 方法中,返回的是基準(zhǔn)元素的位置,這個(gè)位置將用于快速排序算法的遞歸操作。
三、快速排序的時(shí)間復(fù)雜度
快速排序算法的時(shí)間復(fù)雜度主要取決于對(duì)數(shù)組進(jìn)行劃分的過(guò)程。在最壞情況下,如果每次劃分都只能規(guī)模減少 1,那么快速排序的時(shí)間復(fù)雜度為 O(n^2),這種情況發(fā)生在數(shù)組已經(jīng)排好序或基本排好序的情況下。
在平均情況下,假設(shè)每次劃分可以將數(shù)組分成大小分別為 k 和 (n-k-1) 的兩個(gè)子數(shù)組,那么快速排序的時(shí)間復(fù)雜度為 O(nlogn)。這是因?yàn)榭焖倥判蛩惴ǖ倪f歸深度為 logn,每一層的比較次數(shù)為 n,因此總體比較次數(shù)為 nlogn。
需要注意的是,快速排序算法的時(shí)間復(fù)雜度并不穩(wěn)定,因?yàn)榛鶞?zhǔn)元素的選擇對(duì)算法的效率有很大的影響。如果每次都選取最大或最小的元素作為基準(zhǔn)元素,那么算法的時(shí)間復(fù)雜度將退化到 O(n^2)。因此,在實(shí)際應(yīng)用中,我們通常會(huì)采用一些優(yōu)化技巧來(lái)提高快速排序算法的效率,如隨機(jī)選擇基準(zhǔn)元素、三數(shù)取中法等。
補(bǔ)充:快速排序的另一種實(shí)現(xiàn)
我認(rèn)為這種寫(xiě)法更容易理解
public static void QuickSort(int []arr,int low,int high) { if(low<high) { int pivotpos=partition(arr,low,high); QuickSort(arr,low,pivotpos-1); QuickSort(arr,pivotpos+1,high); } } private static int partition(int[] arr, int low, int high) { int pivot=arr[low]; while(low<high) { //起初,一定要從右邊指針開(kāi)始,因?yàn)閍rr[low]的值已經(jīng)扔給了pivot,arr[low] //想象成無(wú)數(shù)字的空位 while(low<high&&pivot<=arr[high]) { --high; } //把比pivot的小的數(shù)扔到左邊指針 //把a(bǔ)rr[high]扔到arr[low]這個(gè)空位上 //然后,high位置可以想象成無(wú)數(shù)字的空位 arr[low]=arr[high]; while(low<high&&arr[low]<=pivot) { ++low; } //把比pivot大的數(shù)扔到右邊 //把a(bǔ)rr[low]扔到arr[high]這個(gè)空位上 //然后,low位置可以想象成是無(wú)數(shù)字的空位 arr[high]=arr[low]; } //此時(shí)low==high,return high也一樣 arr[low]=pivot; return low; } }
總結(jié)
到此這篇關(guān)于Java快速排序?qū)崿F(xiàn)方法的文章就介紹到這了,更多相關(guān)Java快速排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java實(shí)現(xiàn)猜數(shù)字小游戲詳解流程
猜數(shù)字是興起于英國(guó)的益智類小游戲,起源于20世紀(jì)中期,一般由兩個(gè)人或多人玩,也可以由一個(gè)人和電腦玩。游戲規(guī)則為一方出數(shù)字,一方猜,今天我們來(lái)用Java把這個(gè)小游戲?qū)懗鰜?lái)練練手2021-10-10SpringBoot集成SpirePDF實(shí)現(xiàn)文本替換功能
SpirePDF是一個(gè)用于.NET平臺(tái)的高級(jí)PDF文檔處理庫(kù),它提供了一套完整的API,允許開(kāi)發(fā)者創(chuàng)建、編輯、轉(zhuǎn)換、合并、分割和解析PDF文件本文給大家介紹了SpringBoot集成SpirePDF實(shí)現(xiàn)文本替換功能,需要的朋友可以參考下2024-09-09關(guān)于Java Guava ImmutableMap不可變集合源碼分析
這篇文章主要介紹Java Guava不可變集合ImmutableMap的源碼分析的相關(guān)資料,需要的朋友可以參考下面具體的文章內(nèi)容2021-09-09SpringBoot集成Apache POI實(shí)現(xiàn)Excel的導(dǎo)入導(dǎo)出
Apache POI是一個(gè)流行的Java庫(kù),用于處理Microsoft Office格式文件,包括Excel文件,本文主要介紹了SpringBoot集成Apache POI實(shí)現(xiàn)Excel的導(dǎo)入導(dǎo)出,具有一定的參考價(jià)值,感興趣的可以了解一下2024-06-06MyBatis傳入?yún)?shù)的實(shí)例代碼
這篇文章主要介紹了MyBatis傳入?yún)?shù)的實(shí)例代碼的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下2016-06-06Pattern.compile函數(shù)提取字符串中指定的字符(推薦)
這篇文章主要介紹了Pattern.compile函數(shù)提取字符串中指定的字符,使用的是Java中的Pattern.compile函數(shù)來(lái)實(shí)現(xiàn)對(duì)指定字符串的截取,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-12-12SpringBoot開(kāi)發(fā)案例 分布式集群共享Session詳解
這篇文章主要介紹了SpringBoot開(kāi)發(fā)案例 分布式集群共享Session詳解,在分布式系統(tǒng)中,為了提升系統(tǒng)性能,通常會(huì)對(duì)單體項(xiàng)目進(jìn)行拆分,分解成多個(gè)基于功能的微服務(wù),可能還會(huì)對(duì)單個(gè)微服務(wù)進(jìn)行水平擴(kuò)展,保證服務(wù)高可用,需要的朋友可以參考下2019-07-07