python 排序算法

1 插入排序

1.1 直接插入排序

算法思想

直接插入排序的核心思想就是：將數組中的所有元素依次跟前面已經排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，直到全部元素都比較過。
因此，從上面的描述中我們可以發現，直接插入排序可以用兩個循環完成：

• 第一層循環：遍歷待比較的所有數組元素

• 第二層循環：將本輪選擇的元素(selected)與已經排好序的元素(ordered)相比較。如果：selected > ordered，那么將二者交換

    #直接插入排序def insert_sort(L):#遍歷數組中的所有元素，其中0號索引元素默認已排序，因此從1開始for x in range(1,len(L)):#將該元素與已排序好的前序數組依次比較，如果該元素小，則交換#range(x-1,-1,-1):從x-1倒序循環到0for i in range(x-1,-1,-1):#判斷：如果符合條件則交換if L[i] > L[i+1]:L[i] ,L[i+1] = L[i+1],L[i]return L
  

1.2 希爾排序

算法思想

希爾排序在數組中采用跳躍式分組的策略，通過某個增量（gap初始值一般為len(元素長度)//2）將數組元素劃分為若干組，然后分組進行插入排序，這算是一趟排序，（下一趟）隨后逐步縮小增量，繼續按組進行插入排序操作，直至增量為1。希爾排序通過這種策略使得整個數組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在后。然后縮小增量，到增量為1時，其實多數情況下只需微調即可，不會涉及過多的數據移動。
解法1：

def shell_sort(alist):"""希爾排序"""n = len(alist)gap = n // 2while gap >= 1:for j in range(gap, n):i = jwhile (i - gap) >= 0:if alist[i] < alist[i - gap]:alist[i], alist[i - gap] = alist[i - gap], alist[i]i -= gapelse:breakgap //= 2if __name__ == '__main__':alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]print("原列表為：%s" % alist)shell_sort(alist)print("新列表為：%s" % alist)

解法2：

def shell_sort(alist):gap = len(alist)while gap > 1:gap = gap // 2for i in range(gap, len(alist)):for j in range(i % gap, i, gap):if alist[i] < alist[j]:alist[i], alist[j] = alist[j], alist[i]return alistalist = shell_sort([4,5,6,7,3,2,6,9,8])
print (alist)

2. 選擇排序

2.1 簡單選擇排序

選擇排序不受輸入數據的影響，即在任何情況下時間復雜度不變。選擇排序每次選出最小的元素，因此需要遍歷 n-1 次。

def selectionSort(nums):
for i in range(len(nums) - 1): # 遍歷 len(nums)-1 次
minIndex = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[minIndex]: # 更新最小值索引
minIndex = j
nums[i], nums[minIndex] = nums[minIndex], nums[i] # 把最小數交換到前面
return nums

2.2 堆排序

堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

• 大根堆：每個節點的值都大于或等于其子節點的值，用于升序排列；
• 小根堆：每個節點的值都小于或等于其子節點的值，用于降序排列。
  

參考

（1）.https://blog.csdn.net/mxz19901102/article/details/80087596
（2）.https://www.jianshu.com/p/bbbab7fa77a2