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

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

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

Python實(shí)現(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:') #輸入逗號(hào)分隔整數(shù)列 如:7,6,5,1,8,34
for item in input.split(','):
  A.append(int(item))
 
InsertionSort(A)#插入排序
print A

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

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

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

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

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

相關(guān)文章

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

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

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

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

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

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

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

    Python IDE PyCharm的基本快捷鍵和配置簡(jiǎn)介

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

    python制作小說爬蟲實(shí)錄

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

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

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

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

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

    python 標(biāo)準(zhǔn)差計(jì)算的實(shí)現(xiàn)(std)

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

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

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

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

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

最新評(píng)論