比较冒泡排序、选择排序和快速排序的时间（C语言实现）

前言

本文主要比较冒泡排序、快速排序、选择排序的时间。

冒泡排序和快速排序的思想可以参考我转载的以下博文：
https://blog.csdn.net/gogo0707/article/details/124388314

代码设计

随机生成10000个随机数，进行冒泡排序、选择排序和快速排序，并比较时间；

本设计中使用clock函数获取cpu运行时间，排序后的cpu clock数减去排序前的cpu clock数，就可以得到排序消耗的cpu clock数。

代码实现

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <stdbool.h>

//随机生成10000个随机数，进行冒泡排序和快速排序，并比较时间。

//冒泡排序
void BubbleSort(int *a, int length) 
{
	int temp;
	for (int i = 0; i < length - 1; i++)
	{
		for (int j = 0; j < length - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

//快速排序
void QuickSort(int *arr, int low, int high)  
{
	if (low < high)
	{
		int i = low;
		int j = high;
		int k = arr[low];
		while (i < j)
		{
			while (i < j && arr[j] >= k)     // 从右向左找第一个小于k的数
			{
				j--;
			}
 
			if (i < j)
			{
				arr[i++] = arr[j];
			}
 
			while (i < j && arr[i] < k)      // 从左向右找第一个大于等于k的数
			{
				i++;
			}
 
			if (i < j)
			{
				arr[j--] = arr[i];
			}
		}
 
		arr[i] = k;
 
		// 递归调用
		QuickSort(arr, low, i - 1);     // 排序k左边
		QuickSort(arr, i + 1, high);    // 排序k右边
	}
}
 
//选择排序（这里采用的是非稳定版本）
void select_sort(int *array, int size)
{
	int max;
	int pos;
	int i,j;
	int tmp;

	for(i = 0; i < size-1; i++)	//循环一次就找到一个较大的数，然后与数组的第n个数据交换位置(n从0开始)
	{
		max = array[i];
		pos = i;
		for(j = i; j <= size-1; j++)
		{
			if(array[j] > max)
			{
				max = array[j];
				pos = j;
			}
		}
		//直接交换数据，会改变同值数据的顺序，所以是非稳定版本
		tmp = array[i];
	    array[i] = array[pos];
		array[pos] = tmp;
	}
}

//冒泡排序改良版
void BubbleSortNew(int *a, int length) 
{
	int temp;
	//记录最后一次交换的位置
	int last_exchange_index = 0;
	//无序数列的边界，每次比较只需要比到这里	
	int sort_border = length - 1;

	for (int i = 0; i < length - 1; i++)
	{
		bool isSorted = true;
		for (int j = 0; j < sort_border; j++)
		{
			if (a[j] > a[j + 1])
			{
				isSorted = false;	//有数据要交换位置，所以不是有序，标志置为false 
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				last_exchange_index = j;
			}
		}
		sort_border = last_exchange_index;
		if(isSorted)	//一轮下来是否发生数据交换，没有就退出排序
			break;
	}
}


int main(void)
{
	int num[10000]; 
 

 	srand(time(0));
	for (int i = 0; i<10000; i++)
	{
		
		num[i] = rand() % 10000;
		
	}

	clock_t start = clock();
	BubbleSort(num, 10000);		//冒泡排序测试
	clock_t end = clock();
	
	printf("使用冒泡排序花费了 %ld  cpu clock\n", (end - start));//<-
	getchar();
 
 	for (int i = 0; i<10000; i++)
	{
		
		num[i] = rand() % 10000;
		
	}

	clock_t start4 = clock();
	BubbleSortNew(num, 10000);		//冒泡排序改良版测试
	clock_t end4 = clock();
	
	printf("使用改良版冒泡排序花费了 %ld  cpu clock\n", (end4 - start4));//<-
	getchar();

 
 
 	for (int i = 0; i<10000; i++)
	{
		
		num[i] = rand() % 10000;
		
	}
	
	clock_t start2 = clock();
	QuickSort(num, 0, 9999);				//快排测试
	clock_t end2 = clock();
	
	printf("使用快速排序花费了 %ld cpu clock\n", (end2 - start2));//<-
	getchar();
	
	for (int i = 0; i<10000; i++)
	{
		
		num[i] = rand() % 10000;
		
	}
 
	clock_t start3 = clock();
	select_sort(num, 10000);	//选择排序测试
	clock_t end3 = clock();
	
	printf("使用选择排序(非稳定版本)花费了 %ld  cpu clock\n", (end3 - start3));//<-
	getchar();
 
}

运行结果

zzc@zzc-virtual-machine:~/share$ ./2
使用冒泡排序花费了 162699  cpu clock

使用改良版冒泡排序花费了 151667  cpu clock

使用快速排序花费了 724 cpu clock

使用选择排序(非稳定版本)花费了 54151  cpu clock

结果分析

1. 从运行结果可以看出，快速排序用时最短，冒泡排序用时最长，两者相差了几个数量级；
2. 改良后的冒泡比传统的冒泡用时有所减少；
3. 选择排序（非稳定版本）用时比冒泡排序短了近3倍

稳定性测试

做3个测试：
第1个测试，数组（有10000个数据）通过随机数产生，随机数的范围指定为0到9999；
第2个测试，数组（有10000个数据）通过随机数产生，随机数的范围指定为0到99；
第3个测试，数组（有10000个数据）通过随机数产生，随机数的范围指定为0到9；

观察并比较各排序算法用时的变化。

第一个测试结果如下：

第二个测试结果如下：

第三个测试结果如下：

从测试结果可以计算出相差不同数量级（以第一个测试为基准）下各算法用时的变化率，如下表：

综上，可以发现待排序的数据的关联性对快速排序影响很大，排序时间波动很大；
而冒泡排序受到的影响相对较小，排序时间比较稳定。

总结

1. 快速排序虽然用时较短，但是压栈严重，容易造成堆栈溢出，稳定性较差。
2. 冒泡排序虽然平均时间复杂度比较大，但是算法比较稳定。
3. 上述测试中选择排序使用的是非稳定版本，虽然用时较短，但要考虑实际应用时同值数据的顺序有无要求，如有要求，请使用稳定版本。

以上测试的测试量不够大，只能体现出一些变化规律。