排序算法（一）

二分查找

• 二分查找的前提是已经排序好的数据

• 返回数组的下表

  def bin_search(data_set, value):

    low = 0
    high = len(data_set) - 1
    while low <= high:
        mid = (low + high) // 2
        if data_set[mid] == value:
            return mid
        elif data_set[mid] > value:
            high = mid - 1
        else:
            low = mid + 1
  

冒泡排序（Bubble sort)

• 冒泡排序的时间复杂度是n2

def bubble_sort(data_set):
    for i in range(len(data_set)-1):
        for j in range(len(data_set)-i-1):
            if data_set[j]>data_set[j+1]:
                data_set[j],data_set[j+1]=data_set[j+1],data_set[j]
    return data_set

选择排序（select sort)

• 循环选择最小的值一次放在最前边
• 一趟排序记录最小的数， 放在第一个位置上
• 再一趟排序记录列表无序区最小的数，放在第二个位置
• 。。。。。
• 算法关键点：有序区和无序区，无序区最小数的位置

def select_sort(li):
    for i in range(len(li)-1):
        min_loc=i
        for j in range(i+1,len(li)):
            if li[j]<li[min_loc]:
                min_loc=j
        if min_loc != i:
            li[i],li[min_loc]=li[min_loc],li[i]

插入排序（insert sort)

• 初始时手里（有序区）只有一张牌
• 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
• 左手放置有序的牌（从小到大） ， 右手为无序牌， 每次从右手的第一个位置抽取一张牌，往左手插入。

def insert_sort(data_set):
    for i in range(1,len(data_set):
        catch=data_set[i]  #catch 存放右手抓取的牌
        left_index=i-1     #left_index一开始存取的是左手最后一个数下标
        while left_index>=0 and catch<=data_set[left_index]:  #当左手下标大于0，并且抓取的牌小于左手对应下标的牌
            data_set[left_index+1]=dsata_set[left_index]    #将左手下表的牌向后移动一位
            left_index=left_index-1     #将下表向前移动一位
        data_set[left_index+1]=catch    #循环结束将牌插入到下表后
    return data_set