排序性能比较

常见的算法思想有：分治法(繁分为简)、贪心法相对比较满意的解去运算，而不考虑所有的情况)、穷举法(全列出)、递归法(返回本身)、递推法(按照规律求解)、回溯法(退上一步)、动态规划法(寻找最优解)，迭代法(由旧推新)，分支界限法(问题分支分界)。

所谓排序，就是讲原来无序的一个序列重新排列成有序序列。

常见的排序算法，包括：冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序和队排序。冒泡排序、选择排序、插入排序的时间复杂度为O(n^2),希尔排序的时间复杂度为O(n^1.25)，快速排序、归并排序和堆排序的时间复杂度为O(nlog2(n))。

性能的好坏，看重其稳定性。所谓的稳定性，是指代排序的两个或两个以上相同的项，在排序前后这些相同的项相对位置有没有发生变化。

如果要求不能重复，则排序结果是唯一的，那么选择的排序方法稳定与否就无关紧要。如果可以冲去，就要根据实际需求来选择。

那么哪些排序算法是不稳定的呢？

“快些选堆”：其中“快”指的是快速排序，“些”值得书希尔排序，“选”指的是选择排序，“堆”指的是堆排序，这四种是不稳定的，其他是稳定的。

排序算法分类

1.插入类排序
即在一个已经有序的序列中，插入一个新数。这类排序有：直接排序、折半排序、希尔排序。

2.交换类排序
这类方法的核心是“交换”，即每趟排都是通过一系列的“交换”来完成的。这类排序有冒泡排序、快速排序。

3.选择类排序
该方法的核心是“选择”，即每趟排序都选出一个最小（或最大）的记录，把它和序列中的第一个（或最后一个）记录交换，这样最小（或最大）的记录到位。这类排序有：选择排序、堆排序。

4.归并类排序
所谓归并，就是将两个或两个以上的有序序列合并成一个新的有序序列。这类排序有：（二路）归并排序。

5.基数类排序
此类方法较为特别，是基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字。

排序算法分析

本文主要分析的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。

插入排序

算法思想：每趟将一个待排序的关键字，按照其关键字值的大小插入到已经排好的部分序列的适当位置上，直到插入完成。由大到小排，后往前插。空间复杂度O(1)。

'''insertion sort'''
def insertion_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    for i in range(1,iter_len):
        key = sort_list[i]
        location = i
        for j in range(i-1,-1,-1):
            if sort_list[j]>key:
                sort_list[j+1] = sort_list[j]
                location = j
        sort_list[location] = key
    return sort_list

希尔排序

算法思想：希尔排序又叫做缩小增量排序，是将待排序的序列按某种规则分成几个子序列，分别对这几个子序列进行插入排序，其中这一规则就是增量。如可以使用增量为总长的一半，再一半，直至1来分格序列，且每一趟希尔排序的增量都是逐渐缩小的，希尔排序的每趟排序都会使得整个序列变得更加有序，等整个序列基本有序了，再使用一趟插入排序，这样会更有效率，这就是希尔排序的思想。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def shell_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    gap = iter_len / 2
    while gap > 0:
        for i in range(0, gap):
            for j in range(i + gap, iter_len, gap):
                if (sort_list[j] < sort_list[j - gap]):
                    key = sort_list[j]
                    k = j - gap
                    while k >= 0 and sort_list[k]>key:
                        sort_list[k + gap] = sort_list[k]
                        k -= gap

                    sort_list[k + gap] = key
        gap /= 2

    return sort_list

冒泡排序

算法思想：相邻两个数逐次比较，选出大的往下走，小的上浮，每一趟遍历将最大的沉到最后。时间复杂度O(n^2)。

def bubble_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    for i in range(iter_len-1):
        for j in range(iter_len-1-i):
            if sort_list[j]>sort_list[j+1]:
                sort_list[j],sort_list[j+1]=sort_list[j+1],sort_list[j]

    return sort_list

快速排序

算法思想：一趟快速排序是以一个枢轴，将序列分成两部分，枢轴的一边比它小（或小于等于），另一边比它大（或大于等于）。

一遍快速排序结果：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j；

算法性能：快速排序最好情况下时间复杂度为O(nlogn)，待排序列越接近无序，则该算法效率越高，在最坏情况下时间复杂度为O(n*n)，待排序列越接近有序，则该算法效率越低，算法的平均时间复杂度为O(nlogn)。就平均时间而言，快速排序是所有排序算法中最好的。该算法的空间复杂度为 O(logn)，快速排序是递归进行的，需要栈的辅助，因此需要的辅助空间比前面几类排序方法要多。

快速排序的效率和选取的“枢轴”有关，选取的枢轴越接近中间值，算法效率就越高，因此为了提高算法效率，可以在第一次选取“枢轴”时做文章，

#!/usr/bin/env lowython
# -*- coding: utf-8 -*-
class quick_sort(object):
    def _partition(self, alist, low, high):
        i, j = low, high
        x = alist[low]
        while i < j:
            while i < j and alist[j] >= x:
                j -= 1
            if i < j:
                alist[i] = alist[j]
                i += 1
            while i < j and alist[i] <= x:
                i += 1
            if i < j:
                alist[j] = alist[i]
                j -= 1
        alist[i] = x
        return i

    def _quicksort(self, alist, low, high):
        if low < high:
            q = self._partition(alist, low, high)
            self._quicksort(alist, low, q - 1)
            self._quicksort(alist, q + 1, high)

    def __call__(self, sort_list):
        self._quicksort(sort_list, 0, len(sort_list) - 1)
        return sort_list

在快速排序中，需要使用递归来分别处理左右子段，递归深度可以理解为系统栈自动保存的深度，先处理短的分段再处理长的分段，可以减少时间复杂度。

如果按长的递归优先的话，那么短的递归会一直保存在栈中，直到长的处理完。短的优先的话，他是作为一个整体保存在栈中的，所以递归栈中的保留数据少一些。

选择排序

算法思想：该算法的主要动作就是“选择”，采用简单的选择方式，从头至尾顺序扫描序列，找出最小的一个记录，和第一个记录交换，接着从剩下的记录中继续这种选择和交换，最终使序列有序。

def selection_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    for i in range(iter_len-1):
        smallest = sort_list[i]
        location = i
        for j in range(i+1,iter_len):
            if sort_list[j]<smallest:
                smallest = sort_list[j]
                location = j
        if i !=location:
            sort_list[i],sort_list[location]= sort_list[location],sort_list[i]
    return sort_list

堆排序

算法思想：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。

根据堆的定义，其根节点的值是最大（或最小），因此将一个无序序列调整为一个堆，就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后（或最前），这样有序序列元素增加1个，无序序列中元素减少1 个，对新的无序序列重复这样的操作，就实现了序列排序。堆排序中最关键的操作是将序列调整为堆，整个排序的过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树的过程。

class heap_sort(object):
    def _max_heapify(self, alist, i, heap_size=None):
        length = len(alist)
        if heap_size is None:
            heap_size = length
        l = 2 * i + 1
        r = 2 * i + 2
        largest = i
        if l < heap_size and alist[l] > alist[i]:
            largest = l
        if l < heap_size and alist[r] > alist[i]:
            largest = r
        if largest != i:
            alist[i], alist[largest] = alist[largest], alist[i]
            self._max_heapify(alist, largest, heap_size)

    def _build_max_heap(self, alist):
        root_end = int(len(alist) / 2)
        for i in range(root_end-1,-1,-1):
            self._max_heapify(alist,i)

    def __call__(self, sort_list):
        self._build_max_heap(sort_list)
        heap_size = len(sort_list)
        for i in range(len(sort_list)-1,0,-1):
            sort_list[0],sort_list[i]=sort_list[i],sort_list[0]
            heap_size -=1
            self._max_heapify(sort_list, 0, heap_size)
        return sort_list

归并排序

算法思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

class merge_sort(object):
    def _erge(self, alist, p, q, r):
        left = alist[p:q + 1]
        right = alist[q + 1:r + 1]
        for i in range(p, r + 1):
            if len(left) > 0 and len(right) > 0:
                if left[0] <= right[0]:
                    alist[i] = left.pop(0)
                else:
                    alist[i] = right.pop(0)
            elif len(right) == 0:
                alist[i] = left.pop(0)
            elif len(left) == 0:
                alist[i] = right.pop(0)

    def _merge_sort(self, alist, p, r):
        if p < r:
            q = int((p + r) / 2)
            self._merge_sort(alist, p, q)
            self._merge_sort(alist, q + 1, r)
            self._merge(alist, p, q, r)

    def __call__(self, sort_list):
        self._merge_sort(sort_list, 0, len(sort_list) - 1)
        return sort_list

基数排序

算法思想：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

import math
def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists

一些结论

（1）快速排序、希尔排序、归并排序、堆排序的平均时间为O(nlogn)，其他的为O(n*n)。

（2）快速排序、希尔排序、选择排序、堆排序不稳定，其他的稳定。

（3）经过一趟排序能够保证一个元素到达最终位置的是冒泡排序、快速排序、选择排序、堆排序。

（4）元素比较次数和原始序列无关的是选择排序、折半插入排序。

（5）排序趟数和原始序列有关的是交换类排序。

（6）直接插入排序和折半插入排序的区别是寻找插入位置的方式不同，一个是按顺序查找方式，另一个是按折半查找方式。

参考资料：
博客园

宁哥的小站

八大排序算法的Python实现