「@Author： Runsen」
排序可能是所有的算法中最最基础和最最常用的了。排序是一个非常经典的问题，它以一定的顺序对一个数组(或一个列表)中的项进行重新排序。
排序算法有很多种，每个都有其自身的优点和局限性。
今天我们来学习最最简单的冒泡排序算法。
冒泡排序
要学习冒泡排序必须知道它的原理：
所谓冒泡，就是将元素两两之间进行比较，谁大就往后移动，直到将最大的元素排到最后面，接着再循环一趟，从头开始进行两两比较，而上一趟已经排好的那个元素就不用进行比较了。
下面，我们就进入代码环节。
Python实现冒泡排序 现在，我给你一个nums = [3,1,25,6,8,10,15]，要求你用Python将nums实现冒泡排序。
看上去很难入手，其实很简单，我先给出代码
nums = [3,1,25,6,8,10,15]for i in range(len(nums)-1):    for j in range(len(nums) - i -1):        if nums[j] > nums[j+1]:            nums[j],nums[j+1] =  nums[j+1],nums[j]        print("第"+str(j)+"次内循环"+str(nums))    print("第"+str(i)+"次外循环"+str(nums))print("最后的结果"+str(nums))
我们先遍历nums，这不就是我们的range(len(nums)-1)，至于为什么是range(len(nums)-1)，其实就是我们的下标从0开始的，len(nums)返回是7，range是左开右闭，但是冒泡排序，我们只需要取到nums[5] = 10 就足够了，所以这里range(len(nums)-1)，取到[3,1,25,6,8,10]。
然后，我们在遍历之后的nums，比如i = 0，我们将j取值范围到len(nums) - i -1，用nums[j] > nums[j+1]判断两两的大小, 每次内循环将最大的移到最右边。
每一次内循环的目的就是将当中最大的移到最右边，而每一次外循环的目的就是当最大的移到最右边后，缩小范围，再寻找最大的数，再把它移到最右边。
我们执行上面的代码的结果如下：
第0次内循环[1, 3, 25, 6, 8, 10, 15]第1次内循环[1, 3, 25, 6, 8, 10, 15]第2次内循环[1, 3, 6, 25, 8, 10, 15]第3次内循环[1, 3, 6, 8, 25, 10, 15]第4次内循环[1, 3, 6, 8, 10, 25, 15]第5次内循环[1, 3, 6, 8, 10, 15, 25]第0次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第2次内循环[1, 3, 6, 8, 10, 15, 25]第3次内循环[1, 3, 6, 8, 10, 15, 25]第4次内循环[1, 3, 6, 8, 10, 15, 25]第1次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第2次内循环[1, 3, 6, 8, 10, 15, 25]第3次内循环[1, 3, 6, 8, 10, 15, 25]第2次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第2次内循环[1, 3, 6, 8, 10, 15, 25]第3次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第4次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第5次外循环[1, 3, 6, 8, 10, 15, 25]最后的结果[1, 3, 6, 8, 10, 15, 25]
我们可以看到，第0次外循环，已经将25放在了最右边，第1次外循环确定把15放到最右边，这样从右往左，从大到小，这就是完整的冒泡排序。
冒泡排序的时间复杂度是：假设被排序的数列中有N个数。遍历一趟的时间复杂度是，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度。
冒泡排序是稳定的算法：它满足稳定算法的定义；所谓算法稳定性指的是对于一个数列中的两个相等的数a[i]=a[j]，在排序前,a[i]在a[j]前面，经过排序后a[i]仍然在a[j]前，那么这个排序算法是稳定的。
下面是Java冒泡排序代码。
public class Sort {  public static void sort() {    Scanner input = new Scanner(System.in);    int sort[] = new int[10];    int temp;    System.out.println("请输入10个排序的数据：");    for (int i = 0; i 
JavaScript冒泡排序代码。
function sort(arr) {    for (var i = 0; i  arr[j + 1]) {                var temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }    }    return arr;}//举例如下var arr = sort([1, 7, 4, 97, 23, 45]);console.log(arr);
❝
本文已收录 GitHub，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。
❞
Reference
[1]
传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100

十个数，实现正序排序功能。
冒泡排序法
#include<iostream>
using namespace std;

int main()
{
	int s[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int i, j, temp;
	for (i = 0; i < 9; i++)//注意数组下标从s[0]开始
	{
		for (j = 0; j < 10-1-i; j++)
		{
			if (s[j] > s[j + 1])
			{
				temp = s[j];
				s[j] = s[j + 1];
				s[j + 1] = temp;
			}
		}
	}
	cout << "The sort numbers:" << endl;
	for (i = 0; i < 10; i++)
	{
		cout << s[i] << "";
	}
	return 0;
}
其中i=0时： j从0开始a[0],a[1]比较大小，把其中的较大者给a[1],然后j++,a[1]和a[2]再比较，再把两者中的较大者给a[2],这样a[0],a[1],a[2]中的最大者已经交换到a[2]中，这个过程继续，直到j=10-i-1=9,这样 a[9]中的为10个数中的最大数。 
然后i=1时: 由于最大数已找到并放到a[9]中，所以这一次循环j最大只需到10-i-1=8，即a[8]即可，再次从j=0开始a[j]和a[j+1]两两比较交换，最后次大数放到a[8]中 
然后i++,继续... 
当i=9时已经过9次两两比较完成所有排序，i<9不再成立退出比较。 
对于n个数，只需要进行n-1次外循环的两两比较就完成排序。 
至于按降序排列只需将if(a[j]>a[j+1])改为if(a[j]<a[j+1])即可。 

排序算法：

排序基础知识和总结
插入排序：直接插入排序、二分插入排序、希尔排序
交换排序：冒泡排序、快速排序
快速排序：简单选择排序、堆排序
归并排序：2-路归并排序
基数排序
排序算法详细代码



6. 基数排序
也叫桶排序或箱排序
6.1.1 算法分析和思路


基本思想：

分配+收集

分配：设置若干个箱子，将关键字为k的记录放入第k个箱子；
收集：按序号将非空的连接。



数字是有范围的，均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百…进行排序。


注：

算法思路及详细过程可参考后续的示例和代码及代码流程图！
6.1.2 算法示例

6.1.3 算法代码
//基数排序算法
void RadixSort(SqList &L){
    int len = L.length;
    int maxBitNum = MaxBitNum(L);//获取数据的最大位数
    int *count = new int[10];//计数器，关键字取值范围10个值：0~9
    ReadType *tempNums = new ReadType[len];//新建辅助数组tempNums
    int radix = 1;//基数初始为1，即表示个位
    int i, j;
    int k;
    //进行maxBitNum次排序
    for(i = 1; i <= maxBitNum; i++){
        //每次分配前清空计数器
        for(j = 0; j < 10; j++){
            count[j] = 0;
        }
        //统计每个桶中的记录数
        for(j = 1; j <= len; j++){//有哨兵位，索引从1开始
            k = (L.nums[j].key / radix) % 10;
            count[k]++;
        }
        //将tempNum中的位置依次分给每一个桶
        for(j = 1; j < 10; j++){
            count[j] = count[j-1] + count[j];
        }
        //将所有桶中记录依次收集到tempNum中
        for(j = len; j >= 1; j--){//有哨兵位，索引从1开始
            k = (L.nums[j].key / radix) % 10;
            tempNums[count[k] - 1] = L.nums[j];
            count[k]--;
        }
        //将临时数组中的值复制到L.nums[]中
        for(j = 0; j < len; j++){
            L.nums[j+1] = tempNums[j];
        }
        radix *= 10;
    }
}
//辅助函数，求关键字个数，即求数据的最大位数
//先求出最大数，再求出其位数
int MaxBitNum(SqList &L){
    KeyType maxData = L.nums[1].key;
    //先求出最大数
    for(int i = 2; i<= L.length; i++){
        if(L.nums[i].key > maxData){
            maxData = L.nums[i].key;
        }
    }
    //再求出最大位数，即最大数的位数
    int maxBitNum = 1;
    while(maxData >= 10){
        maxData /= 10;
        maxBitNum++;
    }
    return maxBitNum;
}

排序算法详细代码

代码流程图：



6.1.4 算法性能分析

时间复杂度：$O(k*(n+m))$

k：关键字个数，决定了需要分配多少趟；
m：关键字取值范围为m个值。桶的个数，有多少个桶，收集时就要收集多少次；
n：分配时，每趟要往桶里扔多少个元素。
每一趟都需要扔n个，收m次，总共需要k趟


空间复杂度：$O(n+m)$
是一种稳定的排序方法

对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？
本系列文章就尝试解决这个问题。
研读那些排序算法，细品它们的名字，其实都很贴切。
比如基数排序，就是按照数字的“位”来排序。
位，是进位的位，比如十进制数的基数是10，就可以按照个十百千万等位来排序。


上图演示了基数排序算法的总体流程。先按个位从小到大排序，然后再按十位、百位排序。只要排序算法是稳定的，那么最后整体就是有序的。为了方便看出数字的每一位具体是多少，这里对位数少的数字进行了左边补0。
可见该算法的核心在于选择的排序算法是稳定的。
排序是稳定的意思说，排序后，其相同元素的相对顺序并不会改变。比如19和18，按个位排，9大于8，因而顺序是18、19。二者十位上的数值相等（都为1），如果此时排十位的算法是不稳定的话，会可能出现19在前，18在后这样的情形，那么之前先按个位排序的意义将不复存在了。
了解了整体原理后，我们来一步步写出它。
首先，如何判断数字最长有多少位？遍历一遍就能解决：
let array = [666, 520, 36, 49, 9, 600, 8, 502, 998, 32]
let maxLength = 0
for (let v of array) {
  let length = String(v).length
  if (length > maxLength) {
    maxLength = length
  }
}
console.log(maxLength) // 3
复制代码

这里我们取巧，通过转化为字符串，来获取每个数字的位数。也可以通过，找到最大数，用它不断除以10来获取位数。
另一个问题是：如何获取数字某位上的数字呢？
比如获取36的百位上的数字，通过转字符串后，补0取第一位：
String(36).padStart(maxLength, '0')[0] // 0
复制代码

有了上述铺垫后，整体逻辑就有了：
for (i = 0; i < maxLength; i++) {
  array = sort(array, i)
  console.log(array)
}
复制代码

对数组排序三次，每一次的输出作为下一次的输入。其中sort方法只要是稳定的排序算法即可。
这里推荐使用桶排序算法，下面我们简单过一遍。
由于个位上的数值范围是从0到9，需要构建10个桶：
let buckets = []
for (let i = 0; i < 10; i++) {
  buckets.push([])
}
复制代码

然后把按个位上的数值把元素分别分到这些桶里：
for (let v of array) {
  let pad = String(v).padStart(maxLength, '0')
  let num = pad[maxLength -1]
  buckets[num].push(v)
}
console.log(buckets)
// [ [ 520, 600 ], [], [ 502, 32 ], [], [], [], [ 666, 36 ], [], [ 8, 998 ], [ 49, 9 ] ]
复制代码

因为桶的区间大小特殊（为1），因此桶内部不需再排（有点计数排序的意味）。直接按顺序输出每个桶的元素即可：
let result = []
for (let bucket of buckets) {
  result.push(...bucket)
}
console.log(result)
// [ 520, 600, 502, 32, 666, 36, 8, 998, 49, 9 ]
复制代码

sort方法完整代码是：
function sort(array, index) {
  let buckets = []
  for (let i = 0; i < 10; i++) {
    buckets.push([])
  }
  for (let v of array) {
    let pad = String(v).padStart(maxLength, '0')
    let num = pad[maxLength - 1 - index]
    buckets[num].push(v)
  }
  let result = []
  for (let bucket of buckets) {
    result.push(...bucket)
  }
  return result
}
复制代码

至此，基数排序原理和实现已经说完了。查看完整代码：codepen。
需要补充的是，基数排序也有从高位开始遍历的。另外，用它也可以轻松实现字典排序。
这里总结一下，基数排序的性能，取决于内部排序算法的选择。如果使用桶排序，时间复杂度为O(k*n)，其中k为最大元素的位数，一般都是很小数。
基数排序，要做到能分分钟手写出来，是需要掌握其排序原理的。核心是使用稳定排序从低位逐次排列到高位，一旦理解就容易写出来，不需要死记硬背的。
希望有所帮助，本文完。
服务推荐

蜻蜓代理
代理ip
微信域名检测
微信域名拦截检测
微信域名在线拦截检测工具
微信域名在线批量拦截检测工具