1.插入排序
约 953 字大约 3 分钟
2025-06-21
前要：以下代码我只展示最为核心的排序代码实现部分...
1.插入排序
1.1.直接插入排序
- 排序思路：在
[0, end]有序的前提下，保证插入tmp后依旧有序。 - 排序效率：在最坏情况下（对于下面代码来说逆序情况就是最坏情况），由于需要移动数据的次数为 0+1+2+...+n，因此是典型的 O(n2)。
//InsertSort()
#include <stdio.h>
#include <stdlib.h>
void _Show(int* arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void InsertSort(int* arr, int size)
{
int end = -1;
for (int i = 0; i < size; i++)
{
int tmp = arr[i];
while (end != -1 && tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
arr[end + 1] = tmp;
end = i;
//显示排序
_Show(arr, size);
}
}1.2.希尔排序
2.选择排序
2.1.直接选择排序
- 排序思路：从一个待排序列中选出
min/max，然后将min/max和待排序列中的begin/end交换，不断重复，最终得到升序/降序序列。 - 排序效率：由于每次都需要选出最值，从最坏情况考虑，每次都需要遍历整个待排序数组才能得到最值，也就是 n+...+3+2+1 次，因此也是经典的 O(n2)。
//Selectsort()
#include <stdio.h>
#include <stdlib.h>
void _Show(int* arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void _Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void Selectsort(int* arr, int size)
{
for (int begin = 0; begin < size; begin++)
{
//选择最小
int min = begin;
for (int i = begin; i < size; i++)
{
if (arr[min] > arr[i])
min = i;
}
//交换数据
_Swap(&arr[begin], &arr[min]);
//显示排序
_Show(arr, size);
}
}这个实现比较简单，但是我们可以所谓优化一下，每次从待排序数组中选择最小值和最大值，分别把最小值和最大值，扔到待排序序列的开头和结尾即可（就是需要注意处理一些特殊情况）。
//Selectsort()
#include <stdio.h>
#include <stdlib.h>
void _Show(int* arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void _Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void Selectsort(int* arr, int size)
{
int begin_i = 0, end_i = size - 1;
while (begin_i < end_i)
{
//选择最值
int max_i = begin_i, min_i = end_i;
for (int i = begin_i; i < end_i + 1; i++)
{
if (arr[i] > arr[max_i]) //寻找最大值
max_i = i;
if (arr[i] < arr[min_i]) //寻找最小值
min_i = i;
}
//交换数据
_Swap(&arr[min_i], &arr[begin_i]);
if (max_i == begin_i) //处理特殊情况
{
max_i = min_i;
}
_Swap(&arr[max_i], &arr[end_i]);
begin_i++;
end_i--;
//显示排序
_Show(arr, size);
}
}2.2.堆排序
3.交换排序
3.1.直接交换排序
排序思路：直接交换排序也被称为冒泡排序，其思想类似冒出的水泡。
(1)先让待排序序列
[0, n-1]从头开始的每对相邻两个元素进行比较，通过交换，最值放在右端(2)此时序列中最后一个元素
arr[n-1]就一定是最值，且已经到达它最终的位置(3)然后对子序列
[0, n-2]重复步骤(1)，最终达到有序序列排序效率：典型的 O(n2)，其做法非常暴力，因此比较低效。
//BubbleSort()
#include <stdio.h>
#include <stdlib.h>
void _Show(int* arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void _Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void BubbleSort(int* arr, int size)
{
for (int j = 0; j < size - 1; j++) //冒泡次数
{
for (int i = 0; i < size - j - 1; i++) //交换次数
{
if (arr[i] > arr[i + 1])
_Swap(&arr[i], &arr[i + 1]);
}
_Show(arr, size);
}
}3.2.快速排序
4.归并排序
4.1.递归归并
4.2.非递归归并
5.排序补充
其他大同小异的实现方法：
//InsertSort()
#include <stdio.h>
#include <stdlib.h>
void InsertSort(int* arr, int size)
{
int end = -1;
for (int i = 0; i < size; i++)
{
int tmp = arr[i];
while (end != -1 && tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
arr[end + 1] = tmp;
end = i;
}
}更新日志
2025/11/20 09:51
查看所有更新日志