本文为系列专题【数据结构和算法:简单方法】的第 12 篇文章。

  1. 数据结构 | 顺序表
  2. 数据结构 | 链表
  3. 数据结构 | 栈
  4. 数据结构 | 队列
  5. 数据结构 | 双链表和循环链表
  6. 数据结构 | 二叉树的概念和原理
  7. 数据结构 | 二叉树的创建及遍历实现
  8. 数据结构 | 线索二叉树
  9. 数据结构 | 二叉堆
  10. 算法 | 顺序查找和二分查找
  11. 数据结构 | 二叉查找树

本文先简单介绍一下什么是排序,然后再结合动画介绍暴力排序和冒泡排序。

1. 什么是排序?

排序在日常生活中无处不在。比如考试成绩的排名、体育课的从低到高的队形、网购时按价格升序排列或降序排列等等。

在该表格中,我们称一行数据为一条记录,其中姓名、学号等数据项是关键字,关键字是我们排序的依据。关键字可以是主关键字或次关键字,甚至是若干数据项的组合。

比如,在该表格中,我们是按照成绩(次关键字)从高到低降序排序的。也可以按照学号排序,或者按照学号和成绩同时排序:先按成绩降序排列,成绩相同的,按照学号升序排列。

所以,对多条记录排序的本质是对关键字的排序,如果排序依据是多个关键字,可以转化为单个关键字的排序。

所谓排序,是指按指定的关键字,将某个序列的所有元素以有序的方式排列起来

如何实现排序呢?

比如上体育课时按身高的排序,就是比较两个人的身高,然后矮的站前面,高的站后面。如果高的在前,矮的在后,就交换位置;否则就用不动。

没错,排序是借助比较和交换来实现的。比较的是关键字,这是我们排序的依据。交换的是两个元素的位置,通常我们不真的交换位置,而是借助中间变量的赋值来实现交换位置的效果。

/*一个交换函数,交换数组中下标为i和j的元素位置*/
void swap(int *array, int i, int j)
{
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

在实现排序算法时,我们应当追求更少次数的比较和交换,这样才能提高算法的性能

为了后面说明问题方便起见,这里约定几个规则:

  • 只对数组排序,并约定数组长度 length = 10
  • 全部排序算法均按升序排序
  • 由于是针对数组,所以关键字就是其元素值本身。比较关键字即是比较元素值,不再区分。

2. 暴力排序(Violent Sort)

所谓暴力,是指没有任何技巧而言的方式,它直接粗暴地遍历真个数组,从而不停的进行比较和交换。这是最容易理解的排序算法。

核心思想:从数组的第一个元素开始,将每个元素作为基准元素,基准元素和其后面的所有元素比较,如果基准元素大于其后的某个元素,则与其交换位置;否则位置不变。

当基准元素和其后的所有元素比较交换完后,最小值一定被排好了,此时就说一排序完成了,每轮排序有若干次循环,用于比较和交换。像这样进行若干轮的排序后,排序就完成了。

我们需要两个变量,用于标记两个进行比较的元素下标:

  • 变量 i:某个元素的下标;
  • 变量 j:下标 i 之后的下标。

我们需要两个嵌套循环:

  • 外层循环控制轮数;
  • 内层循环控制每轮的比较和交换。

动态过程如下:

【排序算法动画解】排序介绍及冒泡排序-LMLPHP

代码实现如下:

/* 暴力排序
 * array : 数组
 * length : 数组长度
 */
void violent_sort(int *array, int length)
{
    int i, j;
    // 外层循环,遍历数组,控制轮数
    for (i = 0; i < length; i++) {
        // 内层循环,循环比较 array[i] 和其之后的元素,控制循环次数
        for (j = i + 1; j < length; j++) {
            if (array[i] > array[j]) { // 如果大于则交换
                swap(array, i, j);
            }
        }
    }
}

通过以上的暴力排序,我们能够初体会排序的思想,即不断地比较和交换

暴力排序有其明显的缺点,即每个元素都要和其之后的所有的元素比较,这就很容易破坏整个数组的原来顺序,比如在上面的动态过程中,元素 40 在某次交换后被交换到了更靠后的位置。为了排好某个元素,而对其之后的所有元素大动干戈,甚至破坏了它们原来之间的顺序,这就影响了效率。

3. 冒泡排序(Bubble Sort)

冒泡排序是一种很简单的排序算法,由暴力排序改进而来。

核心思想:比较相邻的两个元素,当前者大于后者时,交换二者位置;否则位置不变。

注意:冒泡排序是相邻的两个元素比较并交换,而暴力排序是某个元素和其之后的所有元素比较并交换。

当数组中所有的相邻元素进行两两比较和交换后,一定会找到一个最大值,并且最大值被交换到数组尾处,此时说一轮排序完成了,一轮排序中有若干次循环,用于比较和交换。像这样进行若干轮排序后,排序就完成了。

我们需要两个变量:

  • 变量 i:用于控制轮数;

  • 变量 j:元素下标,j+1 为其相邻元素的下标。

我们需要两个嵌套循环:

  • 外层循环控制轮数
  • 内层循环控制每轮所有相邻元素的比较和交换

动态过程如下:

【排序算法动画解】排序介绍及冒泡排序-LMLPHP

代码实现如下:

/* 冒泡排序
 * array : 数组
 * length : 数组长度
 */
void bubble_sort(int *array, int length)
{
    int i, j;
    // 外层循环,控制轮数。每一轮排好一个元素
    for (i = 0; i < length; i++) {
        // 内层循环,循环比较数组中未排序的元素
        for (j = 0; j < length - i - 1; j++) {
            // 若前者大于后者则交换
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}

由于是相邻的两个元素进行比较,所以一轮比较后,一定有一个最大的元素被交换到最右边,像“大泡泡”浮到水面上一样,所以我们称其为“冒泡排序”。

冒泡排序虽然改善了暴力排序的缺点,但仍然具有可优化的地方。

在上述动态过程中,第 7 轮(i = 6)时就已经完成排序了,但后面仍然进行了 3 轮的比较。这最后 3 轮是完全没必要的,所以我们可以改进一下,避免没必要的比较。

方法就是增加一个标志变量 unsorted,用于标志数组是否已经有序,unsorted = 0 时数组有序,unsorted = 1 时数组无序。

unsorted 通过记录在某轮排序中是否发生了交换,如果没发生,就意味着已经有序。

void bubble_sort_v3(int *array, int length)
{
    int i, j;
    int unsorted = 1; // 标识变量
    for (i = 0; i < length && unsorted; i++) {
        unsorted = 0;
        for (j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                unsorted = 1; // 发生交换,说明尚未有序
            }
        }
    }
}

虽然冒泡排序可以避免一些不必要的比较和交换,但是冒泡排序本质仍和暴力排序相似,即不断地大量交换,或是某个元素和其后所有元素的交换,或是两个相邻元素的交换。通过动图也可以看出,要使一个元素排到其正确的位置上,我们往往需要和多个元素相交换,这是影响效率的“硬伤”

【排序算法动画解】排序介绍及冒泡排序-LMLPHP

06-11 03:53