快速排序
快速排序（Quicksort）是一种常用的排序算法，它基于分治的思想。
时间复杂度：O（nlogn）
空间复杂度：O（logn）
快速排序的基本思想如下：
- 选择一个元素作为基准（pivot）。
- 将序列中比基准小的元素移到基准的左边，比基准大的元素移到基准的右边。这个过程称为划分（partition）。
- 对划分后的两个子序列（基准左边和右边的序列）递归地应用上述步骤，直到子序列的长度为1或0，也即序列已经有序。
- 合并所有子序列的结果，得到最终的排序序列。
代码参考这篇文章：
void Quick_Sort(int *arr, int begin, int end) {if (begin > end) { //当待排序的子数组长度为0或负数时，终止递归 return;}int tmp = arr[begin]; //取数组的第一个元素arr[begin]作为基准元素int i = begin;int j = end;while(i != j) { //指针i和j分别从数组的两端向中间移动，寻找可以交换的元素while(arr[j] >= tmp && j > i)j--;while(arr[i] <= tmp && j > i)i++;if(j > i) { int t = arr[i];arr[i] = arr[j];arr[j] = t;}}arr[begin] = arr[i];arr[i] = tmp; //将基准元素放在最终位置Quick_Sort(arr, begin, i-1);Quick_Sort(arr, i+1, end);
}
冒泡排序
冒泡排序是一种简单但效率较低的排序算法。它通过多次交换相邻元素的位置来实现排序。下面是冒泡排序的具体过程：1.从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
2.继续比较下一对相邻元素，重复上述比较和交换操作，直到遍历到倒数第二个元素。
3.重复执行步骤 1 和步骤 2，直到所有元素都被比较并排序。
这样，每一轮遍历都会将未排序部分的最大（或最小）元素移动到已排序部分的末尾。因此，经过多轮遍历后，整个数组就会按照升序（或降序）排列。
写代码时有个细节要注意： for (int i = 0; i < size - 1; i++) {
#include <iostream>
using namespace std;void bubbleSort(int arr[], int size) {for (int i = 0; i < size - 1; i++) { //size-1 而非size 因为要arr[j+1]for (int j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j + 1] 的值int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {5, 2, 8, 12, 1};int size = sizeof(arr) / sizeof(arr[0]); //sizeof(arr) 表示整个数组 arr 在内存中占用的总字节数。sizeof(arr[0]) 表示数组 arr 中单个元素 arr[0] 的字节大小。cout << "排序前的数组：";for (int i = 0; i < size; i++) {cout << arr[i] << " ";}bubbleSort(arr, size);cout << "\n排序后的数组：";for (int i = 0; i < size; i++) {cout << arr[i] << " ";}return 0;
}
