python常用程序算法
- 2020 年 1 月 16 日
- 筆記
一。冒泡排序：
1.冒泡排序是将无序的数字排列成从小到大的有序组合：
过程：对相邻的两个元素进行比较，对不符合要求的数据进行交换，最后达到数据有序的过程。
规律：
1.冒泡排序的趟数时固定的：n-1
2.冒泡排序比较的次数时固定的：n*(n-1)/2
3.冒泡排序交换的次数时不固定的：但是最大值为：n*(n-1)/2
注意：n = 数据个数，排序过程中需要临时变量存储要交换的数据
eg:
l=[688, 888, 711,999,1,4,6] for i in range(len(l)-1): for j in range(len(l)-1): if l[j]>l[j+1]: tmp=l[j] l[j]=l[j+1] l[j+1]=tmp print(l)
二。选择排序：
list=[10,3,5,2,9]
过程，循环当前列表，将当前循环到的值与余下的每个数字相比较，如果比当前值小，就与当前值交换位置。
eg:
l=[688, 888, 711,999,1,4,6] for i in range(len(l)-1): for j in range(i+1,len(l)): if l[j]<l[i]: tmp=l[i] l[i]=l[j] l[j]=tmp print(l)
优化：每次找到最小值后不立即替换，而是等待本次循环结束再替换，减少了操作的次数，效率提高了
l=[688, 888, 711,999,1,4,6] for i in range(len(l)-1): Min=i for j in range(i+1,len(l)): if l[Min] > l[j]: Min=j tmp=l[Min] l[Min]=l[i] l[i]=tmp print(l)
三。插入排序：
插入排序(Insertion Sort)的基本思想是：将列表分为2部分，左边为排序好的部分，右边为未排序的部分，循环整个列表，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
eg:
array=[9,8,7,6,5,4,3,2,1] for i in range(1,len(array)): current_val=array[i] current_position=i while current_position >0 and array[current_position-1] > current_val: array[current_position]=array[current_position-1] current_position-=1 array[current_position]=current_val print(array)
四。快速排序：
def quick_sort(array,first,last): if first >= last: #如果first=last证明不能再继续分半操作，每组只剩下一个元素，所有first=end，这时跳出程序 return start=first end=last mid=array[first] while start < end: #将end往左移动 while start < end and array[end] > mid: #如果成立则一直将end往左移动 end-=1 array[start]=array[end] #如果跳出上层循环则证明当前arrary[end]的值小于mid的值，此时将小的值移动至array[start]位置 #将start往右移动 while start < end and array[start] < mid: start+=1 array[end]=array[start] array[end]=mid #当最外层循环不成立时证明start与end相等，这时把start或者end位置赋值成mid的值即可 #继续左边的分半 quick_sort(array,first,end-1) #继续右边的分半 quick_sort(array,end+1,last) if __name__ == '__main__': import random,time array=[] for i in range(8): array.append(random.randrange(1,10000)) # array=[11,22,17,9,8,7,6,5,4,3,2] quick_sort(array,0,len(array)-1) print(array)
