选择排序
概述
选择排序可以看作是一种打擂台法，利用一轮打擂台，找出最大的元素，让其与最后一个元素交换，接着再那么这最大的元素的位置就排好了，用相同的方法把下面的元素一个个排完。
选择排序和冒泡排序很像，但冒泡排序在把最大的元素推到最后的过程中两个相邻的元素之间会交换，也就是说最大的元素一般不是直接交换到最后的，而选择排序是。
代码
#include <iostream> using namespace std; void selectionSort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(arr[min_idx], arr[i]); } } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr)/sizeof(arr[0]); selectionSort(arr, n); cout << "Sorted array: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }
冒泡排序
概述
重复地遍历要排序的数列，一次比较两个元素，若顺序错误则交换两个元素，直到所有元素顺序正确。
代码
#include<iostream>using namespace std;void bubbleSort(int arr[],int n){for(int i=0;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(arr[j]>arr[j+1])swap(arr[j],arr[j+1])} } } int main(){ int arr[15]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}int n=15;bubbleSort(arr,n);}
ps：冒泡排序与打擂台法的关联
冒泡排序与打擂台法有异曲同工之处：
都是通过“比较和交换”来实现对数据的排序或筛选。
在冒泡排序中，每一轮遍历都会将当前未排序序列中最大（或最小）的元素“冒泡”到序列的最后位置。这个过程就像是在一个擂台上进行打擂，每轮遍历都会选择当前最强大的挑战者，并将其“打擂”到序列的最后位置。
类似地，在打擂台法中，也是通过比较和筛选来选出最优秀的选手并将其“打擂”到最终的胜者位置。
因此，我们可以将冒泡排序看作是一种打擂台法的应用，通过遍历待排序序列中的元素，逐步筛选并确定最终排序结果。
插入排序
概念
现在列出一组数字：978251364；从一个数9开始，把9拿出来，接着拿出出第二个元素7，发现比9小，放9前面，然后拿出第三个数8，发现比9小，比7大，于是放9和7中间......依次类推，直到所有数都被拿完。
代码
#include <iostream> using namespace std; void insertionSort(int arr[], int n) { //将第一个元素看作已排好的数组，从第二个元素开始遍历for (int i = 1; i < n; i++) { int key = arr[i]; // // 初始已排序元素的最后一个位置当前未排序元素的值int j = i - 1; while (j >= 0 && arr[j] > key) { // 如果已排序元素比当前元素大，则将已排序元素往后移动arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // 将当前元素插入到正确位置 } } int main() { int arr[] = { 10, 7, 8, 9, 1, 5 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); cout << "Sorted array: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; }
ps：现实生活中的例子（可以不看）
高中时买女神物语卡（二次元的东西），买了一包卡时，其顺序是乱的，这时就需要对这些卡排序（好看的放上面），从里面抽出一张放桌面上，接着继续抽如果下一张好看就放上面，否则放下面，接着再抽出一张卡，把卡插入桌面上卡牌的合适位置，抽完所有卡，桌面上就是一副排好的卡牌了
快速排序
概述
通过递归地将序列分成较小的子序列，然后对这些子序列进行快速排序，最终将子序列合并成一个有序的序列。在实现中，选择一个基准元素，将序列中小于基准元素的数放在左侧，大于基准元素的数放在右侧，然后递归地对左右子序列进行排序，最终得到一个有序序列。
快速排序的时间复杂度为O(nlogn)，具体实现的效率与基准元素选择、分割策略等因素有关。在实际应用中，快速排序是一种非常常用和优秀的排序算法，应用广泛。
代码
#include <iostream> #include <vector> using namespace std; int partition(vector<int>& nums, int left, int right) { int pivot = nums[left]; int i = left + 1, j = right; while (i <= j) { if (nums[i] < pivot) { i++; } else if (nums[j] >= pivot) { j--; } else { swap(nums[i++], nums[j--]); } } swap(nums[left], nums[j]); return j; } void quickSort(vector<int>& nums, int left, int right) { if (left < right) { int pivotIdx = partition(nums, left, right); quickSort(nums, left, pivotIdx - 1); quickSort(nums, pivotIdx + 1, right); } } int main() { vector<int> nums = {5, 1, 9, 3, 7, 6, 8, 2, 4}; quickSort(nums, 0, nums.size() - 1); for (int num : nums) { cout << num << " "; } cout << endl; return 0; }
ps（快速排序的演示动画）：
【快速排序算法】/video/BV1at411T75o?vd_source=f749a3cadc8584d9829595a2c17b103f
希尔排序
概述
希尔排序是插入排序的一种改进，也称为缩小增量排序。它会将数组分成若干个子序列，对每个子序列进行插入排序，然后再对整个数组进行插入排序。相比于直接使用插入排序，希尔排序可以更快地将大的元素移动到正确位置，从而减少比较和交换的次数。
基本思路：先将整个待排序序列分成若干个小的子序列（由相隔某个“增量”的元素组成），然后对这些子序列分别进行插入排序。随着增量逐渐减少，每个子序列包含的元素越来越多，当增量减至 1 时，整个序列被分成了一个子序列，此时对整个序列进行插入排序，排序完成后即可得到排序后的序列。
void radixSort(int arr[], int n) {int maxVal = arr[0];for (int i = 1; i < n; i++) maxVal = max(maxVal, arr[i]);for (int exp = 1; maxVal / exp > 0; exp *= 10) {int count[10] = {0};for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;for (int i = 1; i < 10; i++) count[i] += count[i - 1];int output[n];for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < n; i++) arr[i] = output[i];}}
ps（希尔排序演示动画）
【[算法]六分钟彻底弄懂希尔排序，简单易懂】/video/BV1rE411g7rW?vd_source=f749a3cadc8584d9829595a2c17b103f
归并排序
概述
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，递归地对每个部分进行排序，并将两个已排好序的部分合并成一个有序数组。
对于归并排序，我们可以用递归的思想来实现。具体步骤如下：
1.将待排序数组从中间位置分成两个子数组；
2.递归地对两个子数组进行排序；
3.合并两个已排好序的子数组。
代码
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1, n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++) L[i] = arr[l + i];for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];}void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}}
基数排序
概述
基数排序（Radix Sort）是一种非比较排序算法，它通过将排序对象分成多个关键字来实现排序。所谓关键字，就是指待排序元素中，用于排序的各个位数。
基数排序的基本思想是从最低位开始，按照关键字进行排序。这样排序后，每个元素位于正确的位置上。然后再考虑下一位，按照关键字再进行排序。重复这个过程，直到所有位都考虑过了，最终排序完成。
具体操作步骤如下：
1.找出最大数，并确定最大数的位数；
2.从最低位开始，按照个位数排序，将所有元素分配到 0~9 的桶中，然后依次收集桶中元素；
3.按照十位数排序，将所有元素分配到 0~9 的桶中，然后依次收集桶中元素；
4.以此类推，直到最高位排序完成。
代码
void radixSort(int arr[], int n) {int maxVal = arr[0];for (int i = 1; i < n; i++) maxVal = max(maxVal, arr[i]);for (int exp = 1; maxVal / exp > 0; exp *= 10) {int count[10] = {0};for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;for (int i = 1; i < 10; i++) count[i] += count[i - 1];int output[n];for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < n; i++) arr[i] = output[i];}}
ps（基数排序的动画演示）
【【排序算法】基数排序】/video/BV1zF411G7AU?vd_source=f749a3cadc8584d9829595a2c17b103f
