冒泡排序

1. 概念定义

冒泡排序（Bubble Sort）又称为泡式排序，是一种简单的排序算法。

核心思想：它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就像水中的气泡会冒起来一样。

运作步骤（升序排列）：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

比如：

原始数据：3 2 7 8 6，将其按升序排列。

第一次循环：（最大的跑到最右边）

3 2 7 8 6 --> 2 3 7 8 6 （3和2比较，3 < 2，所以3和2交换位置）

2 3 7 8 6 --> 2 3 7 8 6 （3和7比较。3 < 7，所以3和7不用交换位置）

2 3 7 8 6 --> 2 3 7 8 6 （7和8比较，7 < 8，所以7和8不用交换位置）

2 3 7 8 6 --> 2 3 7 6 8 （8和6比较，8 > 6，所以8和6交换位置）

经过第1次循环，此时剩下参与比较的数据：2 3 7 6

第二次循环：

2 3 7 6 --> 2 3 7 6 （2和3比较，不需要交换位置）

2 3 7 6 --> 2 3 7 6 （3和7比较，不需要交换位置）

2 3 7 6 --> 2 3 6 7 （7和6比较，7 > 6，所以7和6交换位置）

经过第2次循环，此时剩下参与比较的数据：2 3 6

第三次循环：

2 3 6 （2和3比较，不需要交换位置）

2 3 6 （3和6比较，不需要交换位置）

经过第3次循环，此时剩下参与比较的数据：2 3

第四次循环：

2 3 （2和3比较，不需要交换位置）

至此，5个数经历了4次循环，每次循环都将当前最大的书交换的最右的位置，然后下次循环就不再考虑该数。

具体实现：使用双重循环，外层循环控制循环的次数，内层循环进行数字的比较。内层每一次循环结束之后，都要找出最大的数据，放到参与比较的这堆数据的最右边，下次循环不再比较该数。

C代码

void bubbleSort(int *nums, int n) {
    int i, j;
    for(i = n-1; i > 0; --i) {  //因为每次比较两个数，所以总共n个数，只需要比较n-1次（外循环n-1次）
        for(j = 0; j < i; ++j) {  //每次比较完后，最大的值在下一次比较中不用比较，所以每次比较只需要循环n-1-i 次（内循环n-1-i次）
            if(nums[j] > nums[j+1]) {
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
}

2. 题目练习

1. 颜色分类
2. 寻找两个正序数组的中位数
3. 至少是其他数字两倍的最大数

3. 解题报告

颜色分类

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

解题思路

使用冒泡排序将数组按升序排列，排完序后相同的数就会相邻。

C代码

void bubbleSort(int *nums, int n) {
    int i, j;
    for(i = n-1; i > 0; --i) {  //因为每次比较两个数，所以总共n个数，只需要比较n-1次（外循环n-1次）
        for(j = 0; j < i; ++j) {  //每次比较完后，最大的值在下一次比较中不用比较，所以每次比较只需要循环n-1-i 次（内循环n-1-i次）
            if(nums[j] > nums[j+1]) {
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
}

void sortColors(int* nums, int numsSize) {
    bubbleSort(nums, numsSize);
}

剩下的题目大同小异，在此不多做展示。