算法分析（一） - 冒泡排序 & 插入排序 & 选择排序

水深无声 2023-06-18 13:00 25阅读 0赞

冒泡排序 、插入排序和选择排序都是基于**比较**的排序算法。本文将详细分析这三种排序。

先说结论：

<table style="width:700px;"> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>基于比较</th> 
   <th>原地排序</th> 
   <th>稳定性</th> 
   <th> <p>时间复杂度</p> <p>最好</p> </th> 
   <th> <p>时间复杂度</p> <p>最坏</p> </th> 
   <th> <p>时间复杂度</p> <p>平均</p> </th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>✔</td> 
   <td>✔</td> 
   <td>✔</td> 
   <td>O(n)</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>✔</td> 
   <td>✔</td> 
   <td>✔</td> 
   <td>O(n)</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>✔</td> 
   <td>✔</td> 
   <td>✘</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
   <td>O(<img alt="n^{2}" src="https://private.codecogs.com/gif.latex?n%5E%7B2%7D">)</td> 
  </tr> 
 </tbody> 
</table>

## 1 冒泡排序 ##

每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一 个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

代码如下：

void BubbleSort(int num[],int n)
    {
        if (n <= 1)
            return;
    
        for (int i = 0; i < n; i++)
        {
            bool flag = false;
            for (int j = 0; j < n - i - 1; j++)
            {
                if (num[j] > num[j + 1])
                {
                    int temp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag)
            {
                break;
            }
        }
    }

### 1.1 冒泡排序是原地排序算法。 ###

冒泡的过程中，只涉及相邻数据的交换操作，不需要额外的空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

### 1.2 冒泡排序是稳定的排序算法 ###

冒泡的过程中，当有相邻的两个元素大小相等时，不做交换，因此相同大小的 数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

### 1.3 冒泡排序的时间复杂度分析 ###

最好情况下，要排序的数据已经是有序的，只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。

最坏情况下，要排序的数据是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(![n^\{2\}][n_2])。

平均时间复杂度就是加权平均期望时间复杂度，结合概率论知识，平均时间复杂度为O(![n^\{2\}][n_2])。

## 2 插入排序 ##

插入排序将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

代码如下：

void InsertSort(int num[], int n)
    {
        if (n <= 1)
            return;
    
        for (int i = 0; i < n; i++)
        {
            int temp = num[i];
            int j = i - 1;
            for (; j >= 0; j--)
            {
                if (num[j] > temp)
                {
                    num[j + 1] = num[j];
                }
                else
                {
                    break;
                }
            }
            num[j + 1] = temp;
        }
    }

### 2.1 插入排序是原地排序算法。 ###

插入的过程中，不需要额外的空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

### 2.2 插入排序是稳定的排序算法 ###

插入的过程中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

### 2.3 插入排序的时间复杂度分析 ###

最好情况下，要排序的数据已经是有序的，我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置，不需要搬移数据。因此最好是时间复杂度为O(n)。

最坏情况下，要排序的数据是倒序排列的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(![n^\{2\}][n_2])。

在数组中插入一个数据的平均时间复杂度是是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(![n^\{2\}][n_2])。

## 3 选择排序 ##

选择排序将数组中的数据分为两个区间，已排序区间和未排序区间。选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码如下：

void SelectSort(int num[], int n)
    {
        if (n <= 1)
            return;
    
        for (int i = 0; i < n; i++)
        {
            int index = i;
            for (int j = i + 1; j < n; j++)
            {
                if (num[index] > num[j])
                {
                    index = j;
                }
            }
            if (index != i)
            {
                int temp = num[i];
                num[i] = num[index];
                num[index] = temp;
            }
        }
    }

### 3.1 选择排序是原地排序算法。 ###

选择排序的过程中，不需要额外的空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

### 3.2 选择排序是不稳定的排序算法 ###

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素 交换位置，这样破坏了稳定性。

如5，8，5，2，9这样一组数据，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

### 3.3 选择排序的时间复杂度分析 ###

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(![n^\{2\}][n_2])。

## 4 测试 ##

随机生成10000个数组，每个数组中包 含200个数据，然后分别用冒泡、插入排序和选择排序算法来排序。

#include<iostream>
    #include <time.h>  
    using namespace std;
    
    int main()
    {    
        double cost = 0;
        for (int i = 0; i <10000; i++)
        {
            const int size = 200;
            int vec[size];
            GenVector(vec, size);
    
            double start, end;
            start = clock();      
            // BubbleSort(vec, size);
            //InsertSort(vec, size);
           // SelectSort(vec, size);
            end = clock();
            cost += (end - start) / CLOCKS_PER_SEC;
        }
       
        cout << cost << endl;
        getchar();
        return 0;
    }

运行结果:

[n_2]: https://private.codecogs.com/gif.latex?n%5E%7B2%7D