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)