以下排序算法均按照從小到大排序N個元素：
1、冒泡排序
基本思想：
遍歷元素列表，比較相鄰的元素专挪，如果第一個比第二個大，則交換其位置茄猫，經(jīng)過第一輪比較狈蚤，最大的元素將恰好被放置到最后一個；
第二輪不再比較最后的元素划纽，只比較前面的N-1個元素脆侮，則經(jīng)過第二輪比較之后，我們可以確定第二大的元素勇劣；
依次類推靖避，第i輪比較能夠確定第i大的元素，可知經(jīng)過N-1輪比較后我們能夠確定所有元素的位置（為什么不是N輪比較?——因?yàn)榍癗-1個大的元素確定了比默，還剩最后一個幻捏，自然就是最小的，無需再比較）
def bubble_sort(nums):
if nums is not None: # 注意判空,不要用=或者!=判空
for i in range(1, len(nums)): # 一共進(jìn)行1到N-1輪比較命咐，N即列表長度len(nums)
is_sorted = True # 用來判斷是否已經(jīng)排好序
for j in range(len(nums) - i): # 第i輪比較中需要比較第0,1,…,(N-i-1)個元素與其后面一個位置上的元素的大小
if nums[j] > nums[j + 1]:
is_sorted = False # 如果沒有發(fā)生交換篡九，則說明已經(jīng)排好序，無需進(jìn)行下一輪比較
nums[j], nums[j + 1] = nums[j + 1], nums[j]
if is_sorted:
break
return nuts
2醋奠、選擇排序
基本思想：
遍歷元素榛臼，記錄下最小的元素所在的位置伊佃，然后把最小的元素和位置0上的元素互換；
一共進(jìn)行N-1輪遍歷：
第一輪確定第1小的元素沛善，放在位置0航揉；
第二輪確定第2小的元素，放在位置1金刁；x
…
第i輪確定第i小的元素帅涂，放在位置i；
N-1輪遍歷之后可以確定所有元素的正確位置尤蛮。
def select_sort(nums):
if nums is not None: # 注意判空
for i in range(0, len(nums) - 1): # 一共進(jìn)行0到N-2共N-1輪選擇媳友，N即列表長度len(nums)
min_index = i # 先初始化每輪選擇中最小的元素的位置為每輪遍歷的第一個元素
for j in range(i + 1, len(nums)): # 從第一個元素的下一個位置開始與記錄的最小元素做比較
if nums[j] < nums[min_index]:
min_index = j
if i != min_index:
nums[i], nums[min_index] = nums[min_index], nums[i]
3、快速排序
基本思想：采用分而治之的思想抵屿，選取nums中的一個數(shù)作為基準(zhǔn)點(diǎn)庆锦，把要排序的數(shù)據(jù)分成兩部分捅位，一部分比基準(zhǔn)點(diǎn)小轧葛，一部分比基準(zhǔn)點(diǎn)大；
然后再對這兩部分?jǐn)?shù)據(jù)分別采用分而治之的方法進(jìn)行排序艇搀；
最后再把這幾部分?jǐn)?shù)據(jù)連接到一起尿扯。
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
4、插入排序
基本思想：插入排序的原理類似于打撲克牌焰雕，把待排序數(shù)據(jù)分成兩部分衷笋，一部分是已排好序的有序數(shù)據(jù)，一部分是亂序數(shù)據(jù)矩屁，
開始時(shí)默認(rèn)第一個數(shù)有序辟宗，然后再將后面的數(shù)逐個插入，插入操作具體包括：
1吝秕、與有序數(shù)據(jù)比較泊脐，確定插入位置，
2烁峭、在每次比較中將比待插入數(shù)據(jù)大的數(shù)據(jù)后移容客，給待插入數(shù)據(jù)騰位置
def insert_sort(nums):
for i in range(len(nums)):
preIndex = i-1 # 0到i-1的數(shù)據(jù)為已經(jīng)排好序的有序數(shù)據(jù)
curnum = nums[i] # 記錄下一個要插入到有序數(shù)據(jù)中的數(shù)
# 遍歷有序數(shù)據(jù)，找到curnum應(yīng)插入的位置
while preIndex >= 0 and nums[preIndex] > curnum: # 注意不要漏掉preIndex等于0
nums[preIndex+1] = nums[preIndex] # 比curnum大的數(shù)往后挪
preIndex -= 1
nums[preIndex+1] = curnum
return nums
5约郁、希爾排序
基本思想：希爾排序是直接插入排序的升級版缩挑，減少插入排序的移動次數(shù)
插入排序在每次插入一個數(shù)據(jù)的過程中，湊要大量移動數(shù)據(jù)鬓梅，
希爾排序?qū)⑿蛄邪垂潭ㄩg隔劃分為多個子序列供置，在子序列中簡單插入排序，先做遠(yuǎn)距離移動使序列基本有序绽快；
逐漸縮小間隔重復(fù)操作芥丧，最后間隔為1時(shí)即簡單插入排序悲关。
def shell_insert(nums, d):
n = len(nums)
for i in range(d, n):
j = i - d
temp = nums[i] # 記錄要插入的數(shù)
while j >= 0 and nums[j] > temp: # 從后向前，找到比其小的數(shù)的位置
nums[j + d] = nums[j] # 向后挪動
j -= d
if j != i - d:
nums[j + d] = temp
def shell_sort(nums):
n = len(nums)
if n <= 1:
return nums
d = n//2
while d >= 1:
shell_insert(nums, d)
d = d//2
return nums
6娄柳、歸并排序
基本思想：歸并排序運(yùn)用分治遞歸思想：將大問題分為較小的子問題寓辱，分而治之；遞歸調(diào)用同樣的方法解決子問題赤拒。
最終將序列的排序問題分治為一個數(shù)的排序問題秫筏，關(guān)鍵在于如何將子問題答案合并為問題答案。
兩個有序序列合并為一個有序序列挎挖，借助一個暫存數(shù)組（列表）这敬，兩個序列元素依次比較填入暫存列表，形成一個有序序列蕉朵。
歸并排序劃分子問題采用二分法崔涂，共需O(logn)次劃分，當(dāng)然需要相當(dāng)次合并始衅；每次合并遍歷比較O(n)冷蚂。時(shí)間復(fù)雜度O(nlogn)。
def merge_sort(nums):
import math
if len(nums) < 2:
return nums
middle = math.floor(len(nums)/2)
left, right = nums[0:middle], nums[middle:]
return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
參考學(xué)習(xí)：
十大排序算法總結(jié)Python3實(shí)現(xiàn)
python 十大經(jīng)典排序算法
