1.快速排序的基本思想——分治

q：無(wú)序數(shù)組
l：左端點(diǎn)
r：右端點(diǎn)
（1）確定分界點(diǎn)x
常用取法可為q[ l ]，q[ (l + r) / 2 ]，q[ r ]， 隨機(jī)取等
（2）調(diào)整區(qū)間
使區(qū)間左邊的數(shù)均小于等于x，區(qū)間右邊的數(shù)均大于等于x
（3）遞歸處理左右兩段區(qū)間

2.暴力解法

（1）開辟兩個(gè)新空間
a[ ]，b[ ]
（2）遍歷q[ l - r ]
q[ i ] <= x 存儲(chǔ)到a[ ]
q[ i ] >= x 存儲(chǔ)到b[ ]
（3）將ab兩個(gè)數(shù)組合并為新數(shù)組
a[ ] → q[ ]
b[ ] → q[ ]

3.優(yōu)美解法

（1）當(dāng)i指向的數(shù)比x小時(shí)，i向右移，直到找到一個(gè)比x大的數(shù)
（2）當(dāng)j指向的數(shù)比x大時(shí)，j向左移，直到找到一個(gè)比x小的數(shù)
（3）交換i、j位置的數(shù)，兩個(gè)指針往前移動(dòng)一位
（4）直至i、j相遇

4.快速排序Python代碼實(shí)現(xiàn)

輸入樣例：

5
3 1 2 4 5

輸出樣例：

1 2 3 4 5

Python3：

def quick_sort(nums, l, r):
    if r <= l:
        return
    x = nums[(l + r) // 2]
    i, j = l - 1, r + 1
    while i < j:
        i += 1
        while nums[i] < x:  # 這里用小于號(hào)
            i += 1
        j -= 1
        while nums[j] > x: # 這里用大于號(hào)
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    quick_sort(nums, l, j) # 這里用 j 和 j + 1
    quick_sort(nums, j + 1, r)

n = input()
nums = [int(v) for v in input().split()]
quick_sort(nums, 0, len(nums) - 1)
for n in nums:
    print(n, end= " ")

5.快速選擇算法（第k個(gè)數(shù)）

時(shí)間復(fù)雜度為 O(n)

基本思路：
SL：左邊的數(shù)的個(gè)數(shù)
若 k <= SL，遞歸Left
若 k > SL，遞歸Right，注意此時(shí)找Right第 k - SL 小的數(shù)

6.快速選擇算法Python代碼實(shí)現(xiàn)

給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)列，以及一個(gè)整數(shù)k，請(qǐng)用快速選擇算法求出數(shù)列從小到大排序后的第k個(gè)數(shù)

輸入樣例：

5 3
3 1 2 4 5

輸出樣例：

3

Python3：

def quick_sort(nums, l, r, k): # 和快排相比，多用一個(gè)參數(shù)k
    if r <= l:
        return
    x = nums[(l + r) // 2]
    i, j = l - 1, r + 1
    while i < j:
        i += 1
        while nums[i] < x:  # 這里用小于號(hào)
            i += 1
        j -= 1
        while nums[j] > x: # 這里用大于號(hào)
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    sl = j - l + 1 # 左側(cè)數(shù)的個(gè)數(shù)
    if k <= sl: quick_sort(nums, l, j, k) # 這里用j
    else: quick_sort(nums, j + 1, r, k - sl) # 這里記得將新的k，替換為k-sl

a = input().split()
n = int(a[0])
k = int(a[1])
nums = [int(v) for v in input().split()]
quick_sort(nums, 0, len(nums) - 1, k)
print(nums[k-1])