首頁 > 軟體

Python排序演演算法之插入排序及其優化方案詳解

2021-06-11 19:01:36

一、插入排序

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

1.1 執行流程

(1)在執行過程中,插入排序會將序列分為2部分,頭部是已經排好序的,尾部是待排序的。
(2)從頭開始掃描每一個元素,每當掃描到一個元素,就將它插入到頭部合適的位置,使得頭部資料依然保持有序

1.2 逆序對

陣列 <2,3,8,6,1> 的逆序對為:<2,1> ❤️,1> <8,1> <8,6> <6,1>,共5個逆序對。
插入排序的時間複雜度與逆序對的數量成正比關係,逆序對的數量越多,插入排序的消耗的時間就越多。
當逆序對的數量極少時,插入排序的效率特別高,甚至速度比 O nlogn 級別的快速排序還要快。

1.3 程式碼實現

將一個元素插入到陣列有序的前半部分中,那個插入的位置元素一定是比該元素大,而該位置前的元素比該元素小(或者是沒有前一個元素)。所以我們可以通過比較,將該元素進行冒泡:如果前一個元素比我大,則交換位置,否則停止冒泡。

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):
    #先複製一份陣列,再進行更改
    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 優化1

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

#元素交換作優化
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 優化2

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

1.5.1 普通二分查詢

普通的二分查詢十分簡單,根據中間位置元素大小更新兩端索引位置即可,在此兩端的索引 [left,right)採用左閉右開的方式,這樣未查詢到元素的條件就十分簡單,因為區間左閉右開,當left<right時,表明區間內還有元素,仍舊可以進行查詢;否則,區間裡沒有元素了,說明元素未查詢到,程式碼如下。

def binary_search(array,target):#[left,right)左閉右開
    left=0
    right=len(array)
    while left<right:#當left<right,表明區間中還有值,否則哪怕left==right,因right不可取,區間中還是無值
        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 二分查詢插入位置

查詢插入位置的二分查詢顯然和普通二分不同,在此我們修改一下左右端點移動的條件與移動方式。在此左右端點依舊左閉右開,如果當array[middle]小於或等於插入元素target,那麼顯然middle不可能是插入位置,middle位置的元素也不再需要,left應該為middle+1;而當array[middle]大於target,那麼middle有可能是插入的位置(插入位置大於target,前一個元素如果存在,應小於target),應該保留middle,所以right=middle。但是區間是左閉右開,right不可取到,哪怕right=middle,middle不還是無法取得嗎?但由於array[middle]不論取何值(不管是大於、等於、小於),都將導致左右端點left、right的變化,且陣列中左右端點代表區間的大小是不斷減小的,最終左右端點重合,此時的位置就是插入的位置。
下面是查詢的範例:




程式碼如下:

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

1.5.3 使用二分的插入排序

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

#利用二分查詢找到插入的點,減少了比較的次數
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 時間空間複雜度

最壞、平均時間複雜度:O(n^2),最好時間複雜度:O(n),空間複雜度:O(1)。

1.7 穩定性

插入排序將後方的元素從後往前插入,後邊相等的元素將插入在左邊相等元素的右側,沒有改變原有的位置,屬於穩定排序。

到此這篇關於Python排序演演算法之插入排序及其優化方案詳解的文章就介紹到這了,更多相關Python插入排序內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com