排序算法之冒泡排序和选择排序

从这周开始，每周我将写一些工作中常用的算法如下：

1. 冒泡排序和选择排序；
2. 插入排序；
3. 希尔排序；
4. 归并排序及其优化；
5. 快速排序及其优化；
6. 堆排序；

下面开始正文：

冒泡排序

冒泡排序可能是我们学习某种编程语言（大多数都是 C）之后，接触到的第一个排序算法。我在网上找了很多的博客之类的介绍冒泡排序的，但总是总是有点纰漏，比如 分析的和写的例子不一致（😂😂😂），很尴尬。下面我们详细来分析一下冒泡排序的过程：

待排序数组为：

{6, 2, 4, 1, 5, 9 }

冒泡排序的原理是：临近的``数字两两进行比较,按照从小到大或者从大到小的顺序进行交换。

这里注意：是临近的两个数字两两进行比较，如果非，那就不是冒泡排序。

起始数组如下：

1. 第一趟排序

第一次比较： 6 > 2 6 大于 2 进行交换，交换后：

第二次比较： 6 > 4 6 大于 4 进行交换，交换后：

第三次比较： 6 > 1 6 大于 1 进行交换，交换后：

第四次比较： 6 > 5 6 大于 5 进行交换，交换后：

第五次比较： 6 < 9 6 小于 9 不进行交换：

后面的第二、三、四、五、六的过程和上面的一样，最终如下面：

注意：第二次比较的时候，最后一位就不参与了，因为最大的已经冒了出来，第三次比较，倒数第二位不参与了，以此类推。

至此，程序就很容易写出来了：

void bubbleSort(int arr[],int n) {
    for (int i = 0; i < n ; i ++) {
        for (int j = 1; j < n-i; j ++) {
            if (arr[j] < arr[j-1]) {
                swap(&arr[j], &arr[j-1]);
            }
        }
    }
}

冒泡排序的优化

我们看一下 每次排序的结果：

第一次：2 4 1 5 6 9 
第二次：2 1 4 5 6 9 
第三次：1 2 4 5 6 9 
第四次：1 2 4 5 6 9 
第五次：1 2 4 5 6 9 
第六次：1 2 4 5 6 9

从中我们发现第三次的时候，已经排好序了，第四、五、六次没必要执行了，这就是我们要对冒泡排序进行优化的地方。

我们可以设置一个flag ，当没有发生交换的时候，记录一下，这时候数组已经有序了。

代码如下：

void bubbleSort2(int arr[],int n) {
    int flag = 1;
    for (int i = 0; i < n && flag ; i ++) {
        flag = 0;
        for (int j = 1; j < n - i; j ++) {
            
            if (arr[j] < arr[j-1]) {
                flag = 1;
                swap(&arr[j], &arr[j-1]);
            }
        }
    }
}

当然，还有其他的优化方案，大家不妨搜下。

选择排序

理解的前面的冒泡排序，选择排序是很容易理解的。选择排序顾名思义，每次循环要找出一个最小的值，然后再交换。

测试用例还是之前的：

第一次大循环找到最小的值 1 然后和 第0位的交换，交换后：

第二次大循环找到最小的值 2 然后和 第1位的交换，交换后：

当然第三次大循环和第二次一样

第四次大循环找到最小的值 5 然后和 第3位的交换，交换后：

后面的就已经排序好了。

从上面可以看出，选择排序是一个不断寻找最小值的排序方法。

所以代码如下：

void selectSort(int arr[],int n) {
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(&arr[i], &arr[minIndex]);
    }
}

是不是很简单 😁😁😁！

最后附上Demo