经典排序算法

最近在恶补算法，写一写经典的排序算法，先贴上各个复杂度对比图：

1.冒泡法排序

1 def bubble_sort(lists):
2     count = len(lists)
3     for i in range(count):
4         for j in range(i+1,count):
5             if lists[j] < lists[i]:
6                 lists[i], lists[j] = lists[j], lists[i]
7     return lists

总结：
最好情况：n-1次，时间复杂度为O(n)
最坏情况：1+2+···+(n-1)，时间复杂度为O(n²)

2.简单选择排序

def select_sort(lists):
    count = len(lists)
    for i in range(lists):
        m = i
        for j in range(i+1, count):
            if lists[j] < lists[min]:
                m = j
        lists[i], lists[min] = lists[min], lists[i]
    return lists

总结：
最好情况和最坏情况一致：1+2+···+(n-1)，时间复杂度为O(n²)

3.插入排序

def insert_sort(lists):
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j+1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

总结：
最好的情况：排序本身就是有序的,时间复杂度为O(n)
最坏的情况：排序是逆序，时间复杂度为O(n²)

4.希尔排序

def shell_sort(list):
    step = len(list)/2
    while step > 0:
        for i in range(step, len(list)):
            while i > step and list[i] > list[i-step]:
                list[i], list[i-step] = list[i-step], list[i]
                i -= step
        step = step/2
    return list

总结：
最好的情况和最坏的情况：时间复杂度为O(n*log₂n)

希尔排序的时间复杂度与step有关，但是没有证明出来。此结论与上表有区别，上表希尔排序的最优情况是改进的希尔排序或者是选择不同step的结果！

5.堆排序

def MAX_Heapify(heap,HeapSize,root):
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < HeapSize and heap[larger] < heap[left]:
        larger = left
    if right < HeapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:
        heap[larger],heap[root] = heap[root],heap[larger]
        MAX_Heapify(heap, HeapSize, larger)
def Build_MAX_Heap(heap):
    HeapSize = len(heap)
    for i in xrange((HeapSize -2)//2,-1,-1):
        MAX_Heapify(heap,HeapSize,i)
def HeapSort(heap):
    Build_MAX_Heap(heap)
    for i in range(len(heap)-1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        MAX_Heapify(heap, i, 0)
    return heap

总结：

堆排序的时间复杂度为O(n*log₂n),不稳定，不适合排序个数较少的情况

6.并归排序

 1 def merge_sort(list):
 2     if len(list) <= 1:
 3         return list
 4     num = len(list)/2
 5     left = merge_sort(list[:num])
 6     right = merge_sort(list[num:])
 7     return merge(left, right)
 8 def merge(left, right):
 9     i,j = 0,0
10     result = []
11     while i < len(left) and j < len(right):
12         if left[i] <= right[j]:
13             result.append(left[i])
14             i += 1
15         else:
16             result.append(right[j])
17             j += 1
18     result += left[i:]
19     result += right[j:]
20     return result

总结：
最好情况和最坏情况一样，时间复杂度都为O(n*log2n)

7.快速排序

def quick_sort(list, left, right):
    if left < right:
        return list
    list[left] = key
    low = left
    high = right
    while left < right:
        while left < right and list[right] >= key:
            right -= 1
        list[right], left[left] = list[left], left[right]
        while left < right and list[left] <= key:
            left += 1
        list[right], left[left] = list[left], left[right]
    pivot = left
    quick_sort(list, low, pivot-1)
    quick_sort(list, pivot+1, high)
    return list

总结：
最好情况：时间复杂度为O(n*log₂n)
最坏情况：时间复杂度为O(n²)
空间复杂度为O(n*log₂n)

8.基数排序

 1 import math
 2 def radix_sort(list, radix=10):
 3     k = int(math.ceil(math.log(max(a), radix)))
 4     bucket = [[] for i in range(radix)]
 5     for i in range(1, K+1):
 6         for val in list:
 7             bucket[val%(radix**i)/(radix**(i-1))].append(val)
 8         del a[:]
 9         for each in bucket:
10             list += each
11             del each[:]
12     return list

总结：
最好情况：时间复杂度为O(d*(n+r*d))
最坏情况：时间复杂度为O(d*(r+n))

写在最后：

安利一个神奇的东西，百度词条。

各种语言版本的排序应有尽有，你值得参考！

还安利一个博客：

http://ahalei.blog.51cto.com/

啊哈磊的博客，里面对各种算法的思想讲的很透彻，值得一看！