本文共 5136 字，大约阅读时间需要 17 分钟。

冒泡排序

冒泡排序 Bubble_Sort，是极为简单的一种排序算法。虽然效率差一点，但好在具有结构简单，容易理解，易于操作等优点。冒泡排序就是把小的元素往前调或者把大的元素往后调。在相邻的两个元素间比较，交换也发生在这两个元素之间。

冒泡排序是一种稳定排序算法，在排序后相同元素的前后顺序并没有改变。

相比于传统的冒泡排序，平均时间复杂度为O(n2)，最好的时间复杂度为2，是一种效率不高的的排序。但胜在使用方便，于是便有了一些对于冒泡的优化算法。

这里，我总结了以下两种优化方案：

1. 使用标记，在冒泡排序有序后提前退出排序
2. 在两个方向上来回进行进行冒泡，使待排数列每次缩短两步

为了不使程序太过复杂，这里我们采用类似于波动曲线的一种方式进行方案二算法的设计。另外方案二与方案一也可以相互结合使用。三种排序算法特点如下所示：

测试三种排序效率

这里我们直接开始测试三种排序的效率，通过以下代码测试最终的优化排序方案，最后与标椎库<stdlib.h>中提供的qsort() 函数进行比较。

辅助函数与主程序代码部分

#include 
   
    #include 
    
     #include 
     
      // 交换两整型变量void Swap_Int(int* pa, int* pb){   	int tmp = *pa;	*pa = *pb;	*pb = tmp;}// 输出arr数组中start下标~stop下标void Show_Ar(int* arr, int indexStart, int indexStop){   	for (int i = indexStart; i < indexStop; ++i)	{   		printf("%d   ", arr[i]);	}	printf("\n");}     /* 三种冒泡排序 */void Bubble_Sort1(int *arr, int n);void Bubble_Sort2(int* arr, int n);void Bubble_Sort3(int* arr, int n);// 测试各排序算法的速度void Speed(void (*pFun)(int *, int ));int main(){   	Speed(Bubble_Sort1);	Speed(Bubble_Sort2);	Speed(Bubble_Sort3);	return 0;}
     
    
   

测试三种排序的速度方法

// 测试排序算法的速度void Speed(void (*pFun)(int*, int)){   	// 测试对十万个数字的排序	const int n = 100000;	// 用于测试排序功能是否正常	//int arr[n] = { 67,45,90,78,89,23,34,100,12,56 };	int arr[n];	// 随机赋值	srand((unsigned)time(NULL));	for (int i = 0; i < n; ++i)	{   		arr[i] = rand() % 1000;	}	// 定义计时器	clock_t start, stop;	// 由于数据过多，这里输出排序后的 10000——10020	start = clock();	(*pFun)(arr, n);	Show_Ar(arr, 10000, 10020);	stop = clock();	// 输出三种排序所用时间	printf("排序用时 %d 秒\n", (stop - start) / CLOCKS_PER_SEC);}

三种冒泡排序方法

// 常规的冒泡函数void Bubble_Sort1(int* arr, int n){   	for (int i = 0; i < n - 1; ++i)	{   					for (int j = 0; j < n - i - 1; ++j)		{   			if (arr[j] > arr[j + 1])			{   				Swap_Int(&arr[j], &arr[j + 1]);			}		}	}}// 优化——使用标记void Bubble_Sort2(int* arr, int n){   	for (int i = 0; i < n - 1; ++i)	{   			// 优化：判断有序		int flg = 0;		for (int j = 0; j < n - i - 1; ++j)		{   			if (arr[j] > arr[j + 1])			{   				Swap_Int(&arr[j], &arr[j + 1]);				flg = 1;			}		}		if (flg == 0) break;	}}// 优化——正反双向排序void Bubble_Sort3(int* arr, int n){   	for (int i = 0; i < n - 1; ++i)	{   	// 优化：判断有序		int flg = 0;		// 正着跑		int j;		for (j = i; j < n - i - 1; ++j)		{   			if (arr[j] > arr[j + 1])			{   				Swap_Int(&arr[j], &arr[j + 1]);				flg = 1;			}		}		if (flg == 0) break;		//　反着跑		for (int k = j - 1; k > i; --k)		{   			if (arr[k] < arr[k - 1])			{   				Swap_Int(&arr[k], &arr[k - 1]);				flg = 1;			}		}		if (flg == 0) break;	}}

测试三个冒泡排序对10万个数据进行排序后的运行结果：

第一次测试截图：

第二次测试截图： 第三次测试截图：

qsort 排序算法测试

qsort() 是C标椎库中自带的一种快速排序算法，排序速度相当快，并且是一种泛型的排序算法。下面是 qsort() 的用法。

// 
   
    void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))base -- 指向要排序的数组的第一个元素的指针。nitems -- 由 base 指向的数组中元素的个数。size -- 数组中每个元素的大小，以字节为单位。compar -- 用来比较两个元素的函数。
   

上图为三种排序的执行结果，接下来使用 qsort() 函数进行排序测试。这里也使用Speed() 函数对测试排序的算法进行封装。

#include 
   
    #include 
    
     #include 
     
      int Cmp_Int(const void* a, const void* b){   	return (*(int*)a - *(int*)b);}// 输出arr数组中start下标~stop下标void Show_Ar(int* arr, int indexStart, int indexStop){   	for (int i = indexStart; i < indexStop; ++i)	{   		printf("%d   ", arr[i]);	}	printf("\n");}void Speed();int main(){   	int n = 3;	while (n--)	{   		Speed();	}	return 0;}// 测试排序算法的速度void Speed(){   	// 测试对十万个数字的排序	const int n = 100000;	int arr[n];	// 随机赋值	srand((unsigned)time(NULL));	for (int i = 0; i < n; ++i)	{   		arr[i] = rand() % 1000;	}	// 定义计时器	clock_t start, stop;	// 由于数据过多，这里输出排序后的 10000——10020	start = clock();	qsort(arr, n, sizeof(int), Cmp_Int);	Show_Ar(arr, 10000, 10020);	stop = clock();	// 输出排序所用时间	printf("排序用时 %d 秒\n", (stop - start) / CLOCKS_PER_SEC);}
     
    
   

第一次排序结果：（由于排序速度过快，不到1秒中就完成了十万个数据的排序）

由于我们计算机栈区的大小限制，不便于测试更大的数据。所以我们改从堆区申请一百万数据进行排序。要知道栈由系统自动分配，速度较快，堆区由程序猿手动申请，且操作效率要慢于栈区。

修改源码，其中///***中内容为修改处

#include 
   
    #include 
    
     #include 
     
      #include 
      
       int Cmp_Int(const void* a, const void* b){   	return (*(int*)a - *(int*)b);}// 输出arr数组中start下标~stop下标,以step步长					//增加步长参数void Show_Ar_Step(int* arr, int indexStart, int indexStop, int step){   	for (int i = indexStart; i < indexStop; i+=step)	{   		printf("%d   ", arr[i]);	}	printf("\n");}///void Speed();int main(){   	int n = 3;	while (n--)	{   		Speed();	}	return 0;}// 测试排序算法的速度void Speed(){   	// 测试对一千万个数字的排序	const int n = 10000000;							////	int* arr = (int*)malloc(sizeof(int) * n);			//堆区申请	assert(arr != NULL);/	// 打印arr数组的容量	printf("共有数据 %d 个\n", n );						// 随机赋值	srand((unsigned)time(NULL));	for (int i = 0; i < n; ++i)	{   		arr[i] = rand() % 1000;	}	// 定义计时器	clock_t start, stop;	// 由于数据过多，这里输出排序后的 100000——500000,步长为10000	start = clock();	qsort(arr, n, sizeof(int), Cmp_Int);	Show_Ar_Step(arr, 100000, 300000,10000);		//	stop = clock();	// 输出排序所用时间	printf("排序用时 %d 秒\n", (stop - start) / CLOCKS_PER_SEC);}
      
     
    
   

对一千万数据进行排序后的输出结果：

可以看到，qsort() 排序真的是非常的快，无论对冒泡排序怎样的优化之间的差距还是非常的大。

以下，是本次测试的数据对比：

冒泡排序：  十万数据    平均用时73秒   (😭完败) 优化冒泡：  十万数据    平均用时64秒  （😛有效果） qsort排序：  千万数据    平均用时 3秒  （😋完胜）

---

虽然，C标椎库中为我们实现了排序算法，我们也不能太过依赖标椎库。每一种算法都有他独特的思想在其中，在平时的练习中也要多加练习其他的排序算法。另外，qsort是基于快排优化而来，下次我们可以通过优化快排和qsort进行测试比较。

附：C语言泛型编程——泛型冒泡排序：

转载地址：http://amio.baihongyu.com/