简单讲讲：我估计能打开我这篇文章的朋友都应该知道冒泡排序吧。我就不那么系统官方的定义了。我喜欢用实例说明，比如给你一个列表L，如下：
[2, 4, 3, 9, 7, 5, 1, 8, 6]
首先我们将2和4比较，4比较大，就保持不变；4和3比较，4比较大，4和3交换位置如下：
[2, 3, 4, 9, 7, 5, 1, 8, 6]
然后4和9比较，保持不变；9和7比较，9大，9和7交换位置，如下：
[2, 3, 4, 7, 9, 5, 1, 8, 6]
然后9和5比较，9大，9和5交换位置，如下：
[2, 3, 4, 7, 5, 9, 1, 8, 6]
9和1比较，9大，9和1交换位置，如下：
[2, 3, 4, 7, 5, 1, 9, 8, 6]
9和8比较，9大，9和8交换位置，如下：
[2, 3, 4, 7, 5, 1, 8, 9, 6]
9和6比较，9大，9和6交换位置，如下：
[2, 3, 4, 7, 5, 1, 8, 6, 9]
至此，经过第1轮“冒泡”之后，列表中最大的数字“9”到了它该到的位置。
以此类推，那么要经过多少轮才能把这个列表中的元素全都排完呢？
如果你不知道，我们可以用一个长度为3的列表来看看：
[3, 2, 1]
① 3 > 2 => [2, 3, 1]; 3 > 1 => [2, 1, 3]; 3到此排完了
② 1 < 2 => [1, 2, 3]；2到此排完了，剩下一个1，没有元素和它比较了，于是排序结束。
观察上面这个例子，3个元素列表，只需要经过2轮就能排完了，因为剩最后2个元素的时候，它们互相比较一下，这2个元素的顺序就都好了，所以当一个列表的长度为len(L)时，只需要经过len(L)-1轮，排序就结束了，于是冒泡法的第一行代码就出来了：
for i in range(len(L)-1): #只需要经过len(L)-1轮，排序即结束，i代表每一轮比较
下面再看看在每轮比较中，一共比较了多少次呢？拿刚开始的列表举例，
[2, 4, 3, 9, 7, 5, 1, 8, 6] ，经过第1轮后，这个列表变为了
[2, 3, 4, 7, 5, 1, 8, 6, 9]，下一轮再比较，比到6就好了，不需要再和9比较了，对吧！所以我们发现这个规律：
第1轮，比较了len(L) - 1 = 8次；
第2轮，比较了len(L) - 2 = 7次；
第N轮，比较了len(L) - N次，于是代码又来一行：
for j in range(1, len(L)-i): #这里面的i就是当前所在的轮数，j表示每一轮要遍历的元素
#这里面range(1, len(L)-i)也可以写成range(0,len(L)-i-1),反正表示的长度是一样的，区别在于
#j的第一个值是0还是1。是0时，先得到第一个元素；是1时，先得到第二个元素。
得到遍历的元素之后，我们就要比较了，相邻的两个元素，如果前面的大于后面的，就让它们的值交换，让大的往后走，一直到这个列表中最大的元素走到列表的最后面，于是：
if L[j-1] > L[j]: # 假设当j=1时，这里是第一个元素和第二个元素比较
L[j-1], L[j] = L[j], L[j-1] # Python常用的交换变量写法
好了，我们的冒泡排序就写完了。觉得很短吗？没错，实际逻辑代码就4行。
标配代码：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)-1): #只需要经过len(L)-1轮，排序即结束，i代表每一轮比较
for j in range(1, len(L)-i):#这里面的i就是当前所在的轮数，j表示每一轮要遍历的元素
if L[j-1] > L[j]: # 假设当j=1时，这里是第一个元素和第二个比较
L[j-1], L[j] = L[j], L[j-1] # Python常用的交换变量写法
print(L)
还可以写成如下形式，但后续的代码都以上面的为主：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)-1):
for j in range(0, len(L)-i-1): #和上面一样的，只是起始索引变了
if L[j] > L[j+1]: #当j=0时，这里是第一个元素和第二个比较
L[j], L[j+1] = L[j+1], L[j]
print(L)
以上就是冒泡排序的最基础的代码。
完了？还有没有可优化的地方？面前的面试官皱着眉头对你说。你必须回答：有！
想象有这么几种特殊情况情况：
第一种：当遍历一轮发现没有元素交换时，排序即可结束。
[2, 1, 4, 3, 6, 5, 8, 7, 9] 当待排序列表为这个时，经过第1轮排序，就变成了
[1, 2, 3, 4, 5, 6, 7, 8, 9] 此时列表已经完全排好序了，但是呢，程序不知道，还在准备进入第2轮排序，前后比较，1和2比，2和3比，一直到7和8比完，一个也没交换，然后紧接着又要进入第3轮了！！停，在这块是不是可以优化下，我们发现在第2轮比较一遍后，没有任何值发生交换，那是不是可以说明这轮比较的所有元素全都是有序的了，所以才不需要交换。那我们在程序中可以添加个代表是否交换的变量，不交换时值为False，如果交换了就置为True。最后每轮结束，如果值为False就说明这轮没有发生交换，没有发生任何交换就直接结束循环，退出程序，因为这个列表已经排序好了；如果值为True就说明这轮发生交换了，需要进入下一轮，但在进入下一轮遍历前，需要先将已经置为True的变量重新设置为False。如果你想明白了，请看代码：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)-1):
swap = False #每一轮都要重置一次swap的值，所以要写在这边
for j in range(1, len(L)-i):
if L[j-1] > L[j]:
swap = True #每次交换就改变swap的值
L[j-1], L[j] = L[j], L[j-1]
if not swap: #当swap为False时，退出循环
break
print(L)
第二种：当列表尾部部分元素提前完成顺序时，不再进行比较。
[4, 2, 3, 5, 1, 6, 7, 8, 9] 当待排序列表为这个时，在第1轮排序中，当5和1交换位置后，
[2, 3, 4, 1, 5, 6, 7, 8, 9] 后面的数已经是有序的了，不再需要交换了，最大的数9归位，第二大的数8也已经归位，但程序进入第二轮后，继续逐个比较并确保8在倒数第二个位置上。其实，在第二轮中只需要比到5的位置就不需要再比较了（或者有个直接的办法就是直接跳过第二三四五轮）。我们可以记录每次交换时最后的那个索引，因为自这个索引之后就没有发生交换了，下次比较的时候只到这个索引，再往后就不比较了。具体代码如下：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
maxindex = len(L) #索引的初始值应为原先下面len(L)-i的第一个值，即len(L)
for i in range(len(L)-1):
for j in range(1, maxindex): #将之前的len(L)-i替换为上次最后赋值的索引ordindex
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
maxindex = j #记录索引，多次循环过后，ordindex存储的是最后被赋值的索引
print(L)
第三种：鸡尾酒排序，双向比较交换，无交换时排序结束。
[2, 3, 4, 5, 6, 7, 8, 9, 1] 当待排序列表为这个时，在第1轮排序中，9和1交换位置后，
[2, 3, 4, 5, 6, 7, 8, 1, 9] 发现前面全都排好了，就差个最小值1，如果是按照冒泡算法，第2轮又要经过N-2次比较，最后1和8交换位置，然后又进入第3轮……这时我们发现现在已经在做无用功了，要是经过第1轮之后，第2轮，直接把1这个数一直向前移，一直移到最前面，那样的话，经过两轮顺序就排好了，这时候配合第一种优化，排好之后直接结束排序就好了，那样会省很多比较。我们观察这个列表的特点，普通冒泡法之所以要经过这么多步骤主要是因为一个列表中最小的数字太靠后了，它没有办法尽快满足第一种优化方案而尽早退出，所以你也可以理解成这个第三种优化是为了更好的实现第一种优化。基于这种特别情况，我们可以采取双向排序的方式，我每次排一个最大值，然后再排一个最小值，让小的值尽量提前往前走，这样有可能提前结束排序。那么这种优化算法有一种专有的名称叫“鸡尾酒排序”。注意，这种优化主要是针对小的值比较靠后的列表。具体代码实现如下：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
for i in range(len(L)//2):
swap = False
for j in range(i+1, len(L)-i): #起始和结尾都在发生变化
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
for k in range(len(L)-i-2,i,-1): #倒序来进行小值往前走的操作
if L[k-1] > L[k]:
L[k-1], L[k] = L[k], L[k-1]
swap = True #只需将交换变量放在最后面的循环即可
if not swap:
break
print(L)
#以上代码是 第一种优化+双向交换 = 鸡尾酒排序
目前能想到的优化就这么多了，最后把 第二种和第三种(已包括第一种)再融合一下，凑成
最终优化版本：
L = [2, 4, 3, 9, 7, 5, 1, 8, 6]
minindex = 0
maxindex = len(L)
for i in range(len(L)//2):
swap = False
for j in range(minindex+1, maxindex):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
maxindex = j
for k in range(maxindex-1, minindex, -1):
if L[k-1] > L[k]:
L[k-1], L[k] = L[k], L[k-1]
minindex = k #当前半段提前完成排序时也不用再比较了
swap = True
if not swap:
break
print(L)
附加说明：上面那三种优化及最终优化版都只是针对特殊情况的，那如果没有特殊情况，其实效率和普通冒泡法基本上是一样的，后面我会做个测试，看看优化后的版本性能到底性能会好多少。冒泡排序的时间复杂度为O(n²)，空间复杂度为O(1)，这些是不变的，即使优化后也是如此。但是可以再细算一点，就拿最标配代码看，
3个元素的列表，要比较2+1=3次；
4个元素的列表，要比较3+2+1=6次；
5个元素的列表，要比较4+3+2+1=10次；
N个元素的列表，要比较N(N-1)/2次（找规律应该会吧）。
所以这个时间复杂度O(n²)是从
 这里来的，算复杂度的时候把系数及低项数去掉了，但是如果两个算法时间复杂度都是O(n²)，那么他们的系数的不同就会影响到他们的计算时间了。比如有10个元素的列表，一个比较了100(n²)次，一个比较了50(1/2n²)次，他们的速度还是有差别的。然后再说一下稳定性，一般来说冒泡排序是稳定的，因为相同的元素是直接跳过的，具体对应的代码为【if L[j-1]> L[j]:】，这里是前面比后面大才交换，前面和后面相等或者小于是不交换的，这就保证了冒泡排序的稳定性，但是如果我把这行代码改成 【if L[j-1] >= L[j]:】那它就不稳定了，因为相等的时候，你也把它交换了，这时你也可以说它是不稳定的。但是完全没必要这么做，因为这做了无用功，相等你还交换啥。所以一般情况下，冒泡排序是稳定的排序。
优化测试：我们对上面的标配版冒泡排序和优化版冒泡排序做个测试比较，分别选取元素个数为20、200、2000的随机列表。
import timeit #一个时间测试模块，用来计算一段代码执行num次的执行时间
import random
def nom_sort(L): #标配版函数
for i in range(len(L)-1):
for j in range(1, len(L)-i):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
return L
def opt_sort(L): #优化版函数
minindex = 0
maxindex = len(L)
for i in range(len(L)//2):
swap = False
for j in range(minindex+1, maxindex):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
maxindex = j
for k in range(maxindex-1, minindex, -1):
if L[k-1] > L[k]:
L[k-1], L[k] = L[k], L[k-1]
minindex = k
swap = True
if not swap:
break
return L
res = []
number = 200 # 20, 200, 2000
M = list(range(0,number))
for i in range(1000): #循环次数 10000 1000 100
random.shuffle(M) #随机打散
N = M[:]
res.append([timeit.timeit('nom_sort(M)', number=1, globals=globals()),
timeit.timeit('opt_sort(N)', number=1, globals=globals())] )
#分别执行两个函数，计算执行number次的总时间，为保证稳定性和公平性用for循环测试多次
print('%.8f%.8f' % tuple([sum([i[j] for i in res])/len(res) for j in range(2)]))
#计算两个函数的各自平均秒数
### output ###
元素数 循环次数 标配版 优化版 提高效率
20 10000 0.00005097 0.00004247 16.7 %
200 1000 0.00404639 0.00338712 16.3 %
2000 100 0.46240990 0.40061400 13.4 %
总结：根据上面测试分析，优化后的代码大概效率会提升15%左右，而且随着元素数的增加，效率应该会逐渐减小。好了，咱们的冒泡排序差不多就讲完了。下一篇：选择排序。

做软件开发，需要了解或是掌握一些常用的算法，排序，也是一种算法。
 
之前嵌入式软件接触的算法不多，但随着科技的进步，常用的通信与控制，相对变的简单化了。除了掌握底层驱动，上层的数据结构与算法，面向对象的编程思路，都是需要不断的掌握起来的，也就是说，要具有与时俱进的心态，有终身学习的打算。
 
最近手写了冒泡法排序的算法，虽然思路是有的，发现了很多的低级的问题。
 
（1）计算机编程，习惯了使用IDE，使用变量或是函数名自动补全，代码的编写除了通过搜索获取代码，改下格式与程序结构，很少从头到尾的写。
 
（2）一般代码，很少一次性写对，变量名称，函数名称，数据类型，程序逻辑，测试代码，可能是不断的调试与修改。
 
 
 
手写的代码，没有上机验证，无法直接获取输出结果。需要通过理解，大体上判断逻辑上是否清晰，逻辑是否有误。所以，基本功还是要打一打。我对自己手写的代码，写完发现逻辑不正确，修改后，勉强能工作，并且还没有考虑异常情况。
 
当然，这些不足，都是自己平时不太注重细节造成的，虽说世界在剧烈的变化，心态还是要稳，一步步把框架搭好，把细节处理好，这就是人生的高楼的建设过程。
 
 
 
冒泡排序的主要算法，需要考虑：
 
（1）排序的是什么数值，有符号还是无符号，一般用int型数组（有符号）足够了。
 
（2）使用VS2019，发现直接在数组里初始化一个负数，会被自动转换成一个正数，因此，负数使用括号括起来，-3使用(-3)。
 
（3）排序，有两种方式，从小到大的排序，从大到小的排序。
 
（4）两个循环，最外层的需要整个数组遍历，内层的，不用全部遍历，因为每次循环，已经把最小的或是最大的，推到了尾部。
 
（5）实际了，这种排序，不需要额外的输出数组，直接在原数组上也可以工作，只是，破坏了原来的输入数组。
 
（6）如果是int型的数组，不要直接memcpy（字节复制）。
 
可能还有其他的注意事项
 
 
 
一种实现如下：
 
// bubble_sort_t0.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#define MAX_BUF_NUM		20 //最大数组的个数

void bubble_sort_high(int32_t * input_buf, uint32_t input_len, int32_t * output_buf)
{
	uint32_t i, j;
	int32_t swap_val = 0;
	for (i = 0; i < input_len; i++) //只为了不影响输入的数组
	{
		output_buf[i] = input_buf[i];
	}

	for (i = 0; i < input_len; i++) //外循环，整个数组遍历
	{
		/* （1）相邻两个数据比较，把小的往后推，这样尾端的数值是最小的。
		   （2）尾端不再重复参与比较。*/
		for (j = 0; j < input_len - i - 1; j++)
		{
			if (output_buf[j] < output_buf[j + 1])
			{
				swap_val = output_buf[j];
				output_buf[j] = output_buf[j + 1];
				output_buf[j + 1] = swap_val;
			}
		}
	}
}

void bubble_sort_low(int32_t* input_buf, uint32_t input_len, int32_t* output_buf)
{
	uint32_t i, j;
	int32_t swap_val = 0;
	for (i = 0; i < input_len; i++) //只为了不影响输入的数组
	{
		output_buf[i] = input_buf[i];
	}

	for (i = 0; i < input_len; i++) //外循环，整个数组遍历
	{
		/* （1）相邻两个数据比较，把大的往后推，这样尾端的数值是最大的。
		   （2）尾端不再重复参与比较。*/
		for (j = 0; j < input_len - i - 1; j++)
		{
			if (output_buf[j] > output_buf[j + 1])
			{
				swap_val = output_buf[j];
				output_buf[j] = output_buf[j + 1];
				output_buf[j + 1] = swap_val;
			}
		}
	}
}

void print_buf(int32_t * buf, uint32_t buf_len) //打印buffer
{
	uint32_t i = 0;
	printf("\n---------------\n");
	for (i = 0; i < buf_len; i++)
	{
		printf(" %d", buf[i]);
	}
	printf("\n---------------\n");
}

int main()
{
	int32_t input_buf[MAX_BUF_NUM] = { 1,3,33,5,79,66,88,22,(-3),102,105,(-5),(-8),(-33),(-112),(-9),(-11),(-42),333,234};
	int32_t output_buf[MAX_BUF_NUM] = { 0 };
	printf("\n------sort high to low ---------\n");
	bubble_sort_high(input_buf, MAX_BUF_NUM, output_buf); //高到低排序
	print_buf(output_buf, MAX_BUF_NUM);
	printf("\n------sort low to high ---------\n");
	bubble_sort_low(input_buf, MAX_BUF_NUM, output_buf); //低到高排序
	print_buf(output_buf, MAX_BUF_NUM);
}
 
运行效果如下：
 
 
另外：纸上的东西，真正的要输入到计算机，实际运行一下，才能掌握其原理，才能收获更多。
 
纸上得来终觉浅。
 
任何事情，都是如此，则简单的事情认真做，可以成为专家。
 
 

编写函数，实现冒泡排序算法。
 
def bubble(num_list):
    for i in range(len(num_list)):
        for j in range(i):
            if num_list[j] > num_list[i]:
                num_list[j], num_list[i] = num_list[i], num_list[j]
    return num_list
 #冒泡排序的函数代码
 
完整代码
 
def bubble(num_list):
    for i in range(len(num_list)):
        for j in range(i):
            if num_list[j] > num_list[i]:
                num_list[j], num_list[i] = num_list[i], num_list[j]
    return num_list
 
list = [2,4,7,87,32,90,11,0,577]
print(list)
print(bubble(list))
 

首先得懂的冒泡排序
 
这是一个很简单的算法，
 int a[5] ={6,4,3,2,5};
 6先和4比，如果大于则交换位置
 {6,4,3,2,5}——>{4,6,3,2,5}；
 {4,6,3,2,5}——>{4,3,6,2,5}；
 {4,3,6,2,5}——>{4,3,2,6,5}；
 {4,3,2,6,5}——>{4,3,2,5,6};
 一次外循环结束；
 …
 然后6又和三比，就这样循环得到{4,3,2,5，6}，最大的来到了最后 ，然后 又从4开始向后比 如此循环。但6已近是最大，为了优化减少运算次数，所以内层循环减一，就是4 比到5 就结束
 
int i = 0;
int j = 0;
for(i = 0; i < 5; i++)
{
   for(j = 0; j < 5 - 1 -i; j++)
   {
      if(a[j] > a[j+1])
      {
         int tmp = a[j];
           a[j]  = a[j+1];
           a[j+1] = tmp;
      }
   }
}
 
然后就是自己实现qsort函数了
 
qsort()函数有四个参数；qsort(void *base,size_t num, size_t width ,int (*p)(const void ,const void )
 提示一下 size_t 是 无符号整型 ,int (*p)(const void ,const void 是函数cmp的函数指针；
 
想利用指针来交换变量，自己写一个函数叫swap(),具体需要的参数等下请看代码理解；
 
你写一个函数，你并不知道用户给你传的是int char double 等类型，所以你就没办法确定＋1时候的所跳过的步长，如果你一个一个的判断，那就有永远写不完的代码，所以只能一劳永逸，用字节来交换，只需要用sizeof（）函数确定占几个字节；把初始类型强行转化成char类型就可以；j*width 到 （j+1）*width 就是需要跳过的下一个变量；
 swap() 交换都是一个字节，一个字节交换，
 
int cmp(const void*a, const void*b)
{
	return *(int *)a - *(int *)b;
	//  详情可用msdn查看
	//可以自己写，亦可以自己写
	//下面是int类型数组，所以强制类型转化成整型
	//相似如果是double，那就强制类型转化double
}

void swap(char *p1, char *p2, int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{    //因为不知道是什么类型，size表示需要交换的字符
	    //几个字节，所以强制类型转化成char型，一个字节一个
	    //字节交换
		char tmp = *((char *)p1 + i);
		*((char *)p1 + i) = *((char *)p2 + i);
		*((char *)p2 + i) = tmp;
	}
}

void my_qsort(void *base,size_t  num, size_t width ,int (*p)(const void *,const void* ))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < num; i++)
	{
		for (j = 0; j < num - i-1; j++)
		{   // j*wide是步长， width表示你这个类型所占的
		    // 字节大小  ，因为强制类型转换成int类型
		    //所以都是按字节来算；
			if (cmp((char *)base + j*width, (char *)base + (j + 1)*width)>0)
				swap((char *)base + j*width, (char *)base + (j + 1)*width, width);
		}
	}

}




int main()
{
	int a[10] = { 0 };
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		a[i] = i;
	}
  //调用自己编写的函数，10是元素个数。
	my_qsort(a, 10, sizeof(int), cmp);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);  
	}
	system("pause");
	return 0;
}


## 如有不足，请指出........
email ——1094185589@qq.com