十大排序的个人总结之——冒泡排序、插入排序

叁歲伎倆 2024-03-25 12:40 62阅读 0赞

## ![5999e007c01f4ef89dc014c7317e3a3f.png][] ##

##  ##

同样，这两几乎也是被淘汰了的算法，尽管它们是稳定的，但是时间复杂度没人喜欢，了解一下就好，没啥好说的，注意最后一句话就行了

## 一，冒泡排序 ##

#### 1. 算法步骤 ####

共n-1趟，**谁两敢冒泡就换了谁两**

第一趟，比较n-1次，每个相邻的位置都比较一次，比较两个元素大小，若位置反了就交换位置，一趟结束，最后一个位置就是最大值（降序就是最小值）

第二趟，比较n-2次，同上，最后一个元素不参与比较

第三趟，比较n-1次，同上，最后两个元素不参与比较

……

第n-1趟，比较1次，同上，最后n-2个元素不参与比较

一共比较累 1+2+3+……n-1 = (1 + n-1)\*(n-1) / 2 = 1/2 \* ( n^2 - n) ,比选择排序的n^2好一点点呵，然并……

#### 2. 动图演示 ####

![00c2e4ce22abf085f4a791126b29a4d2.gif][]

#### 3. 什么时候最快 ####

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

#### 4. 什么时候最慢 ####

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

5、代码

template<typename T> 
    
    void bubble_sort(T arr[], int len) {
            int i, j;
            for (i = 0; i < len - 1; i++)
                    for (j = 0; j < len - 1 - i; j++)
                            if (arr[j] > arr[j + 1])
                                    swap(arr[j], arr[j + 1]);
    }

## 二、插入排序 ##

#### 1. 算法步骤 ####

共n-1趟，**把每一个元素都插入到（理论上）原本该在的位置上去**

第一趟，把第一个元素看成已经排序好了的序列，用第2个元素来与之比较，比它大就插入到第一个后面，比它小就插入到它前面 （比较1次）

第二趟，把前2个元素看成已经排序好了的序列，用第3个元素来与前面的元素逐个比较，比某个比较元素大就插入到它后面，比它小就继续比较再前一个，若直到比第一个还小，就插入到第一个的位置（比较 1~2次）

第三趟，把前3个元素看成已经排序好了的序列，用第4个元素来与前面的元素逐个比较，比某个比较元素大就插入到它后面，比它小就继续比较再前一个，若直到比第一个还小，就插入到第一个的位置（比较1~3次）

………………………………

第n-1趟，把前n-1个元素看成已经排序好了的序列，最后 1 个元素来与前面的n-1元素逐个比较，比某个比较元素大就插入到它后面，比它小就继续比较再前一个，若直到比第一个还小，就插入到第一个的位置（比较1~n-1）

比冒泡排序更好一点了，

#### 2. 动图演示 ####

![7f15b3fa77c5258cd74b4aae157779fc.gif][]

--------------------

### 代码实现 ###

void insertion_sort(int arr[],int len){
            for(int i=1;i<len;i++){
                    int key=arr[i];
                    int j=i-1;
                    while((j>=0) && (key<arr[j])){
                            arr[j+1]=arr[j];
                            j--;
                    }
                    arr[j+1]=key;
            }
    }

## **特别注意：** ##

之所以说只说是几乎被淘汰了，而不是完全淘汰，是因为这两哥们的最好情况是O(n)，还都是稳定的排序方法，在元素大部分都是有序的，只有极个别的位置错了的情况下，这两个算法的优势就来了，特别是插入排序，本来就是逐个插入到正确的位置上去，现在大部分都是有序的，这部相当于大部分都插入好了嘛，就剩下极个别插入一下就完事了对吧，这是其他**任何排序算法**都无法比拟的存在

![526821ad80664567b934eae38385ba77.png][]

[5999e007c01f4ef89dc014c7317e3a3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/21697924b7c54c3b9f4b51a8e6689d6b.png
[00c2e4ce22abf085f4a791126b29a4d2.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0fccf874acf04d3b8f933c4040078f26.png
[7f15b3fa77c5258cd74b4aae157779fc.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3452a1fcef2f4c5685b86659a2cad4eb.png
[526821ad80664567b934eae38385ba77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/bd7636527cba4e05abd478f84851cfe1.png