【数据结构】从冒泡到快速排序：探索经典排序算法的奥秘

野生的编程萌新

发布于 2026-01-15 09:42:34

870

专栏引入

哈喽大家好，我是野生的编程萌新，首先感谢大家的观看。数据结构的学习者大多有这样的想法：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学的很累。我想让大家知道的是：数据结构非常有趣，很多算法是智慧的结晶，我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏，在这里我将把数据结构内容以有趣易懂的方式展现给大家。

1.排序

1.1引入

在我们的日常生活中，我们无时无刻不在与“排序”打交道----整理书架时会把书籍按类别或出版时间排列，排队时会自觉按身高或先来后到调整顺序，考试后老师会按分数高低公布学生成绩......这些行为的本质，都是将一组原本无序的元素转化为有特定规则的序列。这种“让混乱变得有序”的思维，在计算机科学中被提炼为一种核心操作----排序。

当我们用程序处理数据时，无论是管理学生信息、分析销售数据，还是优化搜索引擎的结果，“无序”往往是阻碍效率的难题。例如，若要从百万条用户记录中快速找到年龄最大的用户，直接遍历所有数据可能需要数万次操作；但如果先将数据按年龄排序，只需一次遍历即可定位目标。此时，排序的价值便显现出来：它不仅能提升后续操作的效率（如查找、统计），更能帮助我们从数据中挖掘规律（如时间序列的趋势分析）。

1.2概念

排序（Sorting）是计算机科学和数据处理中最基础、最核心的操作之一，其本质是通过特定的规则，将一组无序的数据元素重新排列，使其满足某种预定义的顺序。

1.3分类

数据结构中排序的分类大致如下：

2.冒泡排序

这时候会有人问了，按照你上面的分类，第一个介绍的不因该是直接插入排序嘛，怎么是冒泡排序啊？无论你学习哪种语言，在学到循环和数组时，通常都会介绍一种排序算法，这个算法就是我们的冒泡排序，它就相当于我们学习编程时的"hello world"。冒泡排序并不是因为它的名字好听，而是因为这个排序算法的思路最简单，最容易理解，所以我们就从冒泡排序开始我们排序之旅。

2.1冒泡排序的实现

什么是冒泡排序呢？我们先看下面的一小段视频：

冒泡排序

冒泡排序是一种简单的交换排序，它的基本思想是：通过重复地遍历待排序的列表，比较相邻的元素并交换他们的位置，将较大的元素逐渐“冒泡”到列表的末端，每遍历一遍都会将一个最大的元素逐渐放到其正确的位置。知道了冒泡排序的思想，那我们就试着实现一下吧：

void Bubblesort(int* arr,int n)
{
  for (int i = 0; i < n - 1; i++) // 外层循环：n-1轮（无需处理最后一个元素）
   { 
     for (int j = 0; j < n - i - 1; j++) // 内层循环：遍历未排序部分（长度逐轮减1）
      {  
        if (arr[j] > arr[j + 1])  // 比较相邻元素
         { 
          swap(&arr[j], &arr[j + 1]);  // 仅交换相邻元素
         }
      }
   }
}

在上面的代码中外层循环for (int i = 0; i < n-1; i++ )控制总共需要 n-1 轮比较，内层循环for（int j=0；j<n-1;j++）在每轮中比较未排序部分的相邻元素，如果前一个元素大于后一个元素就交换他们。假设我们待排序的序列为{9，1，5，8，3，7，4，6，2}，先看第一轮交换过程即i=0时：：

j=0: [1, 9, 5, 8, 3, 7, 4, 6, 2] (交换9和1) j=1: [1, 5, 9, 8, 3, 7, 4, 6, 2] (交换9和5) j=2: [1, 5, 8, 9, 3, 7, 4, 6, 2] (交换9和8) j=3: [1, 5, 8, 3, 9, 7, 4, 6, 2] (交换9和3) j=4: [1, 5, 8, 3, 7, 9, 4, 6, 2] (交换9和7) j=5: [1, 5, 8, 3, 7, 4, 9, 6, 2] (交换9和4) j=6: [1, 5, 8, 3, 7, 4, 6, 9, 2] (交换9和6) j=7: [1, 5, 8, 3, 7, 4, 6, 2, 9] (交换9和2)

后面几轮的操作步骤相同，逐渐的使得待排序的序列有序。这样的冒泡排序能否优化一下呢？答案是有的兄弟，有的...我们一起来看一下：

void Bubblesort(int* arr,int n)
{
  bool flag;
  for(int i=0;i<n-1;i++)
   {
     flag=false;//每轮运行重置标志位
     for(int j=0;j<n-1;j++)
      {
        if(arr[j]>arr[j+1])
         {
           swap(&arr[j],&arr[j+1]);
           flag=true;
         }
      }
     if(!flag)
      break;
   }
}

代码的改动关键就是在i变量的for循环中，增加了flag是否为true的判断，这样的优势在于对于部分接近有序数组，可以减少大部分不必要的遍历，例如：给定的无序数组只有两个相邻的元素无序，这种情况我们只需要遍历一次就可以了，不需要多余的操作。话又说回来了，这么简单易实现的排序算法在我们的生活中有什么应用场景吗？当然是有的，任何一种排序算法都有适合自己的应用场景，冒泡排序在我们生活中仅适用于教学，这是为什么？因为他的时间复杂度太高了，那么接下来我们一起研究下冒泡排序的时间复杂度是多少呢。

2.2冒泡排序的时间复杂度分析

那么现在我们来分析一下冒泡排序的时间复杂度，首先，我们先来分析最好的情况，也就是待排序的序列本身就是有序的，那么我们比较（根据最后改良的代码）次数，就可以推断出来是n-1次的比较，没有数据发生交换（所有元素都已经有序），所以这时候的时间复杂度就是O(n)。说完最好的情况，那接下来我们来分析它的最坏情况，也就是待排序的序列是完全逆序的情况（例如：{5,4,3,2,1}），每一轮遍历都要进行最大次数的比较和交换，总比较次数就是(n-1)+(n-2)+....+1=n(n-1)/2（等差数列求和），由于大O符号关注的是增长趋势，常数系数会被忽略，因此最坏情况下的时间复杂度为O(n²)。时间复杂度我们都算了，那怎么能少得了空间复杂度呢？冒泡排序是原地排序算法，仅需常数级额外空间（如交换时的临时变量），因此空间复杂度为O(1)。

3.插入排序

扑克牌是我们几乎每个人都可能玩过的游戏，我们玩扑克牌时一般都是一只手摸牌，一只手理牌，使其变得有序方便观察，我们先看下面的这张图片

假设我们把已经摸好的牌理好之后是现在这种效果，接着我们又摸了一张6，如果是你该如何理牌呢？哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法是不用教的，只需要将他插入到我们整理好的拍中5和6的中间就算理好了，这种理牌的方法，就是插入排序。首先我们先看下面的一小段视频来了解插入排序是如何工作的：

插入排序

3.1插入排序的实现

不知大家是否观看了上面的一小段视频来了解插入排序的操作步骤，想要实现插入排序，我们就要先了解它的工作原理及其工作思想。插入排序的基本操作是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，直到所有数据排序完毕。

排序算法的操作步骤：

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果被扫描的元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5，直到所有元素均排序完毕。

那我们知道了工作原理和操作步骤，我们就先来实现一下：

void Insertsort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

我们给一个乱序序列看看是否能排序成功：

那我们看一下它的工作效率怎么样，首先我们生成一个装有1万个随机数的序列，再让插入排序对它进行排序，看看运行花费多少时间（毫秒）：

这时候大家是不是会觉得插入排序效率特别高呢？但他还不是最快的排序算法，一个算法是否高效还要从它的时间复杂度和空间复杂度来分析。

3.2插入排序的时间复杂度分析

最坏情况：

最坏的情况就是待排序的序列完全逆序（这点和冒泡排序一样），外层循环执行n-1次，对于每个位置i，内层while循环的执行次数为1，2，3....n-1，总的比较次数1+2+3+...+（n-1）=n(n-1)/2，即O（n²）。

最好情况：

最好的情况仍然为有序序列，对于外层循环仍是运行n-1次，内循环仅执行1次就会break，总比较次数为n-1次，即O（n）。

4.希尔排序

接下来我们要讲解的排序算法是希尔排序，希尔排序在整个排序算法发展历程中是具有里程碑的意义。这时候就有人问了，你为什么会这么赞誉这个排序算法呢？希尔排序是D.L.Shell于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是O(n²)，希尔排序算法是突破这个时间复杂度第一批算法之一。

4.1希尔排序的实现

我们上一个讲的插入排序，他的效率在某些时候是很高的，比如：我们记录的数据本身就接近有序，我们只要执行少量的插入排序操作，就可以完成整个数据的排序工作。此时的插入排序的效率很高效，还有一种情况就是记录数较少时，插入排序的优势也是很突出。这时的主要问题就比较突出了：这两种条件过于苛刻。有条件当然是最好的，没条件我们该怎么办呢？直接创造一个条件呗。于是D.L.Shell研究出了一种新的排序算法，对插入排序改进后可以增加效率：

如何让待排序的序列记录个数减少呢？我们很容易想到的就是将原有的数据进行分组，分割成若干个子序列，这时候每个子序列待排序的数据就减少了，然后再这些子序列内分别进行插入排序，当整个待排序的序列基本有序时，再进行一次插入排序。

希尔排序也叫缩小增量排序，是一种基于插入排序的比较类内部排序算法。希尔排序的核心思想就是：先将整个数组分割成若干个子序列，每个子序列的元素间隔称为“增量”（Gap）；对每个子序列进行插入排序，使数组逐渐变得“基本有序”；随着增量逐渐缩小（最终增量为1），最后一次插入排序只需处理几乎有序的数组，从而大幅提升效率。

为了能让大家更好的了解希尔排序，我们先来实现希尔排序，接着逐步讲解帮助大家能掌握希尔排序：

void Shellsort(int* a,int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n-gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

我们先假设待排序的序列为{5,2,6,7,1,3,9,4,8}，接下来和我一样来掌握希尔排序的具体操作步骤吧：

程序开始运行，此时传入我们的待排序的序列及其长度n。
第三行的gap变量就是我们前面提到的“增量”，我们令他的初始值等于待排序序列的长度n。
第4到23行是一个嵌套for语句的while循环，他的终止条件是gap不大于1时，其实就是增量为1时就停止了。
第6行这一句很关键，也是很难以理解的地方，为什么不像传统shell排序一样用“gap=gap/2”呢？因为gap=gap/3+1能够避免最坏情况的发生，什么情况是最坏的情况呢？就是当序列完全逆序排列时，使用gap=gap/2会造成大量不必要的元素移动，会导致时间复杂度接近O(n²)。gap=gap/3+1还有更快的间隔收缩，相同的初始值，gap/3+1 序列下降得比 gap/2 序列更快。
从第7行开始是一个for循环，从0开始遍历所有可能的子序列的起始位置，n-gap保证不会出现越界，保证每个子序列元素包含：a[i]，a[i+gap]，a[i+2*gap]....大家肯定觉得枯燥难以理解，看下面这个图来帮助大家理解：