排序算法：冒泡排序算法优化实现及分析

「爱情、让人受尽委屈。」 2022-05-31 10:54 304阅读 0赞

# 冒泡排序算法介绍 #

**冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止**。这是书上的定义，感觉太弯弯肠子了。冒泡排序是几乎所有学编程的都会学的一个排序，因为其实现思路简单。实际上就是2 相邻元素两两比较，将最值冒到 最后面去，直到将所有的值都冒泡完毕，排序也就完成了。

# 冒泡排序算法代码 #

在有n个元素的 arr数组，第1轮冒泡 将 最值冒到 arr\[n-1\]，第2轮冒泡将最值冒泡到arr\[n-2\]，外层循环完毕，数组元素全部冒泡ok，冒泡排序结束。下面是冒泡排序代码：

//冒泡排序
    //外层循环1次 将一个最值冒出
    //直到将所有值 冒出去
    void BubbleSort1(int *arr, int length)
    {
    	for (int i = 0; i < length-1; i++)
    	{
    		//冒泡排序是2相邻元素进行比较，然后冒泡
    		for (int j = 0; j < length - 1 - i; j++)
    		{
    			//升序
    			if (arr[j] > arr[j + 1])
    			{
    				Swap(&arr[j], &arr[j + 1]);
    			}
    		}
    	}
    }

#    冒泡排序算法优化 #

比如有个数组\{9,1,2,3,4,5,6,7,8\}。我们进行升序排序，在第1轮冒排序后，已经排序ok，但是我们的普通冒泡排序，还有进行8轮的内层for循环进行比较 ，这不就是浪费时间浪费青春嘛。所以当我们发现排序已经ok了，就可以不用再排序了。**加一个排序是否ok的标志位flag 就行了**。比如\{9,1,2,3,4,5,6,7,8\}，在第2轮冒泡排序完毕，我们发现没有交换数组元素，就知道排序已经ok，就可以结束循环了。下面是优化后的代码：

//冒泡排序 优化版，添加标志位
    //如果内层循环完毕 发现没有交换值，说明排序已经ok了
    void BubbleSort2(int *arr, int length)
    {
    	int flag = 0;//0 表示没有排好序
    	for (int i = 0; i < length - 1 && flag == 0; i++)
    	{
    		flag = 1;//假定排好序了
    		for (int j = 0; j < length - 1 - i; j++)
    		{
    			//升序
    			if (arr[j] > arr[j + 1])
    			{
    				flag = 0;//其实还没有排好序呢
    				Swap(&arr[j], &arr[j + 1]);
    			}
    		}
    	}
    }

#    冒泡排序算法复杂分析 #

内存循环进行两两比较 交换值进行冒泡。在外层

第1轮循环时，arr\[0\]、arr\[1\].....arr\[n-1\]，他们两两比较 进行冒泡，总共比较次数为n -1，将第一个最值冒泡到arr\[n-1\] 处。

第2轮循环时，arr\[0\]、arr\[1\].....arr\[n-2\]，他们两两比较 进行冒泡，总共比较次数为n -2，将第二个最值冒泡到arr\[n-2\] 处。

所以不难得出它的比较的次数是n-1 + n-2 + n-3 + ....1 = n\*（n-1）/2 。

时间复杂度为 = n^2/2- n/2 = n^2 ,**O（n^2）**。

# 冒泡排序和选择排序比较 #

**冒泡排序和选择排序 虽然他们的时间复杂度都是O（n^2），但是由于冒泡排序是进行值的交换，而选择排序是记录最值下标 减少了 值交换的次数，所以选择排序比冒泡排序 效率略微 好一些**。

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <sys/timeb.h>
    #define MAXSIZE 20
    #define MAXNUM 51
    //交换值
    void Swap(int* a, int* b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    //选择排序 核心是记录最值下标
    void SelectSort_Up(int *arr, int length)
    {
    	for (int i = 0; i < length - 1; i++)
    	{
    		int index = i;//记录最值下标
    		for (int j = i + 1; j < length; j++)
    		{
    			//升序
    			if (arr[index] > arr[j])
    			{
    				index = j;
    			}
    		}
    		if (i != index)
    		{
    			Swap(&arr[i], &arr[index]);
    		}
    	}
    }
    //冒泡排序
    //外层循环1次 将一个最值冒出
    //直到将所有值 冒出去
    void BubbleSort1(int *arr, int length)
    {
    	for (int i = 0; i < length-1; i++)
    	{
    		//冒泡排序是2相邻元素进行比较，然后冒泡
    		for (int j = 0; j < length - 1 - i; j++)
    		{
    			//升序
    			if (arr[j] > arr[j + 1])
    			{
    				Swap(&arr[j], &arr[j + 1]);
    			}
    		}
    	}
    }
    //冒泡排序 优化版，添加标志位
    //如果内层循环完毕 发现没有交换值，说明排序已经ok了
    void BubbleSort2(int *arr, int length)
    {
    	int flag = 0;//0 表示没有排好序
    	for (int i = 0; i < length - 1 && flag == 0; i++)
    	{
    		flag = 1;//假定排好序了
    		for (int j = 0; j < length - 1 - i; j++)
    		{
    			//升序
    			if (arr[j] > arr[j + 1])
    			{
    				flag = 0;//其实还没有排好序呢
    				Swap(&arr[j], &arr[j + 1]);
    			}
    		}
    	}
    }
    //打印数组元素
    void PrintArr(int* arr, int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return;
    }
    //获取系统时间
    time_t GetSysTime()
    {
    	struct timeb time;
    	ftime(&time);
    	return time.time * 1000 + time.millitm;;
    }
    
    
    int main(int argc, char *argv[])
    {
    	srand((size_t)time(NULL));//设置随机种子
    	int arr1[MAXSIZE] = { 0 };
    	int arr2[MAXSIZE] = { 0 };
    	int arr3[MAXSIZE] = { 0 };
    
    	//给每个元素设置一个随机值
    	for (int i = 0; i < MAXSIZE; i++)
    	{
    		int num = rand() % MAXNUM;
    		arr1[i] = num;
    		arr2[i] = num;
    		arr3[i] = num;
    	}
    	printf("冒泡排序前:\n");
    	PrintArr(arr1, MAXSIZE);
    	printf("普通版冒泡升序:\n");
    	BubbleSort1(arr1, MAXSIZE);
    	PrintArr(arr1, MAXSIZE);
    
    	printf("冒泡排序前:\n");
    	PrintArr(arr2, MAXSIZE);
    	printf("优化版冒泡升序:\n");
    	long start1 = GetSysTime();
    	BubbleSort2(arr2, MAXSIZE);
    	long end1 = GetSysTime();
    	PrintArr(arr2, MAXSIZE);
    
    	/*printf("选择排序前:\n");
    	PrintArr(arr2, MAXSIZE);
    	printf("选择排序升序:\n");
    	long start2 = GetSysTime();
    	BubbleSort2(arr2, MAXSIZE);
    	long end2 = GetSysTime();
    	PrintArr(arr2, MAXSIZE);
    	printf("%d个元素选择排序耗费时间：%d\n",MAXSIZE,end1-start1);
    	printf("%d个元素冒泡排序耗费时间：%d\n", MAXSIZE, end1 - start1);*/
    	return 0;
    }

# 代码运行检测 #

普通冒泡和优化的冒泡排序

![20180222174414625][]

选择排序和冒泡排序比较，用10000个元素测试，就不打印了。差距很明显哟。

![20180222174844811][]

[20180222174414625]: /images/20220531/6bb70aeffcc8487b8b02ba860221d7ad.png
[20180222174844811]: /images/20220531/34ed9bab2a6c4a629d034233037bc187.png