Python初级笔记4 排序

冒泡排序

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

# 时间复杂度 O(1) O(logN) O(n)
# 空间复杂度
a=[1,2,7,8,9,65,4,11]
for i in range(0,len(a)-1):
    for j in range(0,len(a)-1):
        if a[j]<= a[j+1]:
            a[j],a[j+1]=a[j+1],a[j]
        else:
            pass
print(a)#时间复杂度=O(n^2)

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

a=[1,2,7,8,9,20,65,4,5,11]
for i in range(0,len(a)):
    index=i
    for j in range(i,len(a)):
        if a[index]>a[j]:
            a[index],a[j]=a[j],a[index]
        else:
            pass
print(a)

a=[1,2,7,8,9,20,65,4,5,11,11,3,13,27]
for i in range(0,len(a)):
    for j in range(i,len(a)):
        if a[i]>a[j]:
            a[i],a[j]=a[j],a[i]
        else:
            pass
print(a)

插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

a=[11,53,1,4,8,4,9,19,22,13]
for i in range(0,len(a)-1):
    for j in range(i+1,0,-1):
        if a[j]<a[j-1]:
            a[j],a[j-1]=a[j-1],a[j]
print(a)

二分查找法

1.必须采用顺序存储结构。

2.必须按关键字大小有序排列。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 

a=[1,2,5,7,11,14,19,24,28,35,48,56,61,77,101]
item=int (input("enter the num="))
l=0
r=len(a)-1
while r>=l:
    mid=int((r+l)/2)
    g=a[mid]
    if item==g:
        print(mid)
        break
    elif item>g:
        l=mid+1
    elif item<g:
        r=mid-1
else:
     print("we don't have the num")