排序算法_冒泡排序（算法设计与C代码实现）

# 冒泡排序算法
冒泡排序算法是排序算法中很有意思的一种排序方式，其主要思想是：
每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

一、问题描述

       将一个数组中的数字进行排序处理，并返回一个排好序的新数组。

二、问题分析

算法：排序算法_冒泡排序
步骤：
（1）要进行几轮冒泡？
这个问题很多人觉得很烧脑，其实要进行几轮冒泡很好确定，比如，对5个数进行排序，只需要4轮就可以，你可以想象共有5个位置，当4个数已经确定位置后，那么剩下的数自然就找好了位置。

（2）每轮冒泡要进行几次交换？
这个地方我们可以用从特殊到一般的方法来研究这个算法。
怎么才算特殊？5,4,3,2,1就很特殊，我们下边讨论如何将它从小到大排序：

第1轮排序结果是4,3,2,1,5，可以看出数字5已经就位，下一轮无需比较最后1个数；
第2轮排序结果是3,2,1,4,5，可以看出数字4,5已经就位，下一轮无需比较最后2个数；
第3轮排序结果是2,1,3,4,5，可以看出数字3,4,5已经就位，下一轮无需比较最后3个数；
第4轮排序结果是1,2,3,4,5，可以看出数字1,2,3,4,5已经就位。

根据上边推论得知：
如果我们的数组长度是n，那么就需要进行n-1轮冒泡，若此时是第i轮，那么这一轮我们需要n-i-1次交换。

当然这个是特殊情况，如果普及到一般情况是否符合呢？这个验证工作可以交给代码来完成：

    int target_[5] = {5,4,2,5,1};
    int t = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - 1 - i; ++j) {
            if(target[j] < target[j+1]){
                t = target[j];
                target[j] = target[j+1];
                target[j+1] = t;
            }
        }
    }

（冒泡排序核心代码）
经过验证，我们在特殊情况下推出来的理论完全适合一般情况，因此该推论成立。

三、代码实现

main.c

#include <stdio.h>
#include "bubbleSort.h"

int main() {
    int target_list[6] = {5,4,2,5,16,8};
    int length = sizeof(target_list)/4;
    bubbleSort(target_list,length);

    //输出结果
    for (int i = 0; i < 6; ++i) {
        printf("%d  ",target_list[i]);
    }
    return 0;
}

bubbleSort.h

// 简介: 邻居好说话——冒泡排序
// 思想: 每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来
// Created by lanyan on 05/02/2022.

#ifndef SORTINGALGORITHM_BUBBLESORT_H
#define SORTINGALGORITHM_BUBBLESORT_H

//冒泡排序 5 4 3 2 1
void bubbleSort(int target[], int length){
    int t = 0;
    for (int i = 0; i < length - 1; ++i) {
        for (int j = 0; j < length - 1 - i; ++j) {
            if(target[j] < target[j+1]){
                t = target[j];
                target[j] = target[j+1];
                target[j+1] = t;
            }
        }
    }
}
#endif //SORTINGALGORITHM_BUBBLESORT_H

四、运行结果

五、算法解析

1. 冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N^2)。这是一个非常高的时间复杂度。
2. 正如Donald E. Knuth所说：““冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”
3. 很多初学者会纠结于要进行几轮排序，每轮要比较多少次的问题上，其实没有必要，只要记住了特殊情况，其他情况都会迎刃而解。
4. 还有人会纠结于循环从0开始还是从1开始的问题，这里我举一个例子：

（1）从0开始循环：

    for (int i = 0; i < 5; ++i) {
        printf("hello ");
    }

运行结果为：

（2）从1开始循环：

    for (int i = 1; i <= 5; ++i) {
        printf("hello ");
    }

运行结果为：

相信其中的差别你已经能看的清楚，既然这两种方式是等价的，可以互相替换的，又怎么会有循环从0开始还是从1开始的问题呢？

六、BUG记录

1. 第i轮，这一轮我们需要n-i-1次交换，注意也有一个减1，毕竟先有n - 1轮，后有n - i - 1次交换。