本節(jié)讓我們來介紹三種常用的排序算法乃戈。
1. 快速排序
首先要打亂序列順序 褂痰，以防算法陷入最壞時間復雜度≈⒙牵快速排序使用“分而治之”的方法缩歪。
對于一串序列，首先從中選取一個數谍憔，凡是小于這個數的值就被放在左邊一摞匪蝙，凡是大于這個數的值就被放在右邊一摞。然后习贫，繼續(xù)對左右兩摞進行快速排序逛球。
直到進行快速排序的序列長度小于 2 （即序列中只有一個值或者空值）。
<pre class="" style="margin: 0px; padding: 0px 0.5em; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; color: rgb(51, 51, 51); font-size: 17px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: 0.544000029563904px; line-height: 27.2000007629395px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: 1; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255);">
<pre style="margin: 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; font-size: inherit; color: inherit; line-height: inherit;">
quicksort
import random
def quicksort(seq):
if len(seq) < 2:
return seq
else:
base = seq[0]
left = [elem for elem in seq[1:] if elem < base]
right = [elem for elem in seq[1:] if elem > base]
return quicksort(left) + [base] + quicksort(right)
seq = [9, 8, 7, 6, 5, 4, 3]
random.shuffle(seq)
seq：[6, 4, 9, 3, 8, 5, 7]
print(quicksort(seq))
輸出：[3, 4, 5, 6, 7, 8, 9]
</pre>
</pre>
2. 冒泡排序
冒泡排序（順序形式）苫昌，從左向右颤绕，兩兩比較，如果左邊元素大于右邊祟身，就交換兩個元素的位置奥务。
其中，每一輪排序袜硫，序列中最大的元素浮動到最右面氯葬。也就是說，每一輪排序婉陷，至少確保有一個元素在正確的位置帚称。
這樣接下來的循環(huán)，就不需要考慮已經排好序的元素了憨攒，每次內層循環(huán)次數都會減一世杀。
其中阀参，如果有一輪循環(huán)之后肝集，次序并沒有交換，這時我們就可以停止循環(huán)蛛壳，得到我們想要的有序序列了杏瞻。
<pre class="" style="margin: 0px; padding: 0px 0.5em; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; color: rgb(51, 51, 51); font-size: 17px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: 0.544000029563904px; line-height: 27.2000007629395px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: 1; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255);">
<pre style="margin: 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; font-size: inherit; color: inherit; line-height: inherit;">
def bouble_sort(sequence):
seq = sequence[:]
length = len(seq) - 1
i = j = 0
flag = 1
while i < length:
j = 0
while j < length - i:
if seq[j] > seq[j + 1]:
seq[j], seq[j + 1] = seq[j + 1], seq[j]
flag = 0
j += 1
if flag:
break
i += 1
return seq
</pre>
</pre>
3. 選擇排序
選擇排序，每次選擇當前序列的最小值衙荐，將其與當前序列的第一個元素交換位置捞挥，每迭代一次，當前序列長度減一忧吟。迭代結束砌函，即可得到有序序列。
<pre style="margin: 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; font-size: inherit; color: inherit; line-height: inherit;">
<pre style="margin: 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; font-size: inherit; color: inherit; line-height: inherit;">
def find_minimal_index(seq):
min_elem = seq[0]
count = 0
min_elem_index = count
for elem in seq[1:]:
count += 1
if elem < min_elem:
elem, min_elem = min_elem, elem
min_elem_index = count
return min_elem_index
def select_sort(sequence):
# 選擇排序
seq = sequence[:]
length = len(seq)
for i in range(length):
index = find_minimal_index(seq[i:])
seq[index + i], seq[i] = seq[i], seq[index + i]
return seq
</pre>
</pre>
