Paul's notes
文章目录 关于 简体中文
Paul's notes

目录

直接插入、冒泡、简单选择排序分析

   约 2650 字   预计阅读 6 分钟 

最简单的三个排序算法分析

写作日期：2018年6月21日

注：本文所讨论的排序均为升序排序（考虑待排数组可含重复元素，严格的说是非降序排序） 代码均用C++编写 为方便表述，数组子项称元素

直接插入排序

思路

待排数组分为左右两半，左半放已排好的元素，右半放待排元素
排序的过程就是将左半大小从0变大，直至右半大小为0的过程

顾名思义，直接插入就是将右半元素逐一插入到左半合适位置

如何插入（插入到指定位置前面还是后面，不注意就弄晕了）？
左半是从小到大顺序的，找到合适位置后，此位置后元素全部后移一位，插入

动手写代码看看
首先“准备”好需要的内容：待排数组、数组大小
接下来就是在函数体内写两个for循环，想好思路怎么用代码实现，考虑好边界问题，最后想想有无 可优化之处

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <stdio.h>
#include <cstdlib>

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

int main() {
    int A[9] = {-1, 5, 9, 3, 1, 11, 31, 54, 19};
    int n = 9;
    InsertSort(A, n);
    for (int i = 0; i <= n - 1; i++)
        printf("%d    ", A[i]);
    std::system("pause");
}

C:\Users\wwo\Desktop\workplace\clion_learn_c_cpp\cmake-build-debug\test.exe -1 1 3 5 9 11 19 31 54 请按任意键继续. . .

然而上面的代码还有要优化的地方：

  1. 第2个for循环内，只要把判断条件i<n-1改一下就行，没有必要用上break（可以少好几行代码呢）
  2. 如果用A[0]替代temp，可以少用一个变量，数组从1开始感觉好一点（然而并没有更好，测试用的数组等等还要改一下，全是为了配合上一条优化思路）

新的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>
#include <cstdlib>

void InsertSort(int A[], int n) {
    int i, j;
    for (i = 1; i < n - 1; i++) {
        A[0] = A[i + 1];
        for (j = i + 1; A[j - 1] > A[0]; j--)
            A[j] = A[j - 1];
        A[j] = A[0];
    }
}

int main() {
    int A[10] = {0, -1, 5, 9, 3, 1, 11, 31, 54, 19};
    int n = 10;
    InsertSort(A, n);
    for (int i = 1; i <= n - 1; i++)
        printf("%d    ", A[i]);
    std::system("pause");
}

重新编译运行输出结果如下：

C:\Users\wwo\Desktop\workplace\clion_learn_c_cpp\cmake-build-debug\test.exe -1 1 3 5 9 11 19 31 54 请按任意键继续. . .

性质及复杂度

主要分析排序的稳定性即排序的时间复杂度、空间复杂度

稳定性概念：若排序前后值相等元素的相对位置发生变化，称用到的排序算法为不稳定的，否则稳定
个人分析：排序算法实际应用时，往往要考虑稳定性，因为有的应用场景介意不稳定的排序算法，试想Excel多条件筛选的时候，如果用的排序是不稳定的，岂不是会影响最后结果？当然如果待排序列没有重复元素，稳定性就不是选择算法时需要考虑的因素了。

稳定性分析：从代码和思路可以看出，此算法第一个循环按顺序取元素，第二个循环是往后挪位置，大于取出元素的时候才往后挪，换句话说，等于及小于的元素位置不动。因此是可以说是稳定排序（它确实就是稳定排序）。
刁钻分析：此算法稍微改一下就成了不稳定排序，然而为什么一般教材上和网上都说它是稳定排序呢？

如何把此算法改成不稳定的？
只要第二个循环内中间循环条件i < n - 1改成 i <= n - 1，插入的时候就成了插到元素前（如果看不懂，说明此排序算法还没弄懂，没弄懂不建议研究性质），此时相等元素排序前后相对位置发生了改变，可说是不稳定的。

由于稳定性具有优势，据合理推测，如果算法能写成稳定的，就说此算法是稳定的；如果算法只能写成不稳定的，就说此算法是不稳定的。

再延伸一下，可以推断，不稳定的排序算法，都是不可能写成稳定排序的排序算法。

时间复杂度
最好情况下：最好情况即为待排序列已经是升序的了，此时用上此直接插入排序算法，只需要比较n次确定有序，而不用移动位置，时间复杂度为O(n)

最坏情况下：最坏情况即为待排序列全部降序，要用此算法把它排成升序的，总共比较次数$\Sigma^{n-1}_{i=1}i$，总共移动元素次数$\Sigma_{i=1}^{n-1}i$，总共就是$2\Sigma^{n-1}_{i=1}i$，用等差数列求和公式算出来是$n^2-n$，取最高次幂即O($n^2$)

平均情况下：因为待排序列是随机的，平均情况可取最好情况和最坏情况的平均值，总比较次数和总移动次数为？？，即O($n^2$)

空间复杂度：用了常数个辅助单元，空间复杂度为O(1)（大欧，无穷大无穷小问题的内容，小欧常出现在泰勒公式里）

冒泡排序

思路

从左到右，每一个位置起一轮冒泡。

冒泡方式：向左冒泡，即如果当前位置元素比左边的小，就交换位置，冒完一轮最小值在最左边

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <stdio.h>
#include <cstdlib>

void BubbleSort(int A[], int n) {
    int i, j;
    for (i = 2; i < n ; i++) {
        for(j = i; j > 1; j--)
            if(A[j] < A[j - 1]) {
                A[0] = A[j];
                A[j] = A[j - 1];
                A[j-1] = A[0];
            }
    }
}

int main() {
    int A[10] = {0, -1, 5, 9, 3, 1, 11, 31, 54, 19};
    int n = 10;
    BubbleSort(A, n);
    for (int i = 1; i <= n - 1; i++)
        printf("%d    ", A[i]);
    std::system("pause") ;
}

C:\Users\wwo\Desktop\workplace\clion_learn_c_cpp\cmake-build-debug\test.exe -1 1 3 5 9 11 19 31 54 请按任意键继续. . .

优化思路

  1. 如果内循环没有进行任何元素位置交换，则说明当前状态下已经有序，可以不用进行大小比较了
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>
#include <cstdlib>

void BubbleSort(int A[], int n) {
    int i, j, flag; // +
    for (i = 2; i < n ; i++) {
        flag = 0; // +
        for(j = i; j > 1;j--)
            if(A[j]<A[j - 1]){
                A[0] = A[j];
                A[j] = A[j - 1];
                A[j - 1] = A[0];
                flag = 1;
            }
        if(flag == 0) // +
            return; // +
    }
}

性质及复杂度

稳定性:因为向左冒泡的时候，只有左边小于右边才会交换位置（看for里面的条件），碰到了两个相等的时候不交换，故此算法是稳定的

时间复杂度

突然意识到，时间复杂度这个问题，可以但是没必要算出语句运行次数，直接进行大O运算就够了，没必要研究那么细

附公式

O(a)+O(b)=O(max(a,b))

O(a)*O(b) = O(a+b)

最好情况下：至少跑完一圈外循环才能发现已经是升序的了，O(n)。（此处易误认为是O(1)，注意n是问题规模，它是个变量，而不是常量）

最坏情况下：O($n^2$)

平均情况下：O($n^2$)

简单选择排序

思路

待排序列分成左右两边，左边排好，右边待排
每次从右边取最小元素放到左边

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
#include <cstdlib>


void SelectSort(int A[], int n) {
    int i, j, min;
    for(i = 1;i < n - 1; i++){
        min = i;
        for(j = i + 1; j <= n - 1; j++){
            if(A[j] < A[min]){
                min = j;
            }
        }
        if(i != min){
            A[0] = A[i];
            A[i] = A[min];
            A[min] = A[0];
        }
    }
}

int main() {
    int A[10] = {0, -1, 5, 9, 3, 1, 11, 31, 54, 19};
    int n = 10;
    SelectSort(A, n);
    for (int i = 1; i <= n - 1; i++)
        printf("%d    ", A[i]);
    std::system("pause") ;
}

运行结果：

C:\Users\wwo\Desktop\workplace\clion_learn_c_cpp\cmake-build-debug\test.exe -1 1 3 5 9 11 19 31 54 请按任意键继续. . .

优化思路：此算法没什么好优化的，顶多把那个三行语句交换换成一行，这也不算优化

1
2
3
4
5
6
7
8
9

if(i!=min){
    A[0] = A[i];
    A[i] = A[min];
    A[min] = A[0];
}
//改成
if(i!=min)
    swap(A[i],A[min])

方便手写撕代码，实际运行的时候，swap函数的写法注意一下：

1
2
3
4
5
6

void swap(int &a, int &b){
    int temp;
    temp = a;
    a = b;
    b = temp; 
}

性质及复杂度

稳定性：在右边挑元素的时候，只有被挑的元素小于最小值（等于不算，看代码if(A[j] < A[min])）才会被选，此算法是稳定的

时间复杂度
最好情况下：最好的情况下，内循环跑满，O($n^2$)
最坏情况下：两层循环，全跑满，O($n^2$)
平均情况下：O($n^2$)

更新于 2022-03-17
返回 | 主页