Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说排序算法总结（Python版）[亲测有效],希望能够帮助你!!!。

经典排序算法总结与实现

经典排序算法在面试中占有很大的比重，也是基础，为了未雨绸缪，这次收集整理并用Python实现了八大经典排序算法，包括冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序以及基数排序。希望能帮助到有需要的同学。之所以用 Python 实现，主要是因为它更接近伪代码，能用更少的代码实现算法，更利于理解。

本篇博客所有排序实现均默认从小到大。

一、冒泡排序BubbleSort

介绍：

冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

Python源代码（错误版本）：

def bubble_sort(arry):
    n = len(arry)                   #获得数组的长度
    for i in range(n):
        for j in range(i+1, n):
            if  arry[i] > arry[j] :       #如果前者比后者大
                arry[i],arry[j] = arry[j],arry[i]      #则交换两者
    return arry

注：上述代码是没有问题的，但是实现却不是冒泡排序，而是选择排序（原理见选择排序），注意冒泡排序的本质是“相邻元素”的顺序交换，而非每次完成一个最小数字的选定。

Python源代码（正确版本）：

def bubble_sort(arry):
    n = len(arry)                   #获得数组的长度
    for i in range(n):
        for j in range(1, n-i):    # 每轮找到最大数值 或者用 for j in range(i+1, n)
            if  arry[j-1] > arry[j] :       #如果前者比后者大
                arry[j-1],arry[j] = arry[j], arry[j-1]      #则交换两者
    return arry

不过针对上述代码还有两种优化方案。

优化1：

某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。

Python源代码：

def bubble_sort2(ary):
	n = len(ary)
	for i in range(n):
		flag = True    # 标记
		for j in range(1, n - i):
			if ary[j] < ary[j-1]:
				ary[j], ary[j-1] = ary[j-1], ary[j]
				flag = False
		# 某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了
		if flag:    
			break
	return ary
			

优化2：

记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

def bubble_sort3(ary):
	n = len(ary)
	k = n    #k为循环的范围，初始值n
	for i in range(n):
		flag = True
		for j in range(1, k):    #只遍历到最后交换的位置即可
			if ary[j-1] > ary[j]:
				ary[j-1], ary[j] = ary[j], ary[j-1]
				k = j     #记录最后交换的位置
				flag = False
		if flag:
			break
	return ary
				

注：上面for j in range(1,k)，这句很有意思，虽然后面有if ary[j-1] > ary[j]则k = j,但是这个k不会直接就变动，不然试想，当j=1，0与1位置坐了交换之后，k=j=1，j这一步循环直接就挂掉了，事实上，k的改变是在下一轮i坐了改变之后才会真正起作用，所以j可以记录最后交换位置。

二、选择排序SelectionSort

介绍：

选择排序是另一个很容易理解和实现的简单排序算法。学习它之前首先要知道它的两个很鲜明的特点。
1. 运行时间和输入无关
为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供任何实质性帮助的信息。因此使用这种排序的我们会惊讶的发现，一个已经有序的数组或者数组内元素全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长！而其他算法会更善于利用输入的初始状态，选择排序则不然。
2. 数据移动是最少的
选择排序的交换次数和数组大小关系是线性关系，选择排序无疑是最简单直观的排序。看下面的原理时可以很容易明白这一点。

步骤：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 以此类推，直到所有元素均排序完毕。

源代码：(python实现)

def select_sort(ary):
    n = len(ary)
    for i in range(0,n):
        min = i                             #最小元素下标标记
        for j in range(i+1,n):
            if ary[j] < ary[min] :
                min = j                     #找到最小值的下标
        ary[min],ary[i] = ary[i],ary[min]   #交换两者
    return ary

三、插入排序 InsertionSort

介绍：

插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

排序演示

源代码：(python实现)

# 插入排序
def insert_sort(ary):
	count = len(ary)
	for i in range(1, count):
		key = i - 1
		mark = ary[i]    # 注： 必须将ary[i]赋值为mark，不能直接用ary[i]
		while key >= 0 and ary[key] > mark:
			ary[key+1] = ary[key]
			key -= 1
		ary[key+1] = mark
	return ary

四、希尔排序 ShellSort

介绍：

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10/2 = 5

49 38 65 97 26 13 27 49 55 4

1A 1B
2A 2B
3A 3B
4A 4B
5A 5B

1A, 1B, 2A, 2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。
第二次 gap = 5 / 2 = 2

排序后

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E
2A 2B 2C 2D 2E

第三次 gap = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65

1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

第四次 gap = 1 / 2 = 0 排序完成得到数组：

4 13 26 27 38 49 49 55 65 97

下面给出严格按照定义来写的希尔排序

源代码：(python实现)

def shell_sort(ary):
    count = len(ary)
    gap = round(count / 2)
    # 双杠用于整除（向下取整），在python直接用 “/” 得到的永远是浮点数，
    # 用round()得到四舍五入值
    while gap >= 1:
        for i in range(gap, count):
            temp = ary[i]
            j = i
            while j - gap >= 0 and ary[j - gap] > temp:  # 到这里与插入排序一样了
                ary[j] = ary[j - gap]
                j -= gap
            ary[j] = temp
        gap = round(gap / 2)
    return ary

五、归并排序 MergeSort

介绍：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

原理

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归因排序： 本质是采用分治法思路（Divide and Conquer）。首先，将长度为 N 的无序数组两两拆分为长度为 1 的 N 个有序数据（divide：长度为 1 的数组自然是有序的），然后，对长度为 1 的有序数组进行两两处理（conquer：将两两长度为 1 的数组进行顺序合并）。最终，得到一个完整的排序数组
快速排序： 思路虽然也是分治法思路（Divide and Conquer），但其处理的思路跟归因不一样，归并排序是先两两拆分为长度为 1 的有序数组再处理，而 快速排序 则是先将一个无序数组进行处理为两组数据（左边数组一定小于右边数组），然后再进一步切分，直到长度为 1 的数组时候即完成整个排序。
总结：两者分治的处理步骤不在一起，归因排序 是 分-再处理-合并，而快速排序是 处理-分-合并。

合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为m-i +1、n-m。

1、j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
2、若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
3、//选取r[i]和r[j]较小的存入辅助数组rf
        如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵
        否则，rf[k]=r[j]； j++； k++； 转⑵
4、//将尚未处理完的子表中元素存入rf
        如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
        如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
5、合并结束。

排序演示

源代码：(python实现)

# 归并排序

    def merge_sort(ary):
        
        if len(ary) <= 1:
            return ary
        
        median = int(len(ary)/2)    # 二分分解
        left = merge_sort(ary[:median])
        right = merge_sort(ary[median:])
        return merge(left, right)    # 合并数组
    
    def merge(left, right):
     '''合并操作， 将两个有序数组left[]和right[]合并成一个大的有序数组'''
        res = []
        i = j = k = 0
        while(i < len(left) and j < len(right)):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
                
        res = res + left[i:] + right[j:]
        return res

六、快速排序 QuickSort

介绍：

快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。

步骤：

1. 从数列中挑出一个元素作为基准数。
2. 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
3. 再对左右区间递归执行第二步，直至各区间只有一个数。

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：

先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。

以一个数组作为示例，取区间第一个数为基准数。

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始时，i = 0; j = 9; X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

i = 3; j = 7; X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结：

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

照着这个总结很容易实现挖坑填数的代码.

排序演示

源代码：(python实现)

def quick_sort(ary):
    return qsort(ary, 0, len(ary) - 1)


def qsort(ary, start, end):
    if start < end:
        left = start
        right = end
        key = ary[start]
    else:
        return ary
    while left < right:
        while left < right and ary[right] >= key:
            right -= 1
        if left < right:  # 说明打破while循环的原因是ary[right] <= key
            ary[left] = ary[right]
            left += 1
        while left < right and ary[left] < key:
            left += 1
        if left < right:  # 说明打破while循环的原因是ary[left] >= key
            ary[right] = ary[left]
            right -= 1
    ary[left] = key  # 此时，left=right，用key来填坑

    qsort(ary, start, left - 1)
    qsort(ary, left + 1, end)
    return ary
    

C++ 版本：

#include<iostream>
#include<stack>
#include<vector>
using namespace std;


void quickSortHelper(vector<int>& nums, int begin, int end) { 
   
	if (begin >= end) return;
	int left = begin;
	int right = end;
	int base = nums[left];
	while (left < right) { 
   
		while (left < right && nums[right] >= base) { 
   
			right--;
		}
		if (left < right) { 
   
			nums[left] = nums[right];
			left++;
		}
		while (left < right && nums[left] < base) { 
   
			left++;
		}
		if (left < right) { 
   
			nums[right] = nums[left];
			right--;
		}
	}
	nums[left] = base;
	quickSortHelper(nums, begin, left - 1);
	quickSortHelper(nums, left + 1, end);
	return;
}

vector<int> quickSort(vector<int> nums) { 
   
	if (nums.size() <= 1) return nums;
	int length = nums.size() - 1;
	quickSortHelper(nums, 0, length);
	return nums;

}



int main()
{ 
   
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; ++i)
	{ 
   
		cin >> nums[i];
	}
	vector<int> res;
	res = quickSort(nums);

	for (auto x : res) { 
   
		cout << x;
	}
	return 0;
}

另外一种实现方法

先从待排序的数组中找出一个数作为基准数（取第一个数即可），然后将原来的数组划分成两部分：小于基准数的左子数组和大于等于基准数的右子数组。然后对这两个子数组再递归重复上述过程，直到两个子数组的所有数都分别有序。最后返回“左子数组” + “基准数” + “右子数组”，即是最终排序好的数组。

源代码：(python实现)

# 实现快排
def quicksort(nums):
    if len(nums) <= 1:
        return nums

    # 左子数组
    less = []
    # 右子数组
    greater = []
    # 基准数
    base = nums.pop()

    # 对原数组进行划分
    for x in nums:
        if x < base:
            less.append(x)
        else:
            greater.append(x)

    # 递归调用
    return quicksort(less) + [base] + quicksort(greater)

七、堆排序 HeapSort

介绍：

堆排序与快速排序，归并排序一样都是时间复杂度为$O(N\ast logN)$的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

二叉堆定义及性质：

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：

父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。

堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i +
1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

堆的操作——插入删除

下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解，再给出本人的实现代码，最好是先看明白图后再去看代码。

堆化数组

有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如下图：

很明显，对叶子结点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分别作一次向下调整操作就可以了。

下图展示了这些步骤：

步骤：

1. 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。

2. 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。

3. 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。

排序演示：

源代码：(python实现)

def heap_sort(ary):
	n = len(ary)
	first = int(n/2-1)    #最后一个非叶子节点
	for start in range(first,-1,-1):    #构建最大堆
		max_heapify(ary,start,n-1)
	for end in range(n-1,0,-1):    #堆排，将最大跟堆转换成有序数组
		ary[end],ary[0] = ary[0], ary[end]    #将根节点元素与最后叶子节点进行互换，取出最大根节点元素，对剩余节点重新构建最大堆
		max_heapify(ary,0,end-1)    #因为end上面取的是n-1，故而这里直接放end-1，相当于忽略了最后最大根节点元素ary[n-1]
	return ary


#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
	root = start
	while True:
		child = root * 2 + 1    #调整节点的子节点
		if child > end:
			break
		if child + 1 <= end and ary[child] < ary[child+1]:
			child = child + 1   #取较大的子节点
		if ary[root] < ary[child]:    #较大的子节点成为父节点
			ary[root], ary[child] = ary[child], ary[root]    #交换
			root = child
		else:
			break

八、基数排序

假设要对 10 万个手机号码进行排序，显然桶排序和计数排序都不太适合，那怎样才能做到时间复杂度为 O(n) 呢?

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

8.1 基数排序原理

• 手机号码有这样的规律，假设要比较两个手机号码 a, b 的大小，如果在前面几位中，a 手机号码已经比 b大了，那后面几位就不用看了。
• 借助 稳定排序算法，我们可以这么实现。从手机号码的最后一位开始，分别按照每一位的数字对手机号码进行排序，依次往前进行，经过 11 次排序之后，手机号码就都有序了。
• 下面是一个字符串的排序实例，和手机号码类似。

• 根据每一位的排序，我们可以用刚才的桶排序或者计数排序来实现，它们的时间复杂度可以做到 O(n)。如果排序的数据有 K位，则总的时间复杂度为 O(K * n)，当 K 不大时，基数排序的时间复杂度就近似为 O(n)。
• 有时候，要排序的数据并不都是等长的，比如我们要对英文单词进行排序。这时候，我们可以把所有单词都补足到相同长度，位数不够的在后面补 ’0‘，所有字母的 ASCII 码都大于 ‘0’，因此不会影响原有的大小顺序。
• 基数排序需要数据可以分割出独立的位出来，而且位之间有递进的关系。除此之外，每一位的数据范围都不能太大，要可以用线性排序算法来进行排序。

8.2 算法思想

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

算法步骤：

• 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
• 从最低位开始，依次进行一次排序。
• 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的，所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

动态效果示意图：

8.3 代码

C++：

#include <iostream>
#include <vector>

using namespace std;

// 求出数组中最大数的位数的函数
int MaxBit(vector<int> input){ 
   
	// 数组最大值
	int max_data = input[0];
	for (int i = 1; i < input.size(); i++){ 
   
		if (input[i] > max_data){ 
   
			max_data = input[i];
		}
	}

	// 数组最大值的位数
	int bits_num = 0;
	while (max_data){ 
   
		bits_num++;
		max_data /= 10;
	}

	return bits_num;
}

// 取数xxx上的第d位数字
int digit(int num, int d){ 
   
	int pow = 1;
	while (--d > 0){ 
   
		pow *= 10;
	}
	return num / pow % 10;
}

// 基数排序
vector<int> RadixSort(vector<int> input, int n){ 
   
	// 临时数组，用来存放排序过程中的数据
	vector<int> bucket(n);					
	// 位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数
	vector<int> count(10);				
	// 从低位往高位循环
	for (int d = 1; d <= MaxBit(input); d++){ 
   
		// 计数器清0
		for (int i = 0; i < 10; i++){ 
   
			count[i] = 0;
		}

		// 统计各个桶中的个数
		for (int i = 0; i < n; i++){ 
   
			count[digit(input[i],d)]++;
		}

		/* * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为： [0, 2, * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中 * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的 * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在 * 7、6、5三个(8-5=3)位置 */
		for (int i = 1; i < 10; i++){ 
   
			count[i] += count[i - 1];
		}

		/* * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的顺序，不应该打 * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个 * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处 * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。 * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮 * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会 * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该 * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题 */
		for (int i = n - 1; i >= 0; i--){ 
   
			int k = digit(input[i], d);
			bucket[count[k] - 1] = input[i];
			count[k]--;
		}

		// 临时数组复制到 input 中
		for (int i = 0; i < n; i++){ 
   
			input[i] = bucket[i];
		}
	}

	return input;
}

void main(){ 
   
	int arr[] = { 
    50, 123, 543, 187, 49, 30, 0, 2, 11, 100 };
	vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "排序前:";
	for (int i = 0; i < test.size(); i++){ 
   
		cout << test[i] << " ";
	}
	cout << endl;
	
	vector<int> result = test;
	result = RadixSort(result, result.size());
	cout << "排序后:";
	for (int i = 0; i < result.size(); i++){ 
   
		cout << result[i] << " ";
	}
	cout << endl;
	system("pause");
}

运行结果如下图所示：

Python：

# -*- coding:utf-8 -*-

def RadixSort(input_list):
	''' 函数说明:基数排序（升序） Author: www.cuijiahua.com Parameters: input_list - 待排序列表 Returns: sorted_list - 升序排序好的列表 '''
	def MaxBit(input_list):
		''' 函数说明:求出数组中最大数的位数的函数 Author: www.cuijiahua.com Parameters: input_list - 待排序列表 Returns: bits-num - 位数 '''
		max_data = max(input_list)
		bits_num = 0
		while max_data:
			bits_num += 1
			max_data //= 10
		return bits_num

	def digit(num, d):
		''' 函数说明:取数xxx上的第d位数字 Author: www.cuijiahua.com Parameters: num - 待操作的数 d - 第d位的数 Returns: 取数结果 '''	
		p = 1
		while d > 1:
			d -= 1
			p *= 10
		return num // p % 10


	if len(input_list) == 0:
		return []
	sorted_list = input_list
	length = len(sorted_list)
	bucket = [0] * length
	
	for d in range(1, MaxBit(sorted_list) + 1):
		count = [0] * 10

		for i in range(0, length):
			count[digit(sorted_list[i], d)] += 1

		for i in range(1, 10):
			count[i] += count[i - 1]

		for i in range(0, length)[::-1]:
			k = digit(sorted_list[i], d)
			bucket[count[k] - 1] = sorted_list[i]
			count[k] -= 1
		for i in range(0, length):
			sorted_list[i] = bucket[i]

	return sorted_list

if __name__ == '__main__':
	input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
	print('排序前:', input_list)
	sorted_list = RadixSort(input_list)
	print('排序后:', sorted_list)

8.4 算法分析

8.4.1 基数排序的性能

其中，d 代表数组元素最高为位数，n 代表元素个数。

8.4.2 时间复杂度

这个时间复杂度比较好计算：count * length；其中 count 为数组元素最高位数，length为元素个数；所以时间复杂度：O(n * d)

8.4.3 空间复杂度

空间复杂度是使用了两个临时的数组：10 + length；所以空间复杂度：O（n）。

8.4.4 算法稳定性

在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。

9. 排序算法总结

9.1 时间复杂度

下面为七种经典排序算法指标对比情况：

O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

一般时间复杂度到了$2^n$(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是$O(2^n)$.

平方阶($n^2$)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.

9.2 空间复杂度

冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)

快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.

基数排序的空间复杂是O(n),桶排序的空间复杂度不确定

9.3 最快的排序算法是桶排序

所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)但桶排序一般用的不多,因为有几个比较大的缺陷.

1.待排序的元素不能是负数,小数.

2.空间复杂度不确定,要看待排序元素中最大值是多少.

所需要的辅助数组大小即为最大元素的值.

参考资料

• 经典排序算法总结与实现
• 白话经典算法
• 各种排序算法比较(2):时间复杂度,空间复杂度
• 排序算法总结