admin管理员组

文章数量:1794759

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

冒泡排序和快速排序

前言

本篇以排升序为例

代码位置

gitee

冒泡排序

动图理解

  • 作为第一个接触的排序算法，冒泡排序想必大家已经很熟悉了
    • 总共n个数据，要排n-1趟
    • 第i（i从0开始取）趟要比较n-1-i次
    • 等差数列求和，最坏时间复杂度为O(n2)
  • 定义exchange变量，当数组已经有序时不进入交换，直接跳出循环
    • 最好时间复杂度为O(n)
  • 空间复杂度O(1)
代码语言：javascript代码运行次数：0运行复制
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变量进行优化，可以在最好时间复杂度上达到线性的结果。所以冒泡排序更胜一筹
  • 虽然但是，实际中还是不会使用冒泡排序，但它的教学意义是我们不能忽视的

    本文标签： 初阶数据结构篇冒泡排序和快速排序（中篇）

    版权声明：本文标题：【初阶数据结构篇】冒泡排序和快速排序（中篇） 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754951537a1708569.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。