在两位亦师亦友的朋友的帮助下，准备从零开始学习算法，第一课是从最简单的排序算法开始学习。
本篇文章中的内容是看了别人的文章和书籍的总结，再加上两位朋友的细心教导，最后加上自己的理解。

1.排序介绍

在本文中，我们会依次来介绍10中排序方法分别是：冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序、桶排序、计数排序、基数排序、堆排序。

在排序的过程中我们会分析算法中几个基本的特点：

• 时间复杂度：算法执行需要的时间。
• 空间复杂度：算法执行需要的额外的空间（内存）。
• 稳定性：算法执行过程中相同的数字相对位置是否交换。
  在文章提到的所有的排序的数据都默认是正整数，排序的顺序是递增。

2.排序详解

2.1.冒泡排序（Bubble Sort）

冒泡排序是一种较简单的排序方法，基本的流程就是：

1. 遍历所有的数据，比较相邻的两个数字，如果左边的大于右边的数字，就交换。经过一次遍历之后，数组中最大的数字就会在数组的末尾了。
2. 重复1步骤，直到数组中所有的数字右边的都比左边的大，这样就完成了一个有序的数组，就像水中的气泡一样，慢慢浮上了水面。

vector<int> bubbleSort1(vector<int> arr) {
    int count = arr.size();
    for (int i = 1; i < count; i++) {
        for (int j = 1; j < count - i; j++) {
            if (arr[j] < arr[j - 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
    return arr;
}

从上述代码中可以看出，冒泡排序的需要两层循环，所以时间复杂度为，排序过程中只用到了常数级的额外空间，所以空间复杂度为，算法中只有在左边大于右边的时候才交换，相同数字的相对位置没有改变，所以是一种稳定的排序算法。

优化

但是如果数据已经是有序的呢？上面的算法的时间复杂度还是，所以我们需要对算法改进一下，让它在有序的情况下只遍历一次就够了，下面的算法就是使用一个标记来记录数组是否被交换过，如果交换过，说明数组是无序的，如果没有交换过，说明数组已经是有序的了。这样在已经有序的情况下时间复杂度为。

vector<int> bubbleSort2(vector<int> arr) {
    // 记录是否交换
    bool flag = true;
    while (flag) {
        flag = false;
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] < arr[i - 1]) {
                // 交换
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                flag = true;
            }
        }
    }
    return arr;
}

2.2.选择排序（Selection Sort）

选择排序是一种简单直观的排序方法，基本的流程就是：

1.从待排序的数组中选出一个最小的数据，放在起始位置。
2.从剩余待排序的数组中选出一个最小的数据，放到已排序数组的末尾位置。
3.重复2步骤，直到所有的数组都变成已排序。

vector<int> selectionSort(vector<int> arr) {
    int minIndex;
    for (int i = 0; i < arr.size() - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            // 先找出一个最小的数
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        // 和第i位交换
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

从上述代码中可以看出，选择排序需要两层循环，所以时间复杂度为，排序过程中只用到了常数级的额外空间，所以空间复杂度为，选择排序虽然和冒泡排序虽然类似，但是却是一种不稳定的排序算法。

举个🌰：假如有数组[4, 5, 4, 3, 6]，当第一次循环的时候，3是最小的数据，所以3和第一个4交换，如此以来两个4的相对位置就已经发生了变化，所以是不稳定的排序算法。

2.3.插入排序（Insertion Sort）

插入排序是一种简单直观的排序方法，基本的流程就是：

1.先将数组分成两部分：已排序和待排序，已排序的数组默认放一个。
2.从剩余待排序的数组起始位置取一个，插入到已排序数组的相应位置。
3.重复2步骤，直到所有的数组都变成已排序。

vector<int> insertionSort(vector<int> arr) {
    // 已经排好序的位置
    int sortedIndex = 0;
    int current;
    // 遍历未排序的数组
    for (int i = 1; i < arr.size(); i++) {
        current = arr[i];
        // 把取出来的数据插入到已排序的数组中
        for (int j = sortedIndex; j >= 0; j--) {
            if (current > arr[j]) {
                arr[j + 1] = current;
                sortedIndex++;
                break;
            } else if (current < arr[j]) {
                arr[j + 1] = arr[j];
                if (j == 0) {
                    arr[0] = current;
                    sortedIndex++;
                    break;
                }
            }
        }
    }
    return arr;
}

从上述代码中可以看出，插入排序需要两层循环，所以时间复杂度为，排序过程中只使用了常数级的额外空间，所以空间复杂度为，插入排序是一种稳定的排序算法，插入过程中相同元素的相对位置不会变化。

2.4.快速排序（Quick Sort）

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1.先确定一个关键值，重新排列数组，把比关键值小的放在关键值的左边，把比关键值大的放在关键值的右边。
2.把数组从关键值分割成两个数组，分别把两个新的数组执行步骤1。
3.重复2步骤，直到最小的数组不能分割，现在数组就已经是一个有序的数组了。

void quickSorting(vector<int> &arr, int low, int high) {
    if (low >= high) {
        return;
    }
    // 先保存左右点
    int left = low;
    int right = high;
    // 默认关键值为数组的最左边的点
    int key = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= key) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= key) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = key;
    quickSorting(arr, low, left - 1);
    quickSorting(arr, left + 1, high);
}

vector<int> quickSort(vector<int> arr) {
    quickSorting(arr, 0, arr.size() - 1);
    return arr;
}

从上述代码中可以看出，快速排序是递归调用函数，所以时间复杂度为，空间复杂度也为为（作为算法新手的我其实并不会推导，我也是死记的），快速排序涉及到多次交换，是一种不稳定的排序算法（这里不好举🌰，等我想到合适的再加上）。

2.5.希尔排序（Shell Sort）

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序的改进版，基本的流程就是：

1.先设定一个步长，数组中距离为步长的数据都被编成一组，统一我们都取数组长度的二分之一，特别说明一下这里，如果步长是数组长度的二分之一，那么就是两个数据一组，首先我们会先对这两个数据进行排序。
2.完成所有组排序之后，把步长除2，那数组中的数据就变成了4个一组，继续对数组中的数据排序。
3.完成所有组排序之后，把步长除2，继续对数组中的数据排序。
4.重复步骤3，直到步长为1，这时候数组就剩下一个了，就是我们最终需要的已经排序的数组。

vector<int> shellSort(vector<int> arr) {
    int step = arr.size() / 2;
    while(step >= 1) {
        // 把距离为step的元素编为一组 扫描所有组
        for (int i = step; i < arr.size(); i++) {
            int j = 0;
            int temp = arr[i];
            // 对距离为gap的元素组进行排序
            for (j = i - step; j >= 0 && temp < arr[j]; j = j - step) {
                arr[j + step] = arr[j];
            }
            arr[j + step] = temp;
        }
        // 减小步长
        step /= 2;
    }
    return arr;
}

从上述代码中可以看出，希尔排序虽然是两层循环，但是时间复杂度并不是，因为两层循环的此次都是远远小于n的，所以平均时间复杂度为（弱鸡的我还是不知道是怎么推导出来的），只使用了常数单位的额外空间，空间复杂度为，是一种不稳定的排序算法。

2.6.归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再让子序列段合并成有序的序列，基本的流程就是：

1.先把现有的数组分成两个数组。
2.再分别对两个数组进行归并排序。
3.把已经排序好的两个数组合并成一个新的有序数组。

vector<int> merge(vector<int> left, vector<int> right) {
    vector<int> res;
    // 两个数组归并为一个数组
    int one = 0;
    int two = 0;
    while (one < left.size() && two < right.size()) {
        if (left[one] < right[two]) {
            res.push_back(left[one++]);
        } else {
            res.push_back(right[two++]);
        }
    }
    
    while (one < left.size()) {
        res.push_back(left[one++]);
    }
    
    while (two < right.size()) {
        res.push_back(right[two++]);
    }
    return res;
}

vector<int> mergeSort(vector<int> arr) {
    if (arr.size() < 2) {
        return arr;
    }
    // 先将数组分为两个
    int mid = arr.size() / 2;
    vector<int> left, right;
    copy(arr.begin(), arr.begin() + mid, back_inserter(left));
    copy(arr.begin() + mid, arr.end(), back_inserter(right));
    
    return merge(mergeSort(left), mergeSort(right));
}

从上述代码中可以看出，归并排序是递归调用函数，所以时间复杂度为，归并排序的递归是在排序的过程中，但是内存的消耗却是在合并的过程中，所以空间复杂度为，是一种稳定的排序算法。

2.7.桶排序（Bucket Sort）

桶排序又称箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
后面的几种排序主要是偏理解，所以我都先举个🌰来说明一下：

假如，现在有1w个年龄不等的人（最大年龄为110， 最小年龄为1岁），需要按照年龄的升序来排列。
那我们就可以创建11个桶，编号为1的桶都放1-10岁的人，编号为2的桶都放11-20岁的人，把所有的人都依次放到桶中，分别排序每个桶中的数据，最后按顺序合并称一个大数组，就是最后需要的已排序的数组了。

基本的流程就是：

1.先计算需要的桶的数量。
2.分别把所有数组存放到相应的桶中。
3.把每个桶中的数据使用快速排序进行排序。
4.把所有桶中的数据依次合并成一个大数组，就是最后需要的已排序的数组了。

vector<int> bucketSort(vector<int> arr) {
    if (arr.size() < 2) {
        return arr;
    }
    // 先找出排序数组中的最大和最小的元素
    int maxInt = arr.front();
    int minInt = arr.front();
    for (int i = 0; i < arr.size(); i++) {
        maxInt = max(arr[i], maxInt);
        minInt = min(arr[i], minInt);
    }
    
    // 初始化桶
    // 桶大小
    int bucketSize = 5;
    // 桶个数 向上取整
    int bucketCount = ceil((maxInt - minInt + 1) / 5.0);
    vector<vector<int>> bucket(bucketCount);
    
    for (int i = 0; i < arr.size(); i++) {
        // 判断放到哪一个桶中
        int index = (arr[i] - minInt) / bucketSize;
        bucket[index].push_back(arr[i]);
    }
    
    // 分别对每个桶中的数据快速排序
    arr.resize(0);
    for (int i = 0; i < bucket.size(); i++) {
        if (bucket[i].size() > 0) {
            quickSort(bucket[i]);
            arr.insert(arr.end(), bucket[i].begin(), bucket[i].end());
        }
    }
    return arr;
}

从上述代码中可以看出，桶排序是两个并列的循环，如果数据的个数为n，桶的数量为m，个人理解是因为已经分成了m个桶了，快速排序的时间可以忽略不计，所以时间复杂度为，空间复杂度为（但是具体的公式还是需要通过推导出来），是一种稳定的排序算法。

2.8.计数排序（Counting Sort）

计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
其实计数排序是桶排序的一种情况，举个🌰来说明一下（还是上面的例子）：

假如，现在有1w个年龄不等的人（最大年龄为110， 最小年龄为1岁），需要按照年龄的升序来排列。
那我们就可以创建110个桶，编号为1的桶都放1岁的人，编号为2的桶都放2岁的人，把所有的人都依次放到桶中，（这里并不需要再次排序，因为每一个桶中的人年龄都是相同的），最后按顺序合并称一个大数组，就是最后需要的已排序的数组了。

基本的流程就是：

1.先计算需要的桶的数量。
2.分别把各个数据的个数存放到相应的桶中。
3.根据数据的数量，依次合并成一个大数组，就是需要的已排序的数组了。

vector<int> countingSort(vector<int> arr) {
    if (arr.size() < 2) {
        return arr;
    }
    // 先找出排序数组中的最大和最小的元素
    int maxInt = arr.front();
    int minInt = arr.front();
    for (int i = 0; i < arr.size(); i++) {
        maxInt = max(arr[i], maxInt);
        minInt = min(arr[i], minInt);
    }
    
    // 创建一个数组可以承载最小到最大值中的所有的元素。
    vector<int> bucket(maxInt - minInt + 1);
    for (int i = 0; i < arr.size(); i++) {
        bucket[arr[i] - minInt]++;
    }
    
    int index = 0;
    for (int i = 0; i < bucket.size(); i++) {
        while (bucket[i] > 0) {
            arr[index++] = i;
            bucket[i]--;
        }
    }
    return arr;
}

从上述代码中可以看出，计数排序和桶排序一样，所以时间复杂度为，空间复杂度为（但是具体的公式还是需要通过推导出来），是一种稳定的排序算法。

但是一般都会有一个问题，既然和桶排序这么像，那为什么还叫计数排序，直接叫桶排序好了，原因是我们在存数据的时候并没有存具体的数据，而是存的数据的数量，所以叫计数排序。

2.9.基数排序（Radix Sort）

基数排序属于“分配式排序”，又称“桶子法”，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

举个🌰来说明一下：

假如，现在有1w个11位的手机号码，需要按照升序来排列。
那我们就可以创建10个桶（分别编号为0-10），把倒数第一个数字和桶编号相同的数据放在一个桶中。
已经排序好的数据，继续把倒数第二个数字和桶编号相同的数据放在一个桶中，一直重复，直到把第一个数字和桶编号相同的数据放在一个桶中。
最后按顺序合并称一个大数组，就是最后需要的已排序的数组了。

基本的流程就是：

1.先计算需要的桶的数量，如果是正整数，我们的桶数量一般都是10。
2.把倒数第一个数字和桶编号相同的数据放在一个桶中。
3.重复步骤2，直到把第一个数字和桶编号相同的数据放在一个桶中
4.把桶中的数据取出，依次合并成一个大数组，就是需要的已排序的数组了。

vector<int> radixSort(vector<int> arr) {
    if (arr.size() < 2) {
        return arr;
    }
    
    // 先找出排序数组中的最大和最小的元素
    int maxInt = arr.front();
    for (int i = 0; i < arr.size(); i++) {
        maxInt = max(arr[i], maxInt);
    }
    
    // 求出最大的位数
    int maxDigit = 1;
    while (maxInt / 10 > 0) {
        maxInt = maxInt / 10;
        maxDigit++;
    }
    
    for (int i = 0; i < maxDigit; i++) {
        // 创建一个数组为10的数组
        vector<vector<int>> bucket(10);
        // 分别放到不同的桶中
        for (int j = 0; j < arr.size(); j++) {
            // 计算i个位置的数
            int num = (arr[j] % (int)pow(10, i + 1)) / (int)pow(10, i);
            bucket[num].push_back(arr[j]);
        }
        
        // 把桶中的数据重新取出
        arr.resize(0);
        for (int j = 0; j < bucket.size(); j++) {
            if (bucket[j].size() > 0) {
                for (int k = 0; k < bucket[j].size(); k++) {
                    arr.push_back(bucket[j][k]);
                }
            }
        }
    }
    return arr;
}

从上述代码中可以看出，基数排序是两层循环，如果数据的个数为n，桶的数量为m（桶的数量是根据数据的最大位数决定的），所以时间复杂度为，空间复杂度为（但是具体的公式还是需要通过推导出来），是一种稳定的排序算法。

2.10.堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
最后一个堆排序可能相对于其他的排序比较难理解一点，需要一定的二叉树的知识，才可以理解堆的结构，其实就是一个父节点比子节点大（或者子节点比父节点大）的完全二叉树。

基本的流程就是：

1.先创建一个大顶堆，就是父节点比子节点大的堆。
2.把大顶堆最顶部的一个数据，和最末尾的一个数据交换，这样最大的数据就到了最后面了。
3.重新把剩余的数据，重新变成一个大顶堆，然后在把大顶堆最顶部的一个数据，和未排序最末尾的一个数据交换。
4.重复3步骤，最后就得到了一个有序的数组。

int len;
// 堆化
void adjustHeap(vector<int> &arr, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int top = i;
    
    if (left < len && arr[left] > arr[top]) {
        top = left;
    }
    if (right < len && arr[right] > arr[top]) {
        top = right;
    }
    
    if (top != i) {
        int temp = arr[i];
        arr[i] = arr[top];
        arr[top] = temp;
        adjustHeap(arr, top);
    }
}

// 创建大顶堆
void buildHeap(vector<int> &arr) {
    // 现在是一个无序的普通的堆
    for (int i = arr.size() / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i);
    }
}

vector<int> heapSort(vector<int> arr) {
    if (arr.size() < 2) {
        return arr;
    }
    len = arr.size();
    buildHeap(arr);
    
    for (int i = arr.size() - 1; i > 0; i--) {
        // 交换
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        // 需要实时记录一个len
        len--;
        // 重新排列成为大顶堆 从上到下
        adjustHeap(arr, 0);
    }
    return arr;
}

从上述代码中可以看出，堆排序主要时间消耗是在堆化的过程，是一个递归的过程，所以时间复杂度为，（但是具体的公式还是需要通过推导出来），堆是原地排序，所以空间复杂度为，是一种不稳定的排序算法。

结束语

• 以上算法还没有经过大数据的测试，所以在有些情况下也许没有达到排序的效果，发现有问题的同学可以帮忙指出不足。
• 后面的三种排序算法：桶排序、基数排序、计数排序，虽然效率更快，但是有一定的场景的限制，所以平时使用的并不是很多。
• 看时间复杂度和空间复杂度，堆排序比快速排序感觉还更好一点，但是在实际的运用中快速排序的运用更加的广泛，因为堆排序的操作比较繁琐，建堆和堆化，而且堆是基于二叉树的，所以一般都是使用指针来存储，创建堆的时候内存就有一定的消耗，还有对计算机的内存是不友好的，是碎片存储的。
• 快速排序也不是万能的排序，也有自己的不足之处，比如日常运用中数据量比较大的情况下，需要防止堆栈溢出，解决方法是：我们可以模拟递归的出栈入栈，达到递归相同的效果。
• 如果是已经有序的数组，快速排序的时间复杂度为，但是怎么才可以较好的优化这个算法呢？希望知道的朋友可以教我一下，谢谢了。

参考资料

《编程珠玑》，《算法第四版》，王争的《数据结构与算法之美》