【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）
•
算法结构
目录
一，计数排序
1，基本思想
2，思路实现
3，计数排序的特性总结：
二，排序算法复杂度及稳定性分析
三，排序系列所有源代码
Sort.h
Sort.c
Stack.h
Stack.c
一，计数排序
计数排序也叫非比较排序；
1，基本思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用
操作步骤：
1，统计相同元素出现次数
2，根据统计的结果将序列回收到原来的序列中
图解原理：
对这样一个不需要比较的排序就完成了；
2，思路实现
// 计数排序
void CountSort(int* arr, int n)
{
int i = 0;
int max = arr[0], min = arr[0];
//找最大，最小值
for (i = 0; i max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//空间大小
int sum = max - min + 1;
//开辟空间并且使元素值都为0
int* arr1 = (int*)calloc(sum, sizeof(int));
//给新数组赋值
for (i = 0; i < n; i++)
{
arr1[arr[i] - min]++;
}
int j = 0;
//回收到原来的序列中
for (i = 0; i < sum; i++)
{
while (arr1[i]--)
{
arr[j++] = i + min;
}
}
}
然后我们运行测试一下：
可以看到是有序的，选择排序就 OK 了；
3，计数排序的特性总结：
1， 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限
2.，时间复杂度：O(N+K)
3， 空间复杂度：O(N)
4, 稳定性：稳定
二，排序算法复杂度及稳定性分析
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(N^2) | O(N) | O(N^2) | O(1) | 稳定 |
| 选择排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不稳定 |
| 直接插入排序 | O(N^2) | O(N) | O(N^2) | O(1) | 稳定 |
| 希尔排序 | O(NlongN)~O(N^2) | O(N^1.3) | O(N^2) | O(1) | 不稳定 |
| 堆排序 | O(NlongN) | O(NlongN) | O(NlongN) | O(1) | 不稳定 |
| 归并排序 | O(NlongN) | O(NlongN) | O(NlongN) | O(N) | 稳定 |
| 快速排序 | O(NlongN) | O(NlongN) | O(N^2) | O(N) | 不稳定 |
| 计数排序 | O(N+K) | O(N+K) | O(N+K) | O(K) | 稳定 |
三，排序系列所有源代码
Sort.h
#pragma once #include #include #include #include"Stack.h" //打印 void PrintSort(int* arr, int n); //插入排序 void InsertSort(int* arr, int n); //希尔排序 void HillSort(int* arr, int n); //选择排序 void SeleSort(int* arr, int n); //堆排序 void HeapSort(int* arr, int n); //向下调整 void DownAdjust(int* arr, int n, int i); 冒泡排序 //void BubblSort(int* arr, int n); //快速排序 void QuickSort(int* arr, int begin, int end); //三数取中 int middle(int* arr, int left, int right); //快慢指针法 int PartSort3(int* arr, int left, int right); //挖坑法 int PartSort2(int* arr, int left, int right); //霍尔排序 int PartSort1(int* arr, int left, int right); //快速排序(非递归) void QuickNon(int* arr, int begin, int end); //归并排序 void MergerSort(int* arr, int begin, int end); //归并排序(非递归) void MergerSortNon(int* arr, int begin, int end); // 计数排序 void CountSort(int* arr, int n);
Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//打印
void PrintSort(int* arr, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
//交换
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//插入排序
void InsertSort(int* arr, int n)
{
int i = 0;
for (i = 0; i = 0)
{
if (arr[end] >= tmp)
{
//交换
Swap(&arr[end], &arr[end+1]);
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//希尔排序
void HillSort(int* arr, int n)
{
int gap = n;
int i = 0;
while (gap > 1)
{
gap = gap / 2;
for (i = 0; i = 0)
{
if (arr[end] >= tmp)
{
//交换
Swap(&arr[end], &arr[end + gap]);
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
//选择排序
void SeleSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
Swap(&arr[begin], &arr[mini]);
// 如果maxi和begin重叠，修正一下即可
if (begin == maxi)
{
maxi = mini;
}
Swap(&arr[end], &arr[maxi]);
++begin;
--end;
}
}
//向下调整
void DownAdjust(int* arr, int n, int i)
{
int perent = i;
int child = perent* 2 + 1;
while (child<n)
{
if (child+1 arr[child])
{
child++;
}
if (arr[perent] = 0; i--)
{
//向下调整
DownAdjust(arr, n, i);
}
//交换，删除排序法
while (n > 1)
{
//交换
Swap(&arr[0], &arr[n - 1]);
n--;
//向下调整
DownAdjust(arr, n, 0);
}
}
//三数取中
int middle(int* arr, int left, int right)
{
//int mid = (left +right)/ 2;
//随机数取中
int mid = left + (rand() % (right - left));
if (arr[left] < arr[mid])
{
if (arr[mid] < arr[right])
{
return mid;
}
if (arr[left] < arr[right])
{
return right;
}
else
{
return left;
}
}
//arr[mid] arr[right])
{
return mid;
}
if (arr[left] > arr[right])
{
return right;
}
else
{
return left;
}
}
}
//霍尔排序
int PartSort1(int* arr, int left, int right)
{
//三数取中
int ret = middle(arr, left, right);
Swap(&arr[left], &arr[ret]);
int keyi = left;
while (left < right)
{
//右边先走
while (left=arr[keyi])
{
right--;
}
//左边后走
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
//交换
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
//挖坑法
int PartSort2(int* arr, int left, int right)
{
//三数取中
int ret = middle(arr, left, right);
Swap(&arr[left], &arr[ret]);
int key = arr[left];
int hole = left;
while (left < right)
{
while (left = key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] <= key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
//前后指针法
int PartSort3(int* arr, int left, int right)
{
//三数取中
int ret = middle(arr, left, right);
Swap(&arr[left], &arr[ret]);
int keyi = left;
int slow = left, fast = left+1;
while (fast<=right)
{
if (arr[fast] < arr[keyi] && ++slow!=fast)
{
//交换
Swap(&arr[fast], &arr[slow]);
}
fast++;
}
Swap(&arr[slow], &arr[keyi]);
return slow;
}
//插入排序(改造版)
void InsertSort1(int* arr, int left, int right)
{
int i = 0;
for (i = left; i = 0)
{
if (arr[end] >= tmp)
{
//交换
Swap(&arr[end], &arr[end + 1]);
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//快速排序
void QuickSort(int* arr, int begin, int end)
{
srand(time(0));
if (begin >= end)
{
return NULL;
}
if (end - begin = end)
{
return;
}
//插入
STPush(&ps, end);
STPush(&ps, begin);
//栈不为空就进去
while (!STEmpty(&ps))
{
int left = STInsert(&ps);//栈顶元素
STPop(&ps);//删除
int right = STInsert(&ps);
STPop(&ps);
int keyi = PartSort1(arr, left, right);
//排序[left,keyi-1] & [keyi+1,right]
if (keyi + 1 < right)
{
//插入
STPush(&ps, right);
STPush(&ps, keyi + 1);
}
if (left < keyi - 1)
{
//插入
STPush(&ps, keyi - 1);
STPush(&ps, left);
}
}
//销毁
STDestroy(&ps);
}
//归并
void Merger(int* arr, int* tmp,int begin,int end)
{
int mid = (begin + end) / 2;
if (begin == end)
{
return;
}
//排序【begin,mid】& 【mid+1,end】
Merger(arr, tmp, begin,mid);
Merger(arr, tmp, mid+1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = 0;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while(begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 = end)
{
return;
}
//开辟同等大小数组
int* tmp = (int*)malloc((end - begin + 1)*sizeof(int));
//归并
Merger(arr, tmp, begin, end);
free(tmp);
tmp = NULL;
}
//归并排序(非递归)
void MergerSortNon(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
//开辟同等大小数组
int* tmp = (int*)malloc((end - begin + 1) * sizeof(int));
int gap = 1;
int j = 0;
while (gap < end)
{
for (j = 0; j = end)
{
break;
}
if (end2 >end)
{
end2 = end;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//进行拷贝
memcpy(arr + j, tmp, (end2 - j+ 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
// 计数排序
void CountSort(int* arr, int n)
{
int i = 0;
int max = arr[0], min = arr[0];
//找最大，最小值
for (i = 0; i max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//空间大小
int sum = max - min + 1;
//开辟空间并且使元素值都为0
int* arr1 = (int*)calloc(sum, sizeof(int));
//给新数组赋值
for (i = 0; i < n; i++)
{
arr1[arr[i] - min]++;
}
int j = 0;
//回收到原来的序列中
for (i = 0; i < sum; i++)
{
while (arr1[i]--)
{
arr[j++] = i + min;
}
}
}
Stack.h
#pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct StackTop
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//返回栈顶
STDataType STInsert(ST* ps);
//数量
int STSize(ST* ps);
//判断是否为空
int STEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//销毁
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//插入
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
ps->capacity = ps->top == 0 ? 4 : ps->capacity*2;
ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity);
}
ps->a[ps->top] = x;
ps->top++;
}
//删除
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//返回栈顶
STDataType STInsert(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top-1];
}
//数量
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//判断是否为空
int STEmpty(ST* ps)
{
assert(ps);
if (ps->top == 0)
{
return 1;
}
else
{
return 0;
}
}
同志们！排序的知识就到这里了！
后面博主会陆续更新；
如有不足之处欢迎来补充交流！
完结。。
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/ee0b25960d.html
赞 (0)
如何理解鲁棒性？为什么robustness会翻译为鲁棒性？
« 上一篇
1天前
C语言从入门到实战——结构体与位段
下一篇 »
1天前
相关推荐
-
如何把word檔案自動化
1.安裝 pip install jojo-office ( 安裝這個) 2.讀取表格內容與文章內容，範例如下 import office from docx import Doc…
-
IS-IS：04 DIS
IS-IS 协议只支持两种网络类型，即广播网络和点到点网络。与 OSPF 协议相同， IS-IS 协议在广播网络中会将网络视为一个伪节点 （ Pesudonde，简称 PSN）…
-
R语言【taxlist】——subset()：取taxlist对象的子集
Package taxlist version 0.2.4 Description taxlist对象的子集将通过逻辑操作或模式匹配来完成。子集可以引用包含在插槽taxonName…
-
元旦特辑：Note6—选择排序
目录 前言❌ 1. 基本思想⚠️ 2. 直接选择排序🟢 2.1 思路分析✳️ 2.2 代码实现❎ 2.2.1 sort.h 2.2.2 sort.c 2.2.3 t…
-
短视频与小程序：如何实现完美结合？
在短视频日益成为人们娱乐、社交和信息获取的重要渠道的今天，如何在短视频平台进行小程序推广成为了许多企业和品牌关注的焦点。本文将介绍如何利用短视频平台进行小程序推广，提升品牌曝光和用…
-
notepad++安装json插件【真香】
1.打开notepad++，导航栏点击插件—》插件管理 2.搜索json，安装json tools，json viewer，点击前面方框 3.点击安装，等待重启no…
-
Mysql分区表——范围分区表（新增、删除、重组、查看）
文章目录 一、mysql分区表分类 范围分区（Range Partitioning 哈希分区（Hash Partitioning） 列表分区（List Partitioning） …
-
【word】论文、报告：①插入图表题注，交叉引用②快速插入图表目录③删改后一键更新
【word】①插入图表题注，②删改后一键更新 写在最前面 插入题注 交叉引用 修改插入题注的文字格式 快速插入图表目录 插入题注后有删改，实现编号一键更新 🌈你好呀…
-
MyBatis之动态SQL、#与$的区别和结果映射
目录 前言 一、MyBatis动态SQL 1.动态SQL是什么 2.动态SQL的作用 3.常用动态SQL元素 1. where + if 元素 2. set + if 元素 3. …
-
BUUCTF–mrctf2020
这是一题64位的shellocde题，没啥花招入门题。看下保护： 有可执行的段。接着我们看看IDA： 主函数中无法反汇编，那么我们直接看汇编代码。其实很简单，通过系统调用执行put…
