一.排序算法是什么
排序算法（Sorting Algorithms）是一种数据结构操作，它的目的是将一串元素按照特定的顺序规则组织起来。常见的排序算法有升序（从小到大）和降序（从大到小）排列，如冒泡排序、希尔排序、插入排序、选择排序、快速排序、归并排序等。排序的主要目的是为了方便查找、分析数据，提高数据处理效率。在计算机科学中，数组、列表或数据库查询结果等都可以通过排序来进行整理。每种排序算法的时间复杂度和空间复杂度都有所不同，选择哪种算法取决于实际应用场景的需求和性能要求。
二.六大排序算法
1. 插入排序
步骤：
1.从第一个元素开始，该元素可以认为已经被排序
2.取下一个元素s，从已排序的元素序列从后往前扫描
3.如果该元素大于s，则将该元素移到下一位
4.重复步骤3，直到找到已排序元素中小于等于s的元素
5.s插入到该元素的后面，如果已排序所有元素都大于s，则将s插入到下标为0的位置
6.重复步骤2~5
时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
演示如下：
参考代码：
void bubble_sort(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(arr[j], arr[j + 1]);
swapped = true;
}
}
// 如果这一轮没有发生任何交换，则说明已经有序
if (!swapped)
break;
}
}2.希尔排序
步骤
- 选择增量序列：选择一系列逐渐减小的增量（gap），通常是从数组长度的一半开始，每次减半直到1。
- 分组排序：对于每个增量
gap，将数组分成若干个子序列，每个子序列中的元素相隔 gap个位置。对每个子序列进行插入排序。 - 重复：重复上述步骤，直到增量为1，此时整个数组被看作一个子序列进行插入排序。
时间复杂度平均：O(N^1.3)
空间复杂度：O(1)
演示如下：
参考代码：
void shellSort(std::vector<int>& arr) {
int n = arr.size();
// 选择增量序列
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个子序列进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// 插入排序
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}3.选择排序
步骤：
- 初始化：将数组分为已排序部分和未排序部分。
- 查找最小元素：从未排序部分找到最小的元素。
- 交换元素：将找到的最小元素与未排序部分的第一个元素交换。
- 缩小未排序部分：将未排序部分的范围缩小一个元素。
- 重复步骤2-4，直到未排序部分为空
时间复杂度：最坏情况：O(N^2)
最好情况：O(N^2)
空间复杂度：O(1)
演示如下：
代码：
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
// 遍历未排序部分
for (int i = 0; i < n - 1; i++) {
// 找到未排序部分的最小元素的索引
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将找到的最小元素与未排序部分的第一个元素交换
swap(arr[i], arr[minIndex]);
}
}
4.冒泡排序
步骤：
- 比较相邻元素：如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。 这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 重复步骤1~3，直到排序完成。
时间复杂度：最坏情况：O(N^2)
最好情况：O(N)
空间复杂度：O(1)
演示如下：
参考代码：
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
bool swapped;
// 遍历所有数组元素
for (int i = 0; i < n - 1; i++) {
swapped = false;
// 最后 i 个元素已经到位
for (int j = 0; j < n - i - 1; j++) {
// 遍历 0 到 n-i-1
// 交换如果发现元素比下一个元素大
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// 如果没有两个元素交换，则数组已经排序完成
if (!swapped)
break;
}
}
5.堆排序
步骤：
- 构建初始堆：将无序数组构建成一个最大堆或最小堆。
- 移除堆顶元素：将堆顶元素（最大或最小值）与堆的最后一个元素交换，然后减少堆的大小，重新调整堆使其满足堆属性。
- 重复步骤2：直到堆的大小为1。
时间复杂度：( O(n \log n) )（所有情况下）
参考代码：
// 调整最大堆
void maxHeapify(std::vector<int>& arr, int heapSize, int rootIndex) {
int largest = rootIndex; // 初始化最大为根
int leftChild = (2 * rootIndex) + 1; // 左子节点
int rightChild = (2 * rootIndex) + 2; // 右子节点
// 如果左子节点大于根
if (leftChild < heapSize && arr[leftChild] > arr[largest])
largest = leftChild;
// 如果右子节点大于目前最大
if (rightChild < heapSize && arr[rightChild] > arr[largest])
largest = rightChild;
// 如果最大不是根
if (largest != rootIndex) {
swap(arr[rootIndex], arr[largest]);
// 递归地调整受影响的子树
maxHeapify(arr, heapSize, largest);
}
}
// 堆排序
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(arr, n, i);
}
// 一个个从堆顶取出元素
for (int i = n - 1; i > 0; i--) {
// 移动当前根到数组末尾
swap(arr[0], arr[i]);
// 调整剩余元素构成的最大堆
maxHeapify(arr, i, 0);
}
}6.快速排序
步骤：
- 选择基准元素：从数组中选择一个元素作为“基准”（pivot）。
- 分区操作：重新排列数组，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。
- 递归排序：递归地对左右两个子数组进行快速排序。
演示如下：
时间复杂度：
- 最好情况：( O(n \log n) )
- 平均情况：( O(n \log n) )
- 最坏情况：( O(n^2)
参考代码：
// 分区操作
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 指向小于基准的最后一个元素
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
// 快速排序
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
// pi 是分区后的基准位置
int pi = partition(arr, low, high);
// 递归地排序基准左侧和右侧的子数组
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}