欢迎大家来到IT世界,在知识的湖畔探索吧!

前言

排序算法是面试中经常遇到的，本章内容主要介绍排序算法的概念及冒泡排序的实现方法，讲解冒泡排序的原理，流程图，时间复杂度，优化空间等。希望能在面试中帮到大家

基本概念

排序算法就是将一组数据元素序列重新排列，使得数据元素序列按某个数据项（关键字）有序。

稳定排序和不稳定排序：

• 对于任意的数据元素序列，若排序前后所有相同关键字的相对位置都不变，则称该排序方法称为稳定的排序方法。
• 若存在一组数据序列，在排序前后，相同关键字的相对位置发生了变化，则称该排序方法称为不稳定的排序方法。

例如，对于关键字序列3，2，3，4，若某种排序方法排序后变为2，3，3，4，则该排序方法是不稳定的。

内部排序和外部排序：

• 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
• 若参加排序的记录数量很大，整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序。

如上图所示就是内部排序，内部排序的过程是一个逐步扩大有序序列长度的过程。这个过程并不会增加序列的长度。

冒泡排序

了解了排序的基本概念，下面我们一起看下冒泡排序算法是如何实现的。

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序的过程如下：

依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

1. 第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
2. 比较第2和第3个数，将小数 放在前面，大数放在后面。
3. ……
4. 如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，至此第一趟冒泡完成。之后重复1—4步骤。
5. 在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
6. 在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
7. 依次类推，每一趟比较次数依次减少，直到没有任何一对数字需要比较

上图就是冒泡排序的流程图和动态排序图，对着图的话更容易理解。

代码示例：

#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)  // 冒泡排序次数为待排序序列长度
      // 一趟冒泡排序，依次比较相邻的数据，已排序的最大数据在序列尾部不参与下次排序
        for (j = 0; j < len - 1 - i; j++) 
            if (arr[j] > arr[j + 1]) { // 比较相邻的两个数据如果前面的数据大，则交换两者的位置
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(&arr[0]);
    bubble_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

• bubble_sort有两个for循环，第5行到第9行表示一趟冒泡排序，第4行表示要进行len（待排序序列长度）趟冒泡排序。
• 6行的j < len – 1 – i里面的减i表示的是已排序的最大数据在序列尾部不参与下次排序
• 8到10行用来交换相邻的数据

代码运行结果如下：

冒泡排序的性能分析

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值

Cmin = N – 1, Mmin = 0。所以，冒泡排序最好时间复杂度为O(N)。

若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N – i 次关键字的比较(1 ≤ i ≤ N – 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较Cmax和移动Mmax次数均达到最大值：

Cmax = N(N-1)/2 = O(N^2)

Mmax = 3N(N-1)/2 = O(N^2)

冒泡排序的最坏时间复杂度为O(N^2)。

因此，冒泡排序的平均时间复杂度为O(N^2)。

总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。

算法稳定性

算法排序分为稳定排序和非稳定排序，这个我们在文章开头讲述算法概念的事就就介绍过了。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

冒泡排序就是把小的元素往前调或者把大的元素往后调。是相邻的两个元素的比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

冒泡排序算法优化

不知道大家有没发现上述的冒泡算法实例其实是存在问题的，第4行的for循环肯定会执行len – 1次。那么如果说在进行了 两次排序之后数据已经是排好序的了，那么之前的代码还是要继续进行排序，这无疑是无用功。

针对这种情况，通常的做法是增加一个exchange标志来表示当前这一趟冒泡排序是否进行了数据交换，如果没有进行交换则表示当前的序列已经是排好序的了，就不需要后面的排序操作了

优化代码如下：

欢迎大家来到IT世界,在知识的湖畔探索吧!#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    int exchange;
    for (i = 0; i < len - 1; i++) {
  		  exchange = 0;
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
            	  exchange = 1;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        if (exchange = 0)
        	break;
    }
    
     
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(&arr[0]);
    bubble_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

上述代码中增加了exchange变量来表示当前排序是否进行了数据交换，如果exchange = 0，则表示没有进行数据交换，当前的序列是已经排好序的了。不需要执行后面的排序操作，直接break当前的for循环。

运行效果是跟之前的是一样的。