排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

1. 插入排序

基本思想

插入排序的基本思想是将一个元素插入到已经排好序的有序表中，从而形成一个新的、记录数增加1的有序表。具体步骤如下：

将原数组分为有序数组和无序数组两部分。将数组的第一个元素视为有序数组，其余部分视为无序数组。
从第二个元素开始，遍历无序数组，将当前元素与有序数组中的元素进行比较（有序数组从后往前依次比较）。如果当前元素小于有序数组中的元素，则将有序数组中的元素向后移动一位，继续比较直到找到大于当前元素的位置。
如果当前元素大于有序数组中的最后一个元素，则直接将当前元素添加到有序数组的末尾。

代码实现

#include <stdio.h>

void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i]; // 当前要排序的元素
j = i - 1;

// 将arr[i]与已排序好的序列arr[0...i-1]中的元素进行比较，找到合适的位置插入
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 将大于key的元素向后移动
j = j - 1;
}
arr[j + 1] = key; // 将key插入到合适的位置
}
}

int main() {
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("排序后的数组: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}

示例输出

对于输入数组{5, 2, 4, 6, 1, 3}，排序后的结果为1 2 3 4 5 6。

时间复杂度

插入排序的时间复杂度为O(n^2)，其中n是数组中的元素数量。在最坏情况下（即输入数组是逆序的），需要进行n(n-1)/2次比较和交换。在最好情况下（即输入数组已经有序），只需要进行n-1次比较，不需要交换。

2. 希尔排序

基本思想

分组：选择一个增量序列（例如n/2, n/4, n/8等），将待排序的数组分成若干个子序列，每个子序列中的元素间隔为当前的增量。
插入排序：对每个子序列分别进行直接插入排序。
缩小增量：逐步减小增量，重复上述分组和排序过程，直到增量减小到1。
最终排序：当增量为1时，整个数组被分成一个子序列，此时进行最后一次插入排序，完成整个排序过程。

代码实现

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
int gap, i, j, temp;
// 从n/2开始，每次减半，直到增量为1
for (gap = n / 2; gap > 0; gap /= 2) {
// 对每个子数组进行插入排序
for (i = gap; i < n; i++) {
temp = arr[i];
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}

// 打印数组函数
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {9, 5, 2, 7, 8, 1, 3, 5, 4, 8, 7, 6, 2, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组: \n");
printArray(arr, n);
shellSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}

在外层循环中，j是从i开始递减的，每次减去gap的值，直到arr[j - gap]不再大于temp。这意味着j最终停在了第一个不大于temp的元素的下一个位置。
当j停止递减时，arr[j]实际上是temp应该插入的位置。此时，arr[j - gap]是temp应该替换的元素，而不是之前移动的元素。因此，当我们执行arr[j] = temp;时，我们并没有覆盖之前的交换操作，而是将temp放到了正确的位置。

举例：

假设我们有一个数组arr = {9, 8, 7, 6, 5, 4, 3, 2, 1}，gap为3，我们正在处理索引5（即值5）。
i = 5，temp = arr[5] = 4。
j = 5，j - gap = 2，arr[2] = 7，因为7 > 4，我们执行arr[5] = arr[2] = 7。
j = 2，j - gap = -1（但我们不会执行这个比较，因为j已经小于gap了）。
现在，j停在了2，arr[2]是第一个不大于temp（4）的元素。因此，我们将temp（4）放到 arr[2]的位置，覆盖了之前的7。
最终，数组变为{9, 8, 4, 6, 5, 3, 2, 1, 7}，并且temp（4）被正确地插入到了数组中。

示例输出

排序前的数组: 9 5 2 7 8 1 3 5 4 8 7 6 2 1 5 排序后的数组: 1 1 2 2 3 4 5 5 5 6 7 7 8 8 9

时间复杂度

希尔排序的时间复杂度受增量序列的选择影响较大。在最坏情况下，时间复杂度可能退化为O(n^2)，但在实际应用中，通过合理选择增量序列，时间复杂度可以达到O(nlogn)甚至更优。

3. 选择排序

基本实现步骤

初始化最小索引：从数组的第一个元素开始，假设该元素为当前最小值。
寻找最小值：遍历数组的未排序部分，找到比当前最小值更小的元素，并更新最小值的索引。
交换元素：将找到的最小值与当前未排序部分的第一个元素交换位置。
重复步骤：将已排序部分向右扩展一个元素，重复上述过程，直到所有元素排序完成。

代码实现

#include <stdio.h>

// 交换两个整数的值
void swap(int *xp, int*yp) {
int temp = *xp;
*xp =*yp;
*yp = temp;
}

// 选择排序函数
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;

// 如果找到的最小值不是当前元素，则交换
if(min_idx != i)
swap(&arr[min_idx], &arr[i]);
}
}

// 打印数组
void printArray(int arr[], int size) {
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// 主函数
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前的数组: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}

示例输出

排序前的数组: 64 25 12 22 11 排序后的数组: 11 12 22 25 64

时间复杂度

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)，是一种不稳定的排序算法。

4. 冒泡排序

基本原理

比较与交换：从数组的第一个元素开始，依次比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们的位置。
重复步骤：继续比较和交换相邻元素，直到数组最末尾的元素已排序完毕。
重复排序：重复上述步骤，直到整个数组排序完成。

代码实现

#include <stdio.h>

void bubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;//引入swapped标志位，用于优化算法。

for (i = 0; i < n - 1; i++) {// 外层循环控制比较次数
swapped = 0;
for (j = 0; j < n - i - 1; j++) {// 内层循环控制每次比较元素的数量
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0) {
break; // 如果没有发生交换，说明数组已经有序，提前退出循环
}
}
}

int main() {
int arr[] = {5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

示例输出

排序前数组：5 7 3 2 9 4 1 8 6 0 排序后数组：0 1 2 3 4 5 6 7 8 9

时间复杂度

冒泡排序的时间复杂度取决于输入数据的初始状态：

最好情况：当输入数据已经是正序时，冒泡排序只需要进行一次遍历来确认数据是否已经有序。此时的时间复杂度为O(n)，其中n为数组长度。
最坏情况：当输入数据是逆序时，冒泡排序需要进行n-1轮比较和交换，每轮比较次数逐渐减少。总的比较次数为(n-1)+(n-2)+...+1，即(n^2-n)/2，因此时间复杂度为O(n^2)。
平均情况：在一般情况下，冒泡排序的平均时间复杂度也是O(n^2)。

5. 堆排序

堆排序

6. 快速排序

基本原理

选择基准（Pivot）：
- 从数组中选择一个元素作为基准。基准的选择可以是第一个元素、最后一个元素、随机元素或中间元素。在给定的代码中，基准通常是数组的第一个元素 q[l] 或者中间元素 q[(l+r)/2]。
分区（Partitioning）：
- 重新排列数组，使得所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面。在这个过程中，基准元素最终会被放置在它的正确位置上。
- 使用两个指针 i 和 j，分别从数组的两端向中间移动。i 从左向右寻找第一个大于基准的元素，j 从右向左寻找第一个小于基准的元素。当 i 和 j 相遇时，交换这两个元素的位置，直到 i 不小于 j。
递归排序：
- 对基准左边的子数组和右边的子数组分别进行快速排序。递归地重复这个过程，直到每个子数组只包含一个元素或为空，此时数组就被排序完成了。

代码实现

#include<iostream>
using namespace std;
const int N=1e6+10;
int n;
int q[N];
void quick_sort(int q[],int l,int r){if(l>=r){return ;}int x=q[l],i=l-1,j=r+1;while(i<j){do{i++;}while(q[i]<x);do{j--;}while(q[j]>x);if(i<j){swap(q[i],q[j]);}}quick_sort(q,l,j);quick_sort(q,j+1,r);
}
int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&q[i]);}quick_sort(q,0,n-1);for(int i=0;i<n;i++){printf("%d ",q[i]);}return 0;
}

示例输出

排序前数组：

5
3 1 2 4 5

排序后数组：1 2 3 4 5

时间复杂度

平均时间复杂度：O(nlogn)
最坏情况下的时间复杂度：O(n²)

7. 归并排序

基本原理

分解（Divide）：
- 如果序列的长度为1，则认为该序列已经有序，直接返回。
- 否则，找到序列的中间位置，将序列分成两个子序列。
解决（Conquer）：
- 递归地对两个子序列分别进行归并排序。
合并（Combine）：
- 将两个有序的子序列合并成一个有序的序列。

代码实现

#include<iostream>
using namespace std;
const int N=100010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r){if(l>=r){return ;}int mid=l+r>>1;merge_sort(q,l,mid);merge_sort(q,mid+1,r);int k=0,i=l,j=mid+1;while(i<=mid&&j<=r){if(q[i]<=q[j])tmp[k++]=q[i++];else tmp[k++]=q[j++];}while(i<=mid){tmp[k++]=q[i++];}while(j<=r){tmp[k++]=q[j++];}for(int i=l,j=0;i<=r;i++,j++){ q[i]=tmp[j];}
}
int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&q[i]);}merge_sort(q,0,n-1);for(int i=0;i<n;i++){printf("%d ",q[i]);}return 0;
}