intSelectSort(int *arr, int len) {
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return0;
}
intShellSort(int *arr, int len) {
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < len; i++) {
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
return0;
}
4.4 复杂度
（1）时间复杂度：
依赖于步长序列的选择。
最好情况（基本有序）：接近 O(n log n)；
最坏情况：接近 O(n²)；
实际平均性能远优于插入排序，常见实现为 O(n^1.3 ~ n^1.5)。
（2）空间复杂度：
只需要常数个辅助变量 → O(1)，属于原地排序。
（3）稳定性：
不稳定：因为分组插入时，可能打乱相等元素的顺序
（4）特点：
适合：中等规模的数据（比如几万级别以内），比插入排序快很多；
缺点：复杂度分析困难，且最坏情况仍然是 O(n²)。
希尔排序能显著优化直接插入排序。
5、快速排序
5.1 基本思想
分治法：选一个'基准元素'（pivot），将序列划分为两部分：
小于 pivot 的放左边；
大于 pivot 的放右边；
递归排序左右两部分。
5.2 工作原理
选择基准：从序列中选择一个元素作为基准（pivot）
分区操作：重新排列序列，所有比基准小的放在左边，比基准大的放在右边
递归排序：递归地对左右两个子序列进行快速排序
具体步骤：
选定一个基准值（pivot），通常取数组第一个元素。
设置左右指针：left 指向数组开头，right 指向结尾。
从右往左找第一个小于 pivot 的元素，如果找到放入 left 指向的位置；在从左往右找第一个大于 pivot 的元素，如果找到放在 right 指向的位置。
重复上述步骤 3，直到左右指针相遇。
把 pivot 放到左右指针相遇的位置。
递归对 pivot 左边和右边的子数组分别进行快速排序。
5.3 代码实现
intQuickSort(int *arr, int left, int right) {
if (left >= right) return0;
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
// 覆盖法while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
QuickSort(arr, left, i - 1);
QuickSort(arr, i + 1, right);
return0;
}
5.4 复杂度
（1）时间复杂度：
最好：每次平衡划分 → O(n log n)；
最坏：划分极不平衡（例如有序数组 + 选首元素）→ O(n²)；
平均：O(n log n)。
（2）空间复杂度：
递归栈空间：O(log n)（最好），最坏 O(n)
（3）稳定性：
不稳定：划分过程中可能交换相等元素的顺序。
（4）特点：
平均性能好，是实际应用中最常用的排序算法之一；
适用于大规模数据。
在 C 语言中，可以使用 qsort 函数来实现排序，内部就是使用的快速排序的思想。
C 语言：使用 qsort
#include<stdio.h>#include<stdlib.h>// 比较函数，升序intcmp(constvoid *a, constvoid *b) {
return (*(int*)a - *(int*)b);
}
intmain() {
int arr[] = {5, 2, 9, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
// 排序
qsort(arr, n, sizeof(int), cmp);
// 输出结果for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return0;
}
// 调整堆（大根堆）intHeapify(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) {
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
Heapify(arr, n, largest);
}
return0;
}
intHeapSort(int *arr, int n) {
// 1. 建堆：从最后一个非叶子节点开始，向上调整for (int i = n / 2 - 1; i >= 0; i++)
Heapify(arr, n, i);
// 2. 取出堆顶元素（最大值），放到数组末尾，然后调整剩余堆for (int i = n - 1; i > 0; i--) {
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
Heapify(arr, i, 0); // 只调整前 i 个元素
}
return0;
}
