精心整理的快速排序，并配圖加代碼，方便理解，實屬不易，但是難免不了存在紕漏，感謝大家的指正與理解！覺的寫的不錯的小伙伴兒，一鍵三連支持一下，后期會有持續(xù)更新！！抱拳了罒ω罒

1. 算法思路

1．先從數(shù)組中取出一個數(shù)（通常第一個數(shù)）作為基準數(shù)。
2．將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．對左右兩邊的子數(shù)組進行遞歸排序，直到只剩下一個元素則全部排序完成。

2. 性能

• 時間復雜度：平均情況下的時間復雜度為O(nlogn)。最好的情況是O(n)，最壞情況下時間復雜度為O(n2)。
• 空間復雜度：它是一種原地排序，只需要一個很小的棧作為輔助空間，空間復雜度為O(log2n)，所以適合在數(shù)據(jù)集比較大的時候使用。
• 穩(wěn)定性：不穩(wěn)定的算法

3. 舉例說明

??假如有一個數(shù)組，如下：

首先，我們以第一個數(shù)為基準，然后定義兩個哨兵 i 和 j ，首先哨兵 j 從后往前找比基準元素小的數(shù)的位置，然后哨兵 i 從前往后找比基準元素大的數(shù)的位置。

找到指定元素后，將兩個指定的元素互換位置。

同理繼續(xù)往后運行，直到 i 和 j 重合。

直到哨兵i和哨兵j相遇，相遇位置的元素與基準元素交換。這時相遇位置左邊的元素都比基準元素大，右邊的元素都比基準元素小。將兩邊的元素各作為一個子序列進行遞歸操作。

4. 代碼示范

public class Test{public static void main(String[] args) {int []nums = {5,9,8,7,2,4,2,3,6};quickSort(nums,0,nums.length - 1);for (int i = 0; i < nums.length; i++) {System.out.print(nums[i]+" ");}}/*** 快速排序* @param nums 待排序數(shù)組* @param low 數(shù)組的第一個元素的索引* @param high 數(shù)組的最后一個元素的索引*/public static void quickSort(int[]nums,int low,int high){//只要兩個哨兵相遇那么就退出遞歸！if(low >= high)return;//取出第一個數(shù)為基數(shù)————————————步驟1int mid = nums[low];int i = low,j = high;//i 和 j 兩個哨兵沒有相遇就一直查找while(i< j){// j哨兵往前查找，找到小于基數(shù)的位置while(i< j&& nums[j] >= mid) j--;// i哨兵往后查找，找到大于基數(shù)的位置while(i< j&& nums[i] <= mid) i++;//如果兩個哨兵沒相遇那就將兩個交換——————————步驟2和3if(i< j)swap(nums,i,j);}//跳出循環(huán)，說明i和j哨兵相遇，并且相遇的位置的值一定是小于等于基數(shù)//將相遇的位置的值跟基數(shù)交換————————————步驟4nums[low] = nums[i];nums[i] = mid;//遞歸排序左邊的子數(shù)組quickSort(nums,low,i - 1);//遞歸排序右邊的子數(shù)組quickSort(nums,i + 1,high);}//交換函數(shù)public static void swap(int[]nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

結(jié)果：

2 2 3 4 5 6 7 8 9

快速排序還有很多改進版本，如隨機選擇基數(shù)，最后一位為基數(shù)等等，區(qū)間內(nèi)數(shù)據(jù)較少時直接用另的方法排序以減小遞歸深度。

總結(jié)

以上是生活随笔為你收集整理的图解排序算法之快速排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。