一、插入排序

插入排序與我們平時打撲克牌非常相似，將新摸到的牌插入到已有的牌中合適的位置，而已有的牌往往是有序的。

1.1 執(zhí)行流程

（1）在執(zhí)行過程中，插入排序會將序列分為2部分，頭部是已經(jīng)排好序的，尾部是待排序的。
（2）從頭開始掃描每一個元素，每當(dāng)掃描到一個元素，就將它插入到頭部合適的位置，使得頭部數(shù)據(jù)依然保持有序

1.2 逆序?qū)?/h3>

數(shù)組 <2,3,8,6,1> 的逆序?qū)椋?lt;2,1> ❤️,1> <8,1> <8,6> <6,1>，共5個逆序?qū)Α?br/>插入排序的時間復(fù)雜度與逆序?qū)Φ臄?shù)量成正比關(guān)系，逆序?qū)Φ臄?shù)量越多，插入排序的消耗的時間就越多。
當(dāng)逆序?qū)Φ臄?shù)量極少時，插入排序的效率特別高，甚至速度比 O nlogn 級別的快速排序還要快。

1.3 代碼實現(xiàn)

將一個元素插入到數(shù)組有序的前半部分中，那個插入的位置元素一定是比該元素大，而該位置前的元素比該元素?。ɑ蛘呤菦]有前一個元素）。所以我們可以通過比較，將該元素進行冒泡：如果前一個元素比我大，則交換位置，否則停止冒泡。

def insertion_sort_ver1(array):
 n=len(array)
 for right in range(1,n):
  cur=right
  while cur>0 and array[cur-1]>array[cur]:
array[cur-1],array[cur]=array[cur],array[cur-1]
cur-=1

整體代碼：

import numpy as np
import time
#檢查是否有序
def orderCheck(array):
 for i in range(len(array)-1):
  if array[i]>array[i+1]:
print('排序失敗')
return
 print('排序成功')
 
def sort(sort_algorithm,ori_array):
 #先復(fù)制一份數(shù)組，再進行更改
 array = np.copy(ori_array)
 start=time.clock()
 sort_algorithm(array)
 end=time.clock()
 total_time=float(end-start)
 print(sort_algorithm.__name__+" : %0.5f" % total_time)
 orderCheck(array)
def insertion_sort_ver1(array):
 n=len(array)
 for right in range(1,n):
  cur=right
  while cur>0 and array[cur-1]>array[cur]:
array[cur-1],array[cur]=array[cur],array[cur-1]
cur-=1

array=np.random.randint(0,10000,2000,dtype=int)
sort(insertion_sort_ver1, array)

消耗時間為0.82632秒。

1.4 優(yōu)化1

在冒泡中，交換前后cur和cur-1位置兩個元素的位置，需要進行兩次賦值，但如果冒泡仍要繼續(xù)，cur-1位置的元素還是會被cur-2位置的元素覆蓋，所以兩次賦值中的一次其實是無意義的，為此我們可以先找到插入位置，然后將后方的元素作統(tǒng)一的移動；或者是在冒泡過程中只進行一次賦值（將前一個元素移動到后方），直到冒泡結(jié)束確定插入位置后，再進行待插入元素的插入。

#元素交換作優(yōu)化
def insertion_sort_ver2(array):
 n=len(array)
 for right in range(1,n):
  cur=right
  elem=array[cur]
  while cur>0 and array[cur-1]>elem:
array[cur]=array[cur-1]
cur-=1
  array[cur]=elem

消耗時間為0.45987秒，明顯變快了。

1.5 優(yōu)化2

之前我們在尋找插入的位置時，采用的是從大到小依次遍歷的方法，因為是在一個有序的數(shù)組上尋找插入的位置，我們肯定會想到一種查找的方法：二分查找。通過二分查找，我們可以通過O(logn)級別的比較與O(n)級別的元素移動完成排序任務(wù)，而之前我們進行的比較和移動，都是O(n)級別。

1.5.1 普通二分查找

普通的二分查找十分簡單，根據(jù)中間位置元素大小更新兩端索引位置即可，在此兩端的索引 [left,right)采用左閉右開的方式，這樣未查找到元素的條件就十分簡單，因為區(qū)間左閉右開，當(dāng)left<right時，表明區(qū)間內(nèi)還有元素，仍舊可以進行查找；否則，區(qū)間里沒有元素了，說明元素未查找到，代碼如下。

def binary_search(array,target):#[left,right)左閉右開
 left=0
 right=len(array)
 while left<right:#當(dāng)left<right，表明區(qū)間中還有值，否則哪怕left==right,因right不可取，區(qū)間中還是無值
  middle = (left + right) >> 1
  if target<array[middle]:
right=middle
  elif array[middle]<target:
left=middle+1
  else:
return middle
 return -1

1.5.2 二分查找插入位置

查找插入位置的二分查找顯然和普通二分不同，在此我們修改一下左右端點移動的條件與移動方式。在此左右端點依舊左閉右開，如果當(dāng)array[middle]小于或等于插入元素target，那么顯然middle不可能是插入位置，middle位置的元素也不再需要，left應(yīng)該為middle+1；而當(dāng)array[middle]大于target，那么middle有可能是插入的位置（插入位置大于target，前一個元素如果存在，應(yīng)小于target），應(yīng)該保留middle，所以right=middle。但是區(qū)間是左閉右開，right不可取到，哪怕right=middle，middle不還是無法取得嗎？但由于array[middle]不論取何值（不管是大于、等于、小于），都將導(dǎo)致左右端點left、right的變化，且數(shù)組中左右端點代表區(qū)間的大小是不斷減小的，最終左右端點重合，此時的位置就是插入的位置。
下面是查找的示例：

代碼如下：

def binary_search(array,index):
 left=0
 right=index
 while left<right:
  middle=(left+right)>>1
  if array[middle]>array[index]:#大于目標(biāo)，可能是插入的位置，用right保留
right=middle
  else:#小于等于，不可能是插入位置，更新left為middle+1
left=middle+1
 return left #最后插入的位置

1.5.3 使用二分的插入排序

找到插入位置后，我們只需移動位置后面的元素，再將元素插入即可。

#利用二分查找找到插入的點，減少了比較的次數(shù)
def insertion_sort_ver3(array):
 n=len(array)
 for right in range(1,n):
  index=binary_search(array,right)
  elem=array[right]
  for i in range(right,index,-1):
array[i]=array[i-1]
  array[index]=elem

可見速度比之前的插入排序仍有提高。

1.6 時間空間復(fù)雜度

最壞、平均時間復(fù)雜度：O(n^2)，最好時間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)。

1.7 穩(wěn)定性

插入排序?qū)⒑蠓降脑貜暮笸安迦?，后邊相等的元素將插入在左邊相等元素的右?cè)，沒有改變原有的位置，屬于穩(wěn)定排序。

到此這篇關(guān)于Python排序算法之插入排序及其優(yōu)化方案詳解的文章就介紹到這了,更多相關(guān)Python插入排序內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

國外穩(wěn)定服務(wù)器

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。