欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談插入排序算法在Python程序中的實現(xiàn)及簡單改進

 更新時間:2016年05月04日 10:18:04   作者:chim692  
這篇文章主要介紹了插入排序算法在Python程序中的實現(xiàn)及簡單改進,插入排序算法的最差時間復雜度為O(n^2),最優(yōu)時間復雜度為O(n),存在一定的優(yōu)化空間,需要的朋友可以參考下

Python實現(xiàn)插入排序的一般范例為:

#coding=cp936
#coding=cp936
#插入排序算法
def InsertionSort(A):
  for j in range(1,len(A)):
    key = A[j]
    i = j-1
    #向前查找插入位置
    while i>=0 and A[i]>key:
      A[i+1] = A[i]
      i = i-1
    A[i+1] = key
 
#初始化輸入數(shù)據(jù)
A = []
input = raw_input('please input some numbers:') #輸入逗號分隔整數(shù)列 如:7,6,5,1,8,34
for item in input.split(','):
  A.append(int(item))
 
InsertionSort(A)#插入排序
print A

插入算法的原理是:當前元素和已經(jīng)排序好的部分比較,滿足條件時插入,插入點之后的元素全部往后移。
然而,我也正是受這個描述的誤導,在實現(xiàn)的時候走了一些彎路。比如有以下列表:

test = [2, 5, 11, 21, 10, 18, 24]

比如當前元素是10,我在開最初的實現(xiàn)思路是從列表的第一個元素開始,一直比較到元素11才找到合適位置.這樣做最終是可以實現(xiàn)排序的,但是有一個問題,就是當我把10插入11的位置之后,11和21都需要往后移,這又需要另一個循環(huán),實現(xiàn)如下:

def insertSort(sort_list):
  list_length = len(sort_list)
  if list_length < 2 :
    return sort_list
  for i in range(1,list_length):
    key = sort_list[i]
    j = 0
    while j < i:
      if sort_list[j] > key:
        for k in range(i,j,-1):
          sort_list[k] = sort_list[k-1]
        sort_list[j] = key
        break
      j += 1
  return sort_list

   首先,引入了三個循環(huán)變量以及三層循環(huán),效率較低;其次是代碼結(jié)構(gòu)會比較混亂,需要改進。

后來我想能不能比較完一個元素就把它移到合適的位置,好如去超市買水果,手里拿到不合適的,總會直接把它放到一邊,不會再碰它。具體到算法實現(xiàn),還用上面的列表舉例,當前元素是10,先跟相鄰的21比較,發(fā)現(xiàn)21比10大,則21往后移動一位,即移到10所在位置;然后10和11比較,又會把11往后移動一位;在比較到元素5時,發(fā)現(xiàn)已經(jīng)找到了10應該存放的位置,而此時移動也隨之完成。
代碼實現(xiàn)如下:

def insertSort(sort_list):
  list_length = len(sort_list)
  if list_length < 2 :
    return sort_list
  for i in range(1,list_length):
    key = sort_list[i]
    j = i - 1
    while j >=0 and sort_list[j] > key:
      sort_list[j+1] = sort_list[j]
      j -= 1
    sort_list[j+1] = key
  return sort_list

   孰優(yōu)孰劣,大家對比便知。

相關(guān)文章

  • python虛擬機之描述器實現(xiàn)原理與源碼分析

    python虛擬機之描述器實現(xiàn)原理與源碼分析

    在本篇文章當中主要給大家介紹描述器背后的實現(xiàn)原理,通過分析?cpython對應的源代碼了解與描述器相關(guān)的字節(jié)碼的指令,我們就可以真正了解到描述器背后的原理,需要的朋友可以參考下
    2023-05-05
  • Python?pyecharts案例超市4年數(shù)據(jù)可視化分析

    Python?pyecharts案例超市4年數(shù)據(jù)可視化分析

    這篇文章主要介紹了Python?pyecharts案例超市4年數(shù)據(jù)可視化分析,文章圍繞主題展開詳細的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-08-08
  • pyshp創(chuàng)建shp點文件的方法

    pyshp創(chuàng)建shp點文件的方法

    今天小編就為大家分享一篇pyshp創(chuàng)建shp點文件的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-12-12
  • Python IDE PyCharm的基本快捷鍵和配置簡介

    Python IDE PyCharm的基本快捷鍵和配置簡介

    這篇文章主要介紹了Python IDE PyCharm的基本快捷鍵和配置簡介,PyCharm為一個收費的軟件,需要的朋友可以參考下
    2015-11-11
  • python制作小說爬蟲實錄

    python制作小說爬蟲實錄

    本文給大家介紹的是作者所寫的第一個爬蟲程序的全過程,從構(gòu)思到思路到程序的編寫,非常的細致,有需要的小伙伴可以參考下
    2017-08-08
  • Python代碼注釋規(guī)范代碼實例解析

    Python代碼注釋規(guī)范代碼實例解析

    這篇文章主要介紹了Python代碼注釋規(guī)范代碼實例解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-08-08
  • python實現(xiàn)XML解析的方法解析

    python實現(xiàn)XML解析的方法解析

    這篇文章主要介紹了python實現(xiàn)XML解析的方法解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-11-11
  • python 標準差計算的實現(xiàn)(std)

    python 標準差計算的實現(xiàn)(std)

    這篇文章主要介紹了python 標準差計算的實現(xiàn)(std),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-07-07
  • 基于Python制作一個解壓的內(nèi)存加速球

    基于Python制作一個解壓的內(nèi)存加速球

    安全管家助手什么的上總會帶一個內(nèi)存加速球,有關(guān)掉進程以及內(nèi)存清理的功能,本文就來利用Python制作一個解壓的內(nèi)存加速球,有需要的小伙伴可以參考下
    2023-10-10
  • 詳解python 模擬豆瓣登錄(豆瓣6.0)

    詳解python 模擬豆瓣登錄(豆瓣6.0)

    這篇文章主要介紹了python模擬豆瓣登錄,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-04-04

最新評論