各种排序算法，常见的都有了！
import queue
def print_result_after(f):
def wrapper(*args):
ret = f(*args)
print(ret)
return ret
return wrapper
def binary_search(data,elem,almost = False,start=None,end=None):
if start is None:
start = 0
if end is None:
end = len(data)
if end <= start:
return None
while start < end:
mid = (start + end)//2
if data[mid] == elem:
return mid
elif data[mid] < elem:
start = mid + 1
else:
end = mid
if almost:
return start
else:
return None
@print_result_after
# 第一个数字无效，用来当哨兵
def insert_sort(data):
for i in range(2,len(data),1):
data[0] = data[i]
j = i - 1
while data[0] < data[j]:
data[j+1] = data[j]
j -= 1
data[j+1]= data[0]
data[0] = None
return data
@print_result_after
def insert_sort_using_binary_search(data):
for i in range(1,len(data),1):
elem = data[i]
proper_index = binary_search(data,elem,True,1,i)
j = i-1
while j >= proper_index:
data[j+1] = data[j]
j -= 1
data[proper_index] = elem
return data
@print_result_after
def bubble_sort(data):
for i in range(len(data)):
j = len(data) - 1
has_swap = False
while j > i:
if data[j] < data[j-1]:
data[j],data[j-1] = data[j-1],data[j]
has_swap = True
j -= 1
if not has_swap:
return data
return data
# 递归实现
def quick_sort(data,start,end):
if start >= end:
return
index = partition(data,start,end)
quick_sort(data,start,index)
quick_sort(data,index + 1,end)
# 使用栈实现
def quick_sort_using_stack(data):
if data is None or len(data) == 0:
return
stack = queue.LifoQueue()
stack.put([0,len(data)])
while not stack.empty():
start,end = stack.get()
index = partition(data,start,end)
if start < index:
stack.put([start,index])
if (index + 1) < end:
stack.put([index + 1,end])
# 使用队列实现
# 见文章《用栈和队列实现快速排序算法》http://www.jianshu.com/p/cadc9e830d09
def quick_sort_using_queue(data):
if data is None or len(data) == 0:
return
stack = queue.Queue()
stack.put([0,len(data)])
while not stack.empty():
start,end = stack.get()
index = partition(data,start,end)
if start < index:
stack.put([start,index])
if (index + 1) < end:
stack.put([index + 1,end])
def partition(data,start,end):
# 只有一个元素
if start == end - 1:
return start
pivot = data[start]
last = end - 1
while True:
# 相等的时候是只剩下一个，那个位置是主元的
while start < last:
if data[last] < pivot:
data[start] = data[last]
start += 1
break
else:
last -= 1
else:
data[start] = pivot
return start
while start < last:
if data[start] > pivot:
data[last] = data[start]
last -= 1
break
else:
start += 1
else:
data[start] = pivot
return start
def is_even(elem):
return elem % 2 == 0
def partition_odd_even(data):
start = 0
last = len(data) - 1
while start <= last:
if not is_even(data[start]):
data[start],data[last] = data[last],data[start]
last -= 1
else:
start += 1
# k:0~n-1
@print_result_after
def find_kth_elem(data,k):
if k >= len(data) or k < 0:
return None
start = 0
end = len(data)
index = partition(data, start, end)
while index != k:
if k < index:
end = index
index = partition(data,start,end)
else:
start = index + 1
index = partition(data, index + 1, index)
return data[index]
@print_result_after
def selection_sort(data):
# 最后一个自定
for i in range(len(data)-1):
pivot = i
for j in range(i + 1,len(data)):
if data[j] < data[pivot]:
pivot = j
if pivot != j:
data[pivot],data[i] = data[i],data[pivot]
return data
# 大堆
class max_heap(object):
def __init__(self,data):
self.data = data
for i in range(len(data)//2 + 1,0,-1):
self.max_heapify(i)
def max_heapify(self,node_index,length=None):
if node_index > len(self.data):
return
data = self.data
if not length:
length = len(data)
lc_index = node_index*2
rc_index = node_index*2+1
max_index = node_index
if lc_index < length and data[lc_index] > data[max_index]:
max_index = lc_index
if rc_index < length and data[rc_index] > data[max_index]:
max_index = rc_index
if max_index != node_index:
data[node_index],data[max_index] = data[max_index],data[node_index]
return self.max_heapify(max_index,length)
@print_result_after
def heap_sort(self):
data = self.data
for i in range(len(data)-1,0,-1):
print(i)
data[1],data[i] = data[i],data[1]
self.max_heapify(1,i)
return data
def is_max_heap(self,root=1):
lc_child = root*2
if lc_child < len(self.data) and self.data[lc_child] > self.data[root]:
return False
rc_child = root * 2
if rc_child < len(self.data) and self.data[rc_child] > self.data[root]:
return False
if lc_child < len(self.data):
ret = self.is_max_heap(lc_child)
if not ret:
return False
if rc_child < len(self.data):
ret = self.is_max_heap(rc_child)
if not ret:
return False
return True
def merge(data,start,mid,end):
buff = data.copy()
i = start
j = mid
step = start
while i<mid and j<end:
if buff[i] < buff[j]:
data[step] = buff[i]
i += 1
step += 1
else:
data[step] = buff[j]
j += 1
step += 1
while i < mid:
data[step] = buff[i]
i += 1
step += 1
while j < end:
data[step] = buff[j]
j += 1
step += 1
return data
def merge_sort(data,start,end):
# 0、1、负数个返回
if start >= end-1:
return
mid = (start + end)//2
merge_sort(data,start,mid)
merge_sort(data,mid,end)
merge(data,start,mid,end)
return data
def main():
data = [2,4,1,0,6,7,5]
merge_sort(data,0,len(data))
print(data)
if __name__ == '__main__':
main()
归并排序java版本
public static void mergeSort(int[] nums) {
doMergeSort(nums,0, nums.length);
}
private static void doMergeSort(int[] nums, int start, int end) {
if((end-start)<=1){
return ;
}
int mid = (start+end)/2;
doMergeSort(nums, start, mid);
doMergeSort(nums, mid, end);
merge(nums, start, mid, end);
}
public static void merge(int[] nums, int start, int mid, int end) {
int numMerge = end - start;
int[] temp = new int[numMerge];
int s1 = start;
int e1 = mid;
int s2 = mid;
int e2 = end;
int i = 0;
while(s1<e1&&s2<e2){
if(nums[s1]<nums[s2]){
temp[i++] = nums[s1++];
}else{
temp[i++] = nums[s2++];
}
}
while(s1<e1){
temp[i++] = nums[s1++];
}
while(s2<e2){
temp[i++] = nums[s2++];
}
i = 0;
while(start<end){
nums[start++] = temp[i++];
}
}
