首頁  >  文章  >  後端開發  >  python中排序演算法的實作方法總結(程式碼)

python中排序演算法的實作方法總結(程式碼)

不言
不言原創
2018-09-27 14:48:001871瀏覽

這篇文章帶給大家的內容是關於python中排序演算法的實作方法總結(程式碼),有一定的參考價值,有需要的朋友可以參考一下,希望對你有幫助。

1.插入排序:插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據,演算法適用於少量資料的排序;首先將第一個作為已經排好序的,然後每次從後的取出插入到前面併排序;

def insert_sort(ilist):
    for i in range(len(ilist)):
        for j in range(i):
            if ilist[i] < ilist[j]:
                ilist.insert(j, ilist.pop(i))
                break
    return ilist
 
ilist = insert_sort([4,5,6,7,3,2,6,9,8])
print ilist

2.冒泡排序:它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成

def bubble_sort(blist):
    count = len(blist)
    for i in range(0, count):
        for j in range(i + 1, count):
            if blist[i] > blist[j]:
                blist[i], blist[j] = blist[j], blist[i]
    return blist
 
blist = bubble_sort([4,5,6,7,3,2,6,9,8])
print blist

3.快速排序:透過一趟排序將要排序的資料分割成獨立的兩部分,其中一部分的所有資料都比另外一部分的所有資料都要小,然後再按此方法對這兩部分資料分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個資料變成有序序列

def quick_sort(qlist):
    if qlist == []:
        return []
    else:
        qfirst = qlist[0]
        qless = quick_sort([l for l in qlist[1:] if l < qfirst])
        qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
        return qless + [qfirst] + qmore
 
qlist = quick_sort([4,5,6,7,3,2,6,9,8])
print qlist

4.選擇排序:第1趟,在待排序記錄r1 ~ r[n]中選出最小的記錄,將它與r1交換;第2趟,在待排序記錄r2 ~ r[n]中選出最小的記錄,將它與r2交換;以此類推,第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄,將它與r[i]交換,使有序序列不斷增長直到全部排序完畢

def select_sort(slist):
    for i in range(len(slist)):
        x = i
        for j in range(i, len(slist)):
            if slist[j] < slist[x]:
                x = j
        slist[i], slist[x] = slist[x], slist[i]
    return slist
 
slist = select_sort([4,5,6,7,3,2,6,9,8])
print slist

5.二分查找:主要透過除2後進行判斷查找;

#!/usr/bin/python
# -*- coding: utf-8 -*-
#二分查找,用于在较大的数据列表中查询某个值,考虑到元素比较多,单纯的遍历会造成内存压力过大,考虑使用二分查找
#二分查找的关键在于查询中间值,将需要查找的值与中间值进行比较,然后确定查找方向
def binary_search(data_source,find_n):
    #取中位数
    mid=int(len(data_source)/2)

    if len(data_source)>=1:
        if data_source[mid]>find_n:  #中位数大于要查找的数,则要查找的数在左半部分,继续调用二分算法进行查找
            binary_search(data_source[:mid],find_n)
        elif data_source[mid]<find_n:  #中位数小于要查找的数,则要查找的数在右半部分
            binary_search(data_source[mid:],find_n)
        else:   #中位数等于要查找的数
            print("找到了:",data_source[mid])

    else:
        print("没有找到")


if __name__=="__main__":
    data=list(range(3,1600))
    binary_search(data,400)

以上是python中排序演算法的實作方法總結(程式碼)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn