Summary of implementation methods of sorting algorithms in python (code)

This article brings you a summary (code) of the implementation method of sorting algorithm in python. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. Insertion sort: The basic operation of insertion sort is to insert a data into the ordered data that has been sorted, so as to obtain a new ordered data with the number plus one. The algorithm is suitable for Sorting of a small amount of data; first treat the first one as already sorted, and then take out the last one and insert it into the front each time and sort it;

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. Bubble sorting: it repeatedly visits the items to be sorted A sequence that compares two elements at a time and swaps them if they are in the wrong order. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted.

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. Quick sort: The data to be sorted is divided into two independent parts through one sorting pass, where All the data in one part is smaller than all the data in the other part, and then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence

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. Selection sorting: In the first pass, select the smallest record among the records to be sorted r1 ~ r[n], and exchange it with r1; in the second pass, among the records to be sorted r2 ~ Select the smallest record from r[n] and exchange it with r2; and so on, the i-th pass records r[i] to be sorted ~ Select the smallest record from r[n], exchange it with r[i], so that the ordered sequence continues to grow until all sorting is completed

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. Binary search: mainly search by dividing by 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)

The above is the detailed content of Summary of implementation methods of sorting algorithms in python (code). For more information, please follow other related articles on the PHP Chinese website!