文章目录
一、八大排序算法复杂度对比
二、基于比较的排序算法
1.冒泡排序
2.选择排序
3.插入排序
4.希尔排序
5.直观感受四种算法的时间复杂度
三、基于非比较的排序算法
1.基数排序
2.箱(桶)排序
四、递归比较排序算法
1.快速排序
2.归并排序
a.普通归并
b.归并递归
一、八大排序算法复杂度对比
二、基于比较的排序算法
1.冒泡排序
介绍：冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”
核心：
冒泡排序:
比较 NUM-1轮，每轮NUM-1次，
每轮（相邻两个比较，不符合要求则交换）
找出一个最大的或者一个最小的
//冒泡排序
void bubble_sort(int* a, int len)
{
int t;
for ( int i = 0; i < len-1; i++) //len-1轮
{
for( int j = 0; j < len-1-i ; j++ ) //每轮为无序的元素个数-1次
{
if ( a[j] > a[j+1] ) //不符合规则交换
{
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}
总结：
- 1.冒泡排序是一种非常容易理解的排序
- 2.时间复杂度：O( N2)
- 3.空间复杂度：O(1)
- 4.稳定性：稳定
2.选择排序
介绍：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
核心：
选择排序：
先假设待排数组第一个为最小值
选择NUM-1轮，每轮从待排数组中选最小的，与第一个进行比较，决定放不放到待排数组第一个
循环从待排数组中找到最小的，记录其下标
交换
//选择排序
void select_sort(int* a, int len)
{
int t;
int minIndex;
for (int i = 0; i < len-1; i++) //len-1轮
{
//从待排数组中(i ----- len-1)找到最小的
minIndex = i; //先假设待排数组中的第一个最小
for (int j = i+1; j < len; j++)
{
minIndex = a[j] > a[minIndex] ? minIndex : j;
}
//符合条件和待排数组中的第一个元素(i)交换
if ( a[minIndex] < a[i] )
{
t = a[minIndex];
a[minIndex] = a[i];
a[i] = t;
}
}
}
总结：
- 1.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 2.时间复杂度：O(N2)
- 3.空间复杂度：O(1)
- 4.稳定性：不稳定
3.插入排序
介绍：插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
核心：
插入排序：
设置第一个为有序数组，右边NUM-1个为待插数据
然后NUM-1轮，每轮把一个数据插入到有序数组中
插入方式：
1. 先临时保存待插数据
2. 然后从待插数据前一个开始往前循环（越界循环结束）
比待插数据大则往后覆盖，比待插数据小则循环结束
3. 用待插数据覆盖回来（第二步结束后下标的下一个位置）
插入部分图解
//插入排序
void insert_sort(int* a, int len)
{
int j;
int temp;//保存待插数据
for (int i = 1; i < len; i++) //len-1轮
{
temp = a[i];
//待插数据前一个开始往前循环（越界循环结束）
for ( j = i-1 ; j >= 0 ; j-- )
{
//比待插数据大则往后覆盖
if ( a[j] > temp ) a[j + 1] = a[j];
else break;
}
//用待插数据覆盖回来（第二步结束后下标的下一个位置）
a[j + 1] = temp;
}
}
总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
4.希尔排序
介绍： 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
核心：
希尔（shell）排序：
一个叫做shell的科学家发明的
优化后的插入排序
引入步长的概念：
一开始是 len/2 然后每次 除2 到1为止
根据步长来分组，然后组内作插入排序
//希尔排序
void shell_sort(int* a, int len)
{
int j, temp;
int step = len >> 2;
while ( step )//根据步长来分组
{
//组内作插入排序
//从step开始 len-1-step轮
for( int i = step ; i < len; i++ )
{
temp = a[i];//临时保存待插数据
//待插数据前一个开始往前循环（越界循环结束）
for ( j = i-step; j >= 0 ; j -= step )
{
//比待插数据大则往后覆盖
if (a[j] > temp) a[j + step] = a[j];
else break;
}
//用待插数据覆盖回来（第二步结束后下标的下一个位置）
a[j + step] = temp;
}
step >>= 1;
}
}
总结：
希尔排序是对直接插入排序的优化。
当step > 1时都是预排序，目的是让数组更接近于有序。当step == 1时，数组已经接近有序的 了，这样就会很快。这样整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N1.3— N2）
稳定性：不稳定
5.直观感受四种算法的时间复杂度
这里随机产出100000个数字，利用上面4种排序算法进行排序，结果如下，可以看到希尔排序仅仅用了16ms
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
//数据个数
#define NUM 100000
void init(int* a, int len);
void bubble_sort(int* a, int len);
//选择排序
void select_sort(int* a, int len);
//插入排序
void insert_sort(int* a, int len);
//希尔排序
void shell_sort(int* a, int len);
int main() {
ULONGLONG oldTime, newTime;
srand(time(NULL));
int arr[NUM];
init(arr, NUM);//初始化
//获取排序前时间
oldTime = GetTickCount64();
bubble_sort(arr, NUM);//排序
//获取排序后时间
newTime = GetTickCount64();
printf("bubble_sort:%llu\n", newTime - oldTime);
init(arr, NUM);
oldTime = GetTickCount64();
select_sort(arr, NUM);
newTime = GetTickCount64();
printf("select_sort:%llu\n", newTime - oldTime);
init(arr, NUM);
oldTime = GetTickCount64();
insert_sort(arr, NUM);
newTime = GetTickCount64();
printf("insert_sort:%llu\n", newTime - oldTime);
init(arr, NUM);
oldTime = GetTickCount64();
shell_sort(arr, NUM);
newTime = GetTickCount64();
printf("shell_sort:%llu\n", newTime - oldTime);
while (1);
return 0;
}
void init(int* a, int len) {
for (int i = 0; i < len; i++)
a[i] = rand() % 1000;
}
//希尔排序
void shell_sort(int* a, int len) {
int step = len / 2;
int temp;
int j;
while (step) {//分组
//组内做插入排序
for (int i = step; i < len; i++) {//每次循环插入a[i]
temp = a[i];//临时存储待插数据
for (j = i - step; j >= 0 && a[j] > temp; j -= step) {//从前往后覆盖
a[j + step] = a[j];
}
a[j + step] = temp;
}
step /= 2;//每次步长变成原来的一半
}
}
//插入排序
void insert_sort(int* a, int len) {
int temp;
int j;
for (int i = 1; i < len; i++) {//每次循环插入a[i]
//把a[i] 插入到 a[0] - a[i-1] 数组中去
temp = a[i];//临时存储待插数据
for (j = i - 1; j >= 0 && a[j] > temp; j--) {//从前往后覆盖
a[j + 1] = a[j];
}
//插入进来
a[j + 1] = temp;
}
}
//选择排序
void select_sort(int* a, int len) {
int min_idx;//记录最小的元素的下标
int temp;
for (int i = 0; i < len - 1; i++) {//找len-1次
//每次 找出 a[i] - a[len-1] 范围内最小的元素
min_idx = i;//假设a[i]最小
for (int j = i; j < len; j++) {
min_idx = ((a[min_idx] < a[j]) ? min_idx : j);
}
//a[min_idx] 和 a[i]交换
temp = a[i];
a[i] = a[min_idx];
a[min_idx] = temp;
}
}
void bubble_sort(int* a, int len) {
int temp;
for (int j = 0; j < len - 1; j++) {
for (int i = 0; i < len - j - 1; i++) {//0 - len-2
if (a[i] > a[i + 1]) {//不符合要求
//交换
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
}
三、基于非比较的排序算法
1.基数排序
介绍：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
核心：
基数排序 ：O(n)
最快的排序方式 没有之一
利用数组下标天然有序的特性来进行排序
max:最大元素值
限制很多：
只能排正整数（优化后可以对所有整数排序）
不能有重复
空间可能耗费特别大
临时空间大小
//基数排序
void radix_sort(int* a, int len, int max)
{
int index = 0;
//先准备一个临时数组 max+1
int* pTemp = (int*)malloc(sizeof(int) * (max + 1));
assert(pTemp); //判断申请成功没
//初始化为-1//for (int i = 0; i <= max; i++) pTemp[i] = -1;
memset(pTemp, -1, sizeof(int) * (max + 1));
//将待排数组放到临时数组中，待排数组的值作为临时数组的下标
for (int i = 0; i < len; i++) pTemp[a[i]] = a[i];
//从临时数组中把排序好的数据放回原数组中
for (int i = 0; i <= max; i++)
{
if ( pTemp[i] != -1 )
{
a[index++] = pTemp[i];
}
}
//释放内存
free(pTemp);
}
总结：
时间复杂度：O（n+k）
空间复杂度：O（n+k）
不能对小数进行排序，但是速度极快
2.箱(桶)排序
介绍：桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
核心：
桶(箱)排序:bucket_sort
把数据分成若干个箱子 然后箱子里用其他排序
这里是按个位十位分箱，内部类似于基数排序
//箱排序
void bucket_sort(int* a, int len)
{
int idx, k;
int n = 1;
int* pTemp = NULL;
while ( n < AREA )//1000以内的数字，AREA ==1000
{
//1 做箱子 并初始化箱子
pTemp = (int*)malloc(10 * len * sizeof(int));
for (int i = 0; i < 10 * len; i++) pTemp[i] = -1;
//2 根据特性(对应位作为箱子的编号)放入箱子中
for (int i = 0; i < len; i++)
{
//获取到数据这一轮要看的位上的数据
idx = a[i] / n % 10;
pTemp[idx * len + i] = a[i];
}
//3 从箱子中取出，覆盖a数组
k = 0;
for (int i = 0; i < 10*len; i++)
{
if ( pTemp[i] != -1 )
a[k++] = pTemp[i];
}
//4 销毁箱子
free(pTemp);
pTemp = NULL;
n *= 10;
}
}
四、递归比较排序算法
1.快速排序
介绍：快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进。
核心：
快速排序：就是分组排序
把数据分成两组
确定中间值，左边都比中间值小 右边都比中间值大
递归(递推)持续分组 到 不可再分(一组只有一个数据)为止
void Quick_sort(int* a, int len)
{
quick_sort(a, 0, len - 1);
}
void quick_sort(int* a, int Left, int Right)
{
int L = Left, R = Right;
if ( L >= R ) return; //递归结束
// 先假设a[left]是中间数据,并临时保存
int temp = a[L];
// 循环挪动l和r并覆盖 循环结束后 L==R
while ( L < R )
{
// 先挪右边的
while ( L < R && a[R] > temp) R--;
a[L] = a[R];
// 再挪左边的
while (L<R && a[L] < temp ) L++;
a[R] = a[L];
}
// 用中间数据覆盖回来
a[L] = temp; //a[R] = temp;
quick_sort(a, Left, R - 1);
quick_sort(a, L + 1, Right);
}
2.归并排序
介绍：归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
a.普通归并
核心：两个有序数组合并成一个有序数组
void Merge_sort(int* a, int L, int M, int R)
{
int Left = L, Right = M + 1;
if (L >= R) return;
//开临时内存
int* pTemp = (int*)malloc(sizeof(int) * (R - L + 1));
int k = 0;
//两个中有一个放完了
while ( Left <= M && Right <= R )
{
if (a[Left] < a[Right]) pTemp[k++] = a[Left++];
else pTemp[k++] = a[Right++];
}
//左边还没放完
if (Left <= M) memcpy(pTemp + k, a + Left, sizeof(int) * (M - Left + 1));
//右边还没放完
else memcpy(pTemp + k, a +Right, sizeof(int) * (R - Right + 1));
//覆盖回去
memcpy( a + L , pTemp, sizeof(int) * (R - L + 1));
//释放内存
free(pTemp);
}
b.归并递归
- 核心：把无序数组完全拆开，再进行归并排序
void Merge_Sort(int* a, int len)
{
merge__sort(a, 0, len - 1);
}
void merge__sort(int* a, int L, int R)
{
// L和R不相等，说明还没拆到只剩一个，继续拆
if (L < R)
{
int m = L + (R - L) / 2;
merge__sort(a, L, m); //左边一半
merge__sort(a, m + 1, R); //右边一半
Merge_sort(a, L, m, R); //拆到无法拆了就合并
}
}
版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_72157449/article/details/129104981
