代码如下:
# -*- coding: utf-8 -*-# 测试各种排序算法# link：www.bitscn.com# date：2013/2/2
#选择排序def select_sort(sort_array): for i, elem in enumerate(sort_array): for j, elem in enumerate(sort_array[i:]): if sort_array[i] > sort_array[j + i]: #交换 sort_array[i], sort_array[j + i] = sort_array[j + i], sort_array[i]#冒泡排序def bubble_sort(sort_array): for i, elem in enumerate(sort_array): for j, elem in enumerate(sort_array[:len(sort_array) – i – 1]): if sort_array[j] > sort_array[j + 1]: sort_array[j], sort_array[j + 1] = sort_array[j + 1], sort_array[j]
#插入排序def insert_sort(sort_array): for i, elem in enumerate(sort_array): for j, elem in enumerate(sort_array[:i]): if sort_array[j] > sort_array[i]: sort_array.insert(j, sort_array[i]) del sort_array[i + 1]#归并排序def merge_sort_wrapper(sort_array): merge_sort(sort_array, 0, len(sort_array) – 1)def merge_sort(sort_array, left = 0, right = 0): if left < right: center = (left + right) / 2 merge_sort(sort_array, left, center) merge_sort(sort_array, center + 1, right) merge(sort_array, left, right, center)def merge(sort_array, left, right, center): result = [] arraya = sort_array[left:center + 1] arrayb = sort_array[center + 1:right + 1] while((len(arraya) > 0) and (len(arrayb) > 0)): if(arraya[0] > arrayb[0]): result.append(arrayb.pop(0)) else: result.append(arraya.pop(0)) if(len(arraya) > 0): result.extend(arraya) if(len(arrayb) > 0): result.extend(arrayb) sort_array[left:right + 1] = result
#快排 def quick_sort(sort_array): if(len(sort_array) < 2): return left = [x for x in sort_array[1:] if x < sort_array[0]] right = [x for x in sort_array[1:] if x >= sort_array[0]] quick_sort(left) quick_sort(right) sort_array[:] = left + [sort_array[0]] + right#shell排序def shell_sort(sort_array): dist=len(sort_array)/2 while dist > 0: for i in range(dist,len(sort_array)): tmp=sort_array[i] j = i while j >= dist and tmp < sort_array[j - dist]: sort_array[j] = sort_array[j - dist] j -= dist sort_array[j] = tmp dist /= 2 #基数排序,均为整数，不支持负数和重复def radix_sort(sort_array): max_elem = max(sort_array) bucket_list = [] for i in range(max_elem): bucket_list.insert(i, 0) for x in sort_array: bucket_list[x - 1] = -1 sort_array[:] = [x + 1 for x in range(len(bucket_list)) if bucket_list[x] == -1]
#堆排序def heap_sort(sort_array): #没有写出来，再想想 pass
#测试例子def algo_sort_test(sort_array, sort_method): sort_method(sort_array)
if __name__ == ‘__main__’:
sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23] algo_sort_test(sort_array, select_sort) print sort_array sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23] algo_sort_test(sort_array, bubble_sort) print sort_array sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23] algo_sort_test(sort_array, insert_sort) print sort_array sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23] algo_sort_test(sort_array, merge_sort_wrapper) print sort_array sort_array = [1, 2, 3, 5, -4, 4, 10, 300, 19, 13, 16, 18, 500, 190, 456, 23] algo_sort_test(sort_array, quick_sort) print sort_array
sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23] algo_sort_test(sort_array, shell_sort) print sort_array sort_array = [1, 2, 3, 5, 4, 10, 19, 13, 16, 18, 190, 456, 23] algo_sort_test(sort_array, radix_sort) print sort_array print ‘ok’
非常基础的知识内容，选择、冒泡、插入、归并、基数，还有快排都能手写出来，但写了一遍发现堆排序忘了怎么做了。要复习啦。