1. 二分查找
- def bin_search(data,value):
- low=0
- high=len(data)-1
- while low<high:
- mid=(low+high)//2
- if data[mid]==value:
- return mid
- elif data[mid]<value:
- low=mid+1
- else:
- high=mid-1
2. 冒泡排序
- def bubble_sorted(data):
- for i in range(len(data)):
- #如果列表在一开始的时候就已经排好序, 那么我们提供 exchange 标识位即可判断直接跳出
- exchange=False
- for j in range(len(data)-i-1):
- if data[j]>data[j+1]:
- data[j],data[j+1]=data[j+1],data[j]
- exchange=True
- if not exchange:
- return data
3. 插入排序
- def insert_sorted(data):
- for i in range(1,len(data)):
- tmp=data[i]
- j=i-1
- while j>=0 and tmp<data[j]:
- data[j+1]=data[j]
- j=j-1
- data[j+1]=tmp
4. 快排
思路: 取第一个元素 P, 使 P 先归位, 列表被 P 分成两部分, 左边的都比元素 P 小, 右边的都比元素 P 大. 之后递归完成排序
- def quick_sorted(data,left,right):
- i=left
- j=right
- if i>j:
- return data
- tmp=data[left]
- while left<right:
- while left<right and data[right]>=tmp:
- right+=1
- data[left]=data[right]
- while left <right and data[left]<=tmp:
- left+=1
- data[right]=data[left]
- data[left]=tmp
- quick_sorted(data,left,i-1)
- quick_sorted(data,j+1,right)
- return data
5. 堆排序
思路:
1. 建立堆
2. 得到堆顶元素, 为最大元素
3. 去掉堆顶, 将堆最后一个元素放到堆顶, 此时可通过一次调整重新使堆有序.
4. 堆顶元素为第二大元素.
5. 重复步骤 3, 直到堆变空.
代码自行百度~~~
6. 希尔排序
希尔排序是一种分组插入排序算法. 首先取一个整数 d1=n/2, 将元素分为 d1 个组, 每组相邻量元素之间距离为 d1, 在各组内进行直接插入排序; 取第二个整数 d2=d1/2, 重复上述分组排序过程, 直到 di=1, 即所有元素在同一组内进行直接插入排序.
希尔排序每趟并不使某些元素有序, 而是使整体数据越来越接近有序; 最后一趟排序使得所有数据有序.
- def shell_sorted(data):
- gap=len(data)//2
- while gap>0:
- for i in range(gap,len(data)):
- tmp=data[i]
- j=i-gap
- while j>=0 and tmp<data[j]:
- data[j+gap]=data[j]
- j-=gap
- data[j+gap]=tmp
- gap/=2
基本算法
来源: http://www.bubuko.com/infodetail-2723385.html