912. 排序數組 - 力扣（LeetCode）

題目：

給你一個整數數組?nums，請你將該數組升序排列。

你必須在?不使用任何內置函數?的情況下解決問題，時間復雜度為?O(nlog(n))，并且空間復雜度盡可能小。

示例 1：

輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]

示例 2：

輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5]

方法：快速排序?

快速排序核心就是分而治之，在當前排序區間[L,R]選定一個元素X作為中間值，X可以是nums[L+1],nums[R-1],nums[(L+R)/2]，下面我們選擇nums[(L+R)/2]作為中間值，元素依次與X比較，小于X的元素在X左邊，大于X的元素在X右邊，并且再次遞歸排序左邊的區間以及X右邊的區間，直至整個數組完成排序。

Java實現代碼：

class Solution {public int[] sortArray(int[] nums) {int n=nums.length;quicksort(nums,0,n-1);return nums;}public void quicksort(int []nums,int l,int r){if(l==r)return;int x=nums[(l+r)/2];int i=l-1;int j=r+1;while(i<j){do i++;while(nums[i]<x);do j--;while(nums[j]>x);if(i<j){int tem=nums[i];nums[i]=nums[j];nums[j]=tem;}}quicksort(nums,l,j);quicksort(nums,j+1,r);}
}

平均時間復雜度：O（nlogn），最差時間復雜度為O（n^2），即每次取到的X都是當前區間的最大值或最小值，相當于冒泡排序了。