算法学习 - 基础排序算法

最近在学习算法与数据结构，算法是一个程序员的基本功，但是我不是科班出身，所以这方面的知识有所欠缺。在慕课网上找到一套对应的课程，主讲老师是liuyubobobo,从我学习的感受和体验来看，bobo老师对一个问题讲解的相当清晰和透彻，普通话说的也好，适合初学者理解和学习。大家如果想学习算法与数据结构的知识，我推荐这一套教程。地址链接：https://coding.imooc.com/class/71.html。 这一系列文章主要是对这套课程的内容以文字的形式展示。做这个事情一是想对视频上的知识点在通过形成文字的过程中，加深自己的理解。二是想加强自己的表达能力。

这篇文章主要讲解3个基础的排序算法，选择排序，插入排序，以及冒泡排序，其时间复杂度都是0(n^2)级别的，实现代码使用c++语言。

选择排序

首先给定一个元素是无序的整数数组：

image

需要对这个数组中的8个整数进行从小到大的排序。

选择排序的基本思路

首先从起始位置index = 0开始，遍历一遍数组，获取到最小的元素值index = 4 的元素，元素值为1，然后将index = 0与index = 4 上的两个元素交换位置，此时index = 0 上的元素值1。index = 4上的元素值为5。红色为已排序完成的有序区域。

image

找到了最小的元素放在数组的第一位后，接着从index = 1开始往后遍历数组。找到第二小的元素后再与index = 1的位置交换元素，此时，index = 1上的元素值为2，index = 2 上的元素为4.

image

接着再从index = 2的位置往后遍历数组，找到第三小的元素后再与index = 2上的元素交换位置，交换后，index = 2上的元素为3，index = 5 上的元素为4。

image

然后依此遍历的方法，直到数组的最后一个位置存放的是最大的元素。选择排序的整体思想不难理解，就是循环一遍数组找到循环元素中最小的元素，再与已排好序的下一个索引上的元素交换位置。

代码实现

我写成一个函数，传入一个数组以及元素的个数：

template <typename T>
void selectionSort(T arr[],int n){
    
    for (int i = 0; i < n; i++) {
        int minIndex = i; // minIndex保存内层循环中最小值的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

插入排序

插入排序的基本思路

bobo老师打个这样一个比方，我觉得用来理解插入排序非常合适：就好像有一副牌，三个人用这副牌来斗地主，分牌阶段，你需要将你摸到的牌放在手中的牌中的合适位置，手中的牌是整理好的，是有序的，放入后，使其整体依旧有序。我们来模拟一下这个过程。首先固定手中有一张牌，用红色标记为手中已整理好的牌。

image

接着摸第二张牌，为4，比5小，所以放在5的前面，4与5交换位置。

image

接着摸第三张牌，为2，2比5小，所以先放在5的前面，4的后面。

image

此时这里并不是2合适的位置，继续和前面的元素比较，2比4小，所以要放到4的前面。此时变成有序了。

[图片上传失败...(image-231474-1535017882614)]

接着再摸第四张牌，为7，7比5小，发现不用交换位置，放在原地就好了。

image

就这样，按照这个方法，将摸到的牌与整理好的牌依次做比较，使其放在合适的位置，直到摸完最后一张牌。

代码实现

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

注意：第一层for循环时 i = 1，i不是从零开始。因为第一张牌不需要排序，从第二张牌开始。所以设置i = 1。

在[0 i) 前闭后开这个区间中为已排好序的元素，i为待排序的元素的索引，第二层for循环是从待整理的元素索引i开始。在已排好序的区间[0,i)中，从后往前遍历。 如果发现前面的元素比它大，则两个元素交换位置。当发现前面的元素比它小的时候，此时它就找到了合适的位置。就不需要再遍历了，直接结束这一层循环。

插入排序优化

在交换两个元素位置的时候,调用了swap(arr[j - 1],arr[j])，而一次交换其实是三次赋值，这句代码其实也可以改写为：

int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;

如果一个较小的元素要插入到合适的位置，肯定要一路交换很多次。这无形中就增加了排序时间。优化思路就是只进行赋值操作而不进行交换操作，先保存一份待排序的元素，然后遍历已排好序的元素，从后往前进行逐一比较，如果当遍历到index = j的元素时，j - 1索引上的元素要比j位置上的元素大，则将j - 1索引位置的元素往后挪，往后挪也就是将j索引位置的元素赋值为j-1索引位置的元素，当遍历到j-1索引上的元素比元素j位置上的元素小或相等时，就说明上一次循环往后挪而腾出来的位置为待排序的合适位置，在将该位置的值赋值为待排序的值就好了。

假定现在按照优化的思路对1进行排序，红色为已排好序的部分。

image

首先先复制一份待排序的元素1

image

然后将待排序的元素与已排好序的index = 3位置，值为7的元素比较，如果这个元素比待排序的元素要大，则直接将待排序的值复制为这个元素。7 比 1 大，7往后挪，所以待排序位置上的元素值赋值为7，而index = 3位置就腾出来了。

image

然后依次往前与带排序的元素比较。这次是index = 2 时的 5 与 1比较， 5比1大，5往后挪，将index = 3 位置上的元素赋值为5，index = 2这个位置就腾出来了。

image

再将index = 1 时的4 与 待排序的元素1比较，4 还是比1 大，4往后挪，将 index = 2位置赋值为4，index = 1这个位置就腾出来了。

image

继续。再将index = 0时的2, 与待排序的元素1比较，2还是比1大，2往后挪，将index = 1位置赋值为2，index = 0这个位置腾出来了。

image

那么腾出来的位置上为元素的前面已没有元素可以比较了。所以此时在index = 0的位置上放置上待排序的元素。

image

元素1经过一番波折，尘埃落定，终于找到了他合适的位置，元素1排序完毕

image

然后index = 5上的元素3按照上述方法找到合适的位置，index = 6 上的元素按照上述方法找到合适的位置，接着是index = 7上的元素。将所有的元素都按照上述方法找到自己合适的位置。

代码实现

template <typename T>
void insertionSort(T arr[],int n){
    
    for (int i = 1; i < n; i++) {
        T e = arr[i]; // 保存待插入索引为i时的元素e
        int j = i; // j保存元素e应该插入的位置
        for (j = i; j > 0; j--) {
            if (arr[j-1] > e) {
                arr[j] = arr[j-1];
            }
        }
        arr[j] = e;
    }
}

冒泡排序

冒泡排序实现思路

首先还是这一个由8个数组成的一个无序的数组

image

冒泡排序的核心思想就是将相邻的两个元素两两比较，根据大小来交换元素的位置

首先，5与4比较，5比4大，我们的需求是从小到达排列，4需要在5的前面，所以4与5交换位置，红色表示两个要交换位置的元素。

image

交换后

image

然后, 5与2开始比较，5比2大，交换位置

image

交换后

image

继续， 5和7比较，5比7小，位置保持不变

image

go on， 7与1比较，7比1大，交换位置

image

交换后

image

不要停，7与3比较，7比3大，交换位置

image

交换后

image

继续深入， 7与8比较，7比8小，保持不变

image

还有最后一个，8与6比，8比6大，交换位置

image

交换后

image

这样一轮下来，元素8排到了最右侧，此时红色代表️已排好序的区域

image

接着按照上述方法，重新重头开始相邻元素两两遍历，前一个元素比后一个元素大则交换位置，小则保持位置不变，一路比较下来。找到第二大的元素放到元素8的左侧。

image

然后是

image

然后是

image

给定的一组无序的整数数组，按照排序的思路来讲，蓝色区域属于无序的区域，还需要比较，但是上面图片中蓝色部分已经是有序的了，这可以作为一个优化的方面，就是当发现代排区域中的元素已经是有序了的时候，排序完成，结束排序，下面的代码中不涉及这部分的优化。

实现代码

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

代码不难理解，双层循环，外层每一次循环确定一个最大值放在数组的右侧，内层寻找这个最大值。先进行元素比较，满足则交换。

冒泡排序的优化

刚刚在逐步比较的时候，出现了这样一种情况：蓝色的无序区域中的元素已经是有序的了。

image

但是上面的冒泡排序的代码还会继续的比较下去。每一个元素都会参与外层循环，直到循环结束。所以优化方向是在无序区域中的元素已经有序了的情况下结束循环。
优化后的代码,部分解释见注释。

void BubbleSort(T arr[],int n){
    
    for (int i = 0; i < n; i++) {
        bool isSorted = true; // 用一个bool值来标记每一层是否是有序的，默认为true.
        
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j],arr[j+1]);
                isSorted = false; // 如果有交换元素，那么不是有序，该bool值改为false.
            }
        }
        if (isSorted) { // 在内层中，如果该bool值没有被改为false,那么就说明内层没有元素交换，那么该数列排序完成了，直接结束循环。
            break;
        }
    }
}

这个优化主要是用一个bool值做标记，来确定是否有序。在内层循环中如果没有元素交换，那么这个数列肯定就是有序的了，那么外层就无需在循环了。

下次学习内容：归并排序