十大排序算法（慢慢更新）

冒泡排序（升序）：

基本思想：冒泡排序是一种简单的排序算法，其核心思想是通过相邻元素的比较和交换，使得每一轮遍历都能将未排序部分中的最大元素“冒泡”到未排序部分的末尾，最终使数组按升序排列。经过多次这样的遍历，数组会变得有序。直接上代码，这个还是很好理解的，个人感觉。

        结合下面的代码和输出，手动推一遍就没问题了。代码中加了很多便于定位的输出，使用的时候删掉这些输出就可以了，应该是问题不大的。

#include <iostream>
#include <vector>
using namespace std;
// 打印数组
void printVector(const vector<int>& vec) {
    for (const auto& elem : vec) {
        cout << elem << " ";
    }
    cout << endl;
}
// 冒泡排序算法
void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
		cout<<"开始第"<<i+1<<"轮排序："<<endl;
        // 用于标记本轮是否发生交换
		bool swapped = false; 
		//从索引为0开始，相邻数据依次比较，大的换到前面去
        for (int j = 0; j < n - i - 1; j++) {
           cout<<"  "<<"排序中......"<<endl; 
			if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
				cout<<"  ";
				printVector(nums);
            }
        }
		cout<<"  "<<"第"<<i+1<<"轮排序后的数组：";
		printVector(nums);
        // 如果本轮没有发生交换，说明数组已经有序，可以提前结束排序
        if (!swapped) {
            break;
        }
    }
}
int main() {
    vector<int> nums = {5, 3, 8, 1, 2, 7};
    cout << "排序前的数组：";
    printVector(nums);
    bubbleSort(nums);
    cout << "冒泡排序后的数组：";
    printVector(nums);

    return 0;
}

 上面代码的输出：【显示“排序中......”之后却没有显示数据说明 这次比较没有进行数据交换】

排序前的数组：5 3 8 1 2 7 
开始第1轮排序：
  排序中......
  3 5 8 1 2 7 
  排序中......
  排序中......
  3 5 1 8 2 7 
  排序中......
  3 5 1 2 8 7 
  排序中......
  3 5 1 2 7 8 
  第1轮排序后的数组：3 5 1 2 7 8 
开始第2轮排序：
  排序中......
  排序中......
  3 1 5 2 7 8 
  排序中......
  3 1 2 5 7 8 
  排序中......
  第2轮排序后的数组：3 1 2 5 7 8 
开始第3轮排序：
  排序中......
  1 3 2 5 7 8 
  排序中......
  1 2 3 5 7 8 
  排序中......
  第3轮排序后的数组：1 2 3 5 7 8 
开始第4轮排序：
  排序中......
  排序中......
  第4轮排序后的数组：1 2 3 5 7 8 
冒泡排序后的数组：1 2 3 5 7 8 

快速排序（升序）：

基本思想见文章：排序——快速排序（Quick sort）-CSDN博客

        感觉很好理解，但是感觉它的代码和他讲的思想有点对不上，所以自己按照文章讲的思想重新写了一下，对照上面的思想，还有下面的代码和输出，一步一步推导写一下应该很快就可以掌握。

#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>

//输出vector数组函数
void printVector(const vector<int>& vec) {
    for (const auto& elem : vec) {
        cout << elem << " ";
    }
    cout << endl;
}
//快速排序算法【输出cout可删】
void quickSort(vector<int>& nums, int left, int right) {
    // 左端点大于等于右端点 递归结束
    if (left >= right) {
        return;
    }
    cout << "进行快速排序前的边界分别是left=" << left << "right=" << right<< endl;
    cout << "进行快速排序前的数组：" << endl;
    printVector(nums);
    //  确定边界和关键值
    int key = nums[left];
    cout << "确定的key的值为：" << key << endl;
    int i = left, j = right;
    //体现思想的主体代码
    while (i < j) {
        while (nums[j] >= key && i < j) {
            j--;
        }
        if (i < j) {
            nums[i] = nums[j];
            i++;
        }
        while (nums[i] <= key && i < j) {
            i++;
        }
        if (i < j) {
            nums[j] = nums[i];
            j--;
        }
    }
    nums[i] = key;
    cout << "排序后i的值：" << i << endl;
    cout << "边界索引分别是left=" << left << "right=" << right << endl;
    cout << "排序后的数组：" << endl;
    printVector(nums);
    cout << endl;
    
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

int main() {
    // 测试用例
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int right = nums.size();
    quickSort(nums, 0, right - 1);
    cout << "快速排序后的数组：" << endl;
    printVector(nums);
    return 0;
}

        这个的输出如下：简单解释一下，输出的第一块是main函数引用quickSort之后，进行第一次排序，此时做右端点是main种传入的参数0, right-1也就是0，5，key值这里设置的是左端点的值，即 key=3，按照代码进行排序后 i 的值是2，也就是最后key值放入的位置，排序后的数组是：1 2 3 5 6 4，此时数组以key值为中点分成了左右两个部分，左边的数都比key值小，右边的值都比key值大。以key为分界点将左右两个部分再分别进行快速排序，也就是代码：

quickSort(nums, left, i - 1);
quickSort(nums, i + 1, right);

 输出的第二块是对上面输出数组的左边部分【0 1】进行排序

输出的第三块是对上面输出数组的右边部分【5 6 4】进行排序

进行快速排序前的边界分别是left=0right=5
进行快速排序前的数组：
3 2 1 5 6 4 
确定的key的值为：3
排序后i的值：2
边界索引分别是left=0right=5
排序后的数组：
1 2 3 5 6 4 

进行快速排序前的边界分别是left=0right=1
进行快速排序前的数组：
1 2 3 5 6 4 
确定的key的值为：1
排序后i的值：0
边界索引分别是left=0right=1
排序后的数组：
1 2 3 5 6 4 

进行快速排序前的边界分别是left=3right=5
进行快速排序前的数组：
1 2 3 5 6 4 
确定的key的值为：5
排序后i的值：4
边界索引分别是left=3right=5
排序后的数组：
1 2 3 4 5 6 

快速排序后的数组：
1 2 3 4 5 6 

插入排序（升序）：

基本思想：插入排序是一种简单直观的排序算法，其基本思想是构建一个有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。对于少量或者部分有序的数据，插入排序是一种快速有效的排序方法。 下面用一组数据来说明具体排序过程，应该还是比较好理解的。

当使用插入排序对数组 nums = {5, 3, 8, 1, 2, 7} 进行排序时，
默认第一个数字是排好序的，后面的数字是无序的，将后面的数字根据大小插入对应的位置。
每一次操作的过程如下：

初始数组： nums = {5, 3, 8, 1, 2, 7}

第一轮迭代：
当前数组状态： {5, 3, 8, 1, 2, 7}
将 3 插入到正确的位置：
3 比 5 小，交换位置： {3, 5, 8, 1, 2, 7}
第一轮迭代后前两个数据就是排好序的了

第二轮迭代：
当前数组状态： {3, 5, 8, 1, 2, 7}
将 8 插入到正确的位置：
8 比 5 大，保持位置不变： {3, 5, 8, 1, 2, 7}
第二轮迭代后前三个数据就是排好序的了【以此类推】

第三轮迭代：
当前数组状态： {3, 5, 8, 1, 2, 7}
将 1 插入到正确的位置：
1 比 8 小，交换位置： {3, 5, 1, 8, 2, 7}
1 比 5 小，交换位置： {3, 1, 5, 8, 2, 7}
1 比 3 小，交换位置： {1, 3, 5, 8, 2, 7}

第四轮迭代：
当前数组状态： {1, 3, 5, 8, 2, 7}
将 2 插入到正确的位置：
2 比 8 小，交换位置： {1, 3, 5, 2, 8, 7}
2 比 5 小，交换位置： {1, 3, 2, 5, 8, 7}
2 比 3 小，交换位置： {1, 2, 3, 5, 8, 7}

第五轮迭代：
当前数组状态： {1, 2, 3, 5, 8, 7}
将 7 插入到正确的位置：
7 比 8 小，交换位置： {1, 2, 3, 5, 7, 8}
排序完成：最终数组为 {1, 2, 3, 5, 7, 8}

  代码如下：

#include <iostream>
#include <vector>
using namespace std;
// 打印数组
void printVector(const vector<int>& vec) {
    for (const auto& elem : vec) {
        cout << elem << " ";
    }
    cout << endl;
}
// 插入排序算法
void insertionSort(vector<int>& nums) {
    int len = nums.size();
    for (int i = 1; i < len; i++) {
        int key = nums[i];
        int j ;
		for(j = i-1 ; j>=0 ; j--){
			if(nums[j] >key){
				nums[j+1] = nums[j] ;	
			}else{
				//break一定要有，不然j会在for循环中一直减到0
				break ;
			}
		}
        nums[j + 1] = key;
    }
}
int main() {
    vector<int> nums = {5, 3, 8, 1, 2, 7};
    cout << "排序前的数组：";
    printVector(nums);
    insertionSort(nums);
    cout << "插入排序后的数组：";
    printVector(nums);
    return 0;
}

        还有一种用while语句写的，个人比较习惯用for语句，但是while语句可能会更简单一点，不会踩到break的坑。

// 插入排序算法
void insertionSort(vector<int>& nums) {
    int len = nums.size();
    for (int i = 1; i < len; i++) {
		cout<<"第"<<i<<"次插入："<<endl ;
        int key = nums[i];
        int j = i - 1;
        // 将比 key 大的元素向右移动
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
        cout << "key的值：" << key << endl;
        printVector(nums);
		cout<<endl ;
    }
}

希尔排序（升序）：

基本思想：希尔排序是插入排序的一种改进版本，也被称为“缩小增量排序”。它通过将数据集分成多个较小的子集进行排序，然后逐渐减少子集的大小，最后使用插入排序完成整个数据集的排序。这样做的目的是减少数据的交换次数和移动次数，从而提高效率。

实现步骤：

• 选择增量序列：选择一个增量序列，通常从较大的增量开始逐步缩小到1。常见的增量序列是希尔增量（初始增量一般为数组长度的一半，然后逐步减半）。
• 分组排序：根据当前增量将数组分成多个子数组，对每个子数组进行插入排序。
• 逐步缩小增量：减小增量，重复步骤2，直到增量为1。此时，对整个数组进行一次插入排序。

PS:插入排序用了两个for循环，希尔排序用了3个，因为其在插入排序的基础上增加了一个“增量gap循环”

复杂度分析：

• 时间复杂度：希尔排序的时间复杂度取决于所选择的增量序列。平均情况下，希尔排序的时间复杂度在 O(nlog⁡2n) 到 O(n^{3/2}) 之间。对于希尔增量序列，时间复杂度为 O(n^2) 。一些优化的增量序列可以将时间复杂度降低到 O(nlog⁡n) 。
• 空间复杂度：希尔排序是一个原地排序算法，因此它的空间复杂度为 O(1) 。
• 稳定性：希尔排序不是一个稳定的排序算法，因为元素的比较和交换不局限于相邻元素。

实现代码：

#include <iostream>
#include <vector>
using namespace std;

// 打印数组
void printVector(const vector<int>& vec) {
    for (const auto& elem : vec) {
        cout << elem << " ";
    }
    cout << endl;
}

// 希尔排序算法
void shellSort(vector<int>& nums) {
    int len = nums.size();
    for (int gap = len / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < len; i++) {
            int key = nums[i];
            int j;
            for (j = i; j >= gap && nums[j - gap] > key; j = j - gap) {
                nums[j] = nums[j - gap];
            }
            nums[j] = key;
        }
    }
}

int main() {
    vector<int> nums = {5, 3, 8, 1, 2, 7, 9, 9, 6, 4};
    cout << "排序前的数组：";
    printVector(nums);
    shellSort(nums);
    cout << "希尔排序后的数组：";
    printVector(nums);
    return 0;
}

为了详细了解希尔排序的执行过程，我们将用增量序列 {3, 1} 对数组 {5, 3, 8, 1, 2, 7} 进行排序。

初始数组：5, 3, 8, 1, 2, 7
第一步：使用增量 3 进行排序
    分组情况：
      第1组: {5, 1}
      第2组: {3, 2}
      第3组: {8, 7}
分别对每一组进行插入排序。
      组1: {5, 1}  插入排序后：{5, 1} ，那么原数组：1, 3, 8, 5, 2, 7
      组2: {3, 2}  插入排序后：{2, 3} ，那么原数组：1, 2, 8, 5, 3, 7
      组3同理，原数组就变成了：1, 2, 7, 5, 3, 8

第二步：使用增量 1 进行排序(就是插入排序)
      数组：1, 2, 7, 5, 3, 8，对这个数组进行插入排序后就得到了正确的结果：1, 2, 3, 5, 7, 8

选择排序（升序）：

基本思想：选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从未排序的部分中选出最小（或最大）的元素，并将其放到已排序部分的末尾，直到所有元素都排序完成。

具体步骤如下：

1. 从待排序序列中找到最小（最大）元素，将其放到序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（最大）元素，然后放到已排序序列的末尾。
3. 重复上述步骤，直到所有元素都排序完成。

时间复杂度：

选择排序的时间复杂度为 O(n2)，其中 n 是数组的长度。具体来说：

• 最佳情况时间复杂度：O(n2)
• 最坏情况时间复杂度：O(n2)
• 平均情况时间复杂度：O(n2)

空间复杂度为 O(1)，因为选择排序是原地排序，不需要额外的存储空间。

代码如下：好像没什么好讲的，遍历找到最小值，然后交换就可以了。值得注意的是，需要交换索引，也就是nums[i] 和 nums[minindex]，而不是交换某两个数字。

#include <iostream>
#include <vector>
using namespace std;
// 打印数组
void printVector(const vector<int>& vec) {
    for (const auto& elem : vec) {
        cout << elem << " ";
    }
    cout << endl;
}
// 选择排序算法
void selectionSort(vector<int>& nums) {
    int len = nums.size();
    int i = 0 ;
	for(i = 0 ; i<len-1 ;i++){
		int minindex = i ;
		for(int j = i+1 ;j<len ;j++){
			if(nums[j] < nums[minindex]){
                //这里一定是要找到最小值的在的《位置》，也就是数组对应的索引
				minindex = j ;
			}
		}
		swap(nums[i], nums[minindex]);
		printVector(nums);
	}
}
int main() {
    vector<int> nums = {5, 3, 8, 1, 2, 7};
    cout << "排序前的数组：";
    printVector(nums);
    selectionSort(nums);
    cout << "选择排序后的数组：";
    printVector(nums);
    return 0;
}

归并排序（升序）：

基本思想：归并排序是一种基于分治思想的排序算法。其基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后将已排序的子数组合并成一个有序的数组。

时间复杂度：

        归并排序的时间复杂度为 O(nlog⁡n)，其中 n 是数组的长度。其空间复杂度为 O(n)，因为需要额外的数组来存放合并过程中的中间结果

代码实现：

写在最后：

发现一个好东西：十大经典排序算法（动图演示，收藏好文）

         看懂每一个排序算法的思路再看动图会比较好，更加直观并且帮助记忆。没懂排序思想的话看动图感觉还是云里雾里的。