二分查找
def bin_search(data_set, val):
low = 0
high = len(data_set) - 1
while low <= high:
mid = (low + high)//2
if data_set[mid]==val:
return mid
elif data_set[mid] < val:
low = mid + 1
else:
high = mid - 1
data = [1,4,2,5,63,4]
res = bin_search(data,63)
print(res)
冒泡排序
思路：首先列表中每两个相邻的数，如果前边的比后面的大，那么交换这两个数。
import random
def bubble_sort(list1):
for i in range(len(list1)-1):
for j in range(len(list1)-i-1):
if list1[j]>list1[j+1]:
list1[j],list1[j+1] = list1[j+1],list1[j]
data = list(range(15))
random.shuffle(data) #[2, 3, 13, 0, 14, 12, 6, 1, 4, 8, 10, 7, 11, 9, 5]
print(data)
res = bubble_sort(data) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print(data)
优化后
import random
def bubble_sort(list1):
for i in range(len(list1)-1):
exchange = False
for j in range(len(list1)-i-1):
if (list1[j])>(list1[j+1]):
list1[j],list1[j+1] = list1[j+1],list1[j]
exchange = True
if not exchange:
break
data = list(range(20))
random.shuffle(data)
print(data) # [5, 1, 14, 13, 6, 15, 7, 12, 2, 16, 11, 9, 18, 8, 17, 3, 4, 10, 0, 19]
bubble_sort(data)
print(data) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
java版冒泡排序
public class ArrayDemo4 {
public static void main(String[] args) {
int[] arr = new int[5];
arr[0] = 5;
arr[1] = 3;
arr[2] = 14;
arr[3] = 15;
arr[4] = 9;
// 冒泡排序
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
// 打印出排序的结果
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
}
选择排序
思路：一趟遍历记录最小的数，放到第一个位置，再一趟遍历记录剩余列表中的最小的值，依次放置
方法1
import random
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
li[i],li[min_loc] = li[min_loc],li[i]
data = list(range(20))
random.shuffle(data)
print(data)
select_sort(data)
print(data)
方法2
def select_sort(relist):
for i in range(len(relist)):
for j in range(len(relist)-i):
if relist[i] > relist[i+j]:
relist[i],relist[i+j] = relist[i+j],relist[i]
return relist
print(select_sort([1,5,2,6,9,3]))
插入排序
import random
def insert_sort(li):
for i in range(1,len(li)):
temp = li[i]
j = i - 1
while j>=0 and li[j]>temp:
li[j+1] = li[j]
j = j-1
li[j+1] = temp
data = list(range(20))
random.shuffle(data)
print(data)
insert_sort(data)
print(data)
快排
思路：1、取一个元素p（第一个元素）,使元素p归位
2、列表被p分成两部分，左边都比p小，右边都比p大
3、递归完成排序
总结：跟着我，右手左手一个慢动作，右手左手慢动作重播
def quick_sort(data,left,right):
if left < right:
mid = partition(data,left,right)
quick_sort(data,left,mid - 1)
quick_sort(data,mid+1,right)
def partition(data,left,right):
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
return left
import random
data = list(range(20))
random.shuffle(data)
print(data) # [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
quick_sort(data,0,len(data)-1)
print(data) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]