- 深入理解算法中‘分割’的概念瘟斜。
- 在序列變換中巧妙使用‘空位’， 使代碼變得美觀
- 推薦每個(gè)程序員可以在十分鐘內(nèi)寫(xiě)完如下代碼
- 面試前寄症，先寫(xiě)個(gè)快排
- 在入門(mén)一個(gè)新的程序語(yǔ)言時(shí)，不妨先寫(xiě)個(gè)快排練練
# Quick Sort
# 選取一個(gè)Key
# 對(duì)比： 將比Key小的放到左邊萍恕，比Key大的放到右邊
# 循環(huán)： 直至每個(gè)元素都與key對(duì)比過(guò)了
# 遞歸： key左側(cè)的和key右側(cè)的分別遞歸
list = [5,7,1,8,4]
count = len(list)
def quickSort(L, low, high):
print('\nquickSort: ', L, low, high)
i = low
j = high
if i >= j:
return L
# 為了序列調(diào)位方便 在序列中挖出一個(gè)空位
# 此時(shí)空位 序列中i的位置
key = L[i]
while i < j:
while i < j and L[j] >= key: # 遍歷key右側(cè)的值
j = j-1 # 若不小于key厅须，j向左挪一個(gè)
# 此時(shí)序列中的空位為L(zhǎng)[i]椿猎，賦值后變?yōu)長(zhǎng)[j]
L[i] = L[j] #此時(shí)j指向的值小于key, 將其賦給i指向的位置（i值在key 值的左側(cè)）
while i < j and L[i] <= key: #遍歷key左側(cè)的值
i = i+1 # 若不大于key, i 向右挪一個(gè)
# 此時(shí)序列中的空位為L(zhǎng)[j], 賦值后變?yōu)長(zhǎng)[i]
L[j] = L[i] #此時(shí)i 指向的值大于key，將其值賦給（空位）
print(L, i, j)
# 每循環(huán)一次調(diào)整序列中的兩個(gè)值
# key右側(cè)的一個(gè)值和key左側(cè)的一個(gè)值
# 不斷循環(huán)直到i = j示损，即key左側(cè)的均小于key渗磅，右側(cè)的均大于key
# 此時(shí)i = j ， 將key值放入空位中
L[i] = key
quickSort(L, low, i-1)
quickSort(L, j+1, high)
return L
quickSort(list,0,count-1)
無(wú)注釋版
def quick_sort(lists, left, right):
# 快速排序
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
一行版---- 利用序列切片
import numpy as np
# 生成隨機(jī)序列
randomList = np.random.randint(500,size=100)
print(randomList)
def qsort(numbers):
if len(numbers) == 0: return []
else: return qsort([i for i in numbers[1:] if i <= numbers[0]]) + [numbers[0]] + qsort([i for i in numbers[1:] if i > numbers[0]])
qsort(randomList)
