#include <iostream>
#include <vector>
#include <algorithm> // 用于std::swap
// 冒泡排序函数
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 使用std::swap交换两个元素
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// 如果在这一轮排序中没有发生交换，说明数组已经有序，可以提前结束
if (!swapped) {
break;
}
}
}
// 打印数组的函数
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
// 主函数
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "Original array:\n";
printArray(arr);
bubbleSort(arr);
std::cout << "Sorted array:\n";
printArray(arr);
return 0;
}
快速排序 Quick Sort
定义：由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一个称为“基准”（pivot）的元素将数组分成两个子数组，使得左边子数组的所有元素都比基准小，右边子数组的所有元素都比基准大，然后递归地对这两个子数组进行快速排序。
#include <iostream>
#include <vector>
// 合并两个子序列的函数
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 左子序列的长度
int n2 = right - mid; // 右子序列的长度
// 创建临时数组
std::vector<int> L(n1), R(n2);
// 拷贝数据到临时数组 L[] 和 R[]
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并临时数组回到 arr[left..right]
int i = 0; // 初始索引第一个子数组
int j = 0; // 初始索引第二个子数组
int k = left; // 初始索引合并的子数组
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 拷贝 L[] 的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 拷贝 R[] 的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l 是数组的左边界，r 是右边界
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
// 同 [left, mid] 和 [mid+1, right] 两个子序列
int mid = left + (right - left) / 2;
// 分别对两个子序列进行归并排序
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并两个子序列
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
int arr_size = arr.size();
mergeSort(arr, 0, arr_size - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < arr_size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
堆排序 Heap Sort
定义：是一种基于比较的排序算法，使用二叉堆数据结构。堆排序分为两个阶段：建立堆（Build Max Heap）和排序（Heapsort）。堆是一个满足以下性质的完全二叉树：对于最大的堆（大顶堆），父节点的键值总是大于或等于其子节点的键值；对于最小的堆（小顶堆），父节点的键值总是小于或等于其子节点的键值。
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap()
// 调整堆，保持最大堆性质
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i; // 初始化最大元素为根
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根大，则更新最大元素
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点比最大元素大，则更新最大元素
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大元素不是根，交换它们，并继续调整堆
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// 堆排序
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 一个个从堆顶取出元素
for (int i = n - 1; i >= 0; i--) {
// 将当前最大元素（堆顶）与末尾元素交换
std::swap(arr[0], arr[i]);
// 调整堆
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
heapSort(arr);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}