【python】二分查找_排序

# 实现一个二分查找
# 输入:一个顺序list
# 输出: 待查找的元素的位置
def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1

    while first <= last:
#         " // "表示整数除法
        mid = (first + last)//2
        print('中间值\n',+mid)
#         print( mid)
        if alist[mid] > item:
            last = mid - 1
        elif alist[mid] < item:
            first = mid + 1
        else:
            return mid+1
    return -1

test = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(test, 3))      

排序算法

冒泡排序

大的往后面排

下面来用Python代码来简单的实现冒泡排序算法。思路很简单，第一层循环表示总共需要进行几层遍历，第一层遍历将最大的数转移到列表最后，第二次遍历将第二大的数转移到列表倒数第二的位置。总共循环n - 1次。内层循环依次比较相邻的数据大小，若靠前的数据比考后的数据大，则进行交换。

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                #alist[i], alist[i + 1] = alist[i + 1], alist[i]
                #把小的往前面排
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp
                
test = [100, 1, 2, 800, 13, 17, 191, 32, 42]
bubbleSort(test)          
test 
[1, 2, 13, 17, 32, 42, 100, 191, 800]


#或者
def bubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
    return alist
    
test = [0, 1, 2, 8, 13, 17, 19, 32, 42] 
bubbleSort(test)
test   
[0, 1, 2, 8, 13, 17, 19, 32, 42]      

冒泡法优化

短路冒泡法排序

上面的排序算法，第二层循环每次都会循环

def short_bubble_sort(a_list):
    for pass_num in range(len(a_list) - 1, 0, -1):
        exchanged = False
        for i in range(pass_num):
            if a_list[i] > a_list[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
#                 temp = a_list[i]
#                 a_list[i] = a_list[i + 1]
#                 a_list[i + 1] = temp
                exchanged = True
        if not exchanged:
            break      

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，所以称为：选择排序。

提升了冒泡法的性能

def selectionSort(alist):
   for num in range(len(alist)-1,0,-1):
       positionOfMax=0
       for i in range(1,num+1):
           if alist[i]>alist[positionOfMax]:
               positionOfMax = i
       #这一轮循环找到最大的索引        
#        temp = alist[num]
#        alist[num] = alist[positionOfMax]
#        alist[positionOfMax] = temp
       alist[positionOfMax],alist[num]=alist[num],alist[positionOfMax]
 
alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)      

def insert_sort(alist):
    """插入排序（逆序）"""
    #从前往后
    for i in range(1, len(alist)):
    #从后往前
        for j in range(i,0,-1):
       # 如果后面的比前面的小
            if alist[j] < alist[j-1]:
            #就把后面数值往前
                alist[j], alist[j-1] = alist[j-1], alist[j]
            else:
                break
    return alist

def main():
    alist = [2,5,7,4,6,9,1,3,8,7]
    insert_sort(alist)
    print(insert_sort(alist))
    # for li in alist[6::-1]:
    #     print(li)

if __name__ == '__main__':
    main()      

def quick_sort(alist, low, high):
    # 快速排序
    if low >= high:
        return alist
    else:
        one_base = alist[low]    # 把第一个作为基准值
        left_flag = low
        right_flag = high
        while left_flag < right_flag:
            while left_flag < right_flag and alist[right_flag] >= one_base:
                right_flag -= 1    # 右边的哨兵左移一个
            alist[left_flag] = alist[right_flag]
            while left_flag < right_flag and alist[left_flag] <= one_base:
                left_flag +=1    # 左边的哨兵右移一个
            alist[right_flag] = alist[left_flag]
        alist[right_flag] = one_base    # 两个哨兵相遇时则说明找到基准值的位置
        quick_sort(alist, low, left_flag-1)    # 递归左半部分
        quick_sort(alist, left_flag+1, high)    # 递归右半部分
        return alist

if __name__ == '__main__':
    alist = list(map(int, input().split()))
    print('排序前：', end='')
    for i in alist:
        print(i, end=' ')
    alist = quick_sort(alist, 0, len(alist)-1)
    print('\n排序后：', end='')
    for i in alist:
        print(i, end=' ')