【初阶数据结构篇】冒泡排序和快速排序（中篇）

冒泡排序和快速排序

前言

本篇以排升序为例

代码位置

gitee

冒泡排序

动图理解

• 作为第一个接触的排序算法，冒泡排序想必大家已经很熟悉了
  • 总共n个数据，要排n-1趟
  • 第i（i从0开始取）趟要比较n-1-i次
  • 等差数列求和，最坏时间复杂度为O(n2)
• 定义exchange变量，当数组已经有序时不进入交换，直接跳出循环
  • 最好时间复杂度为O(n)
• 空间复杂度O(1)

代码语言：javascript复制

void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i  )
	{
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j  )
		{
			//升序
			if (arr[j] < arr[j   1])
			{
				exchange = 1;
				Swap(&arr[j], &arr[j   1]);
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

• 与直接插入排序法相比，比较次数一致，但冒泡排序的交换需要执行三次，而直接插入排序因为使用了tmp临时变量存储要插入的数据，只用执行一次，所以直接插入排序法效率明显更高
• 与直接选择排序法相比，直接选择排序法无论数组是否有序都要执行到结束条件，不存在最好最坏时间复杂度。而冒泡排序因为使用了exchange变量进行优化，可以在最好时间复杂度上达到线性的结果。所以冒泡排序更胜一筹
• 虽然但是，实际中还是不会使用冒泡排序，但它的教学意义是我们不能忽视的
  指针 数据结构 递归 排序 数据
  1 人点赞