1. Toy模板网首页
  2. > Toy博客

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）

7月前 作者：手法king 分类：Toy博客 阅读(31) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一，计数排序

1，基本思想

2，思路实现

3，计数排序的特性总结：

二，排序算法复杂度及稳定性分析

三，排序系列所有源代码

Sort.h

Sort.c

Stack.h

Stack.c

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio

一，计数排序

计数排序也叫非比较排序；

1，基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用

操作步骤：

1，统计相同元素出现次数

2，根据统计的结果将序列回收到原来的序列中

图解原理：

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio

对这样一个不需要比较的排序就完成了；

2，思路实现

// 计数排序
void CountSort(int* arr, int n)
{
	int i = 0;
	int max = arr[0], min = arr[0];
	//找最大，最小值
	for (i = 0; i < n; i++)
	{
		if (arr[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;
		}
	}
}

然后我们运行测试一下：

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio

可以看到是有序的，选择排序就 OK 了；

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio

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) 稳定

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio

三，排序系列所有源代码

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#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 < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 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 < n-gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 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 <= end; i++)
		{
			if (arr[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<n && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[perent] < arr[child])
		{
			//交换
			Swap(&arr[perent], &arr[child]);
			perent = child;
			child = perent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int* arr, int n)
{
	//建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 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[left]
	else
	{
		if (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<right && arr[right]>=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 < right && arr[right] >= 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 < right; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 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 <10)
	{
		InsertSort1(arr,begin,end);
	}
	else
	{
		int keyi = PartSort1(arr, begin, end);
		//排序[begin,keyi) & [keyi+1,end]
		QuickSort(arr, begin, keyi);
		QuickSort(arr, keyi + 1, end);
	}
}

//快速排序(非递归)
void QuickNon(int* arr, int begin, int end)
{
	srand(time(0));
	ST ps;
	//初始化
	STInit(&ps);
	if (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 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//进行拷贝
	memcpy(arr + begin, tmp, (end - begin+1)*sizeof(int));
}

//归并排序
void MergerSort(int* arr, int begin, int end)
{
	if (begin >= 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; j += 2 * gap)
		{
			int begin1 = j, end1 = begin1+gap-1;
			int begin2 =end1+1, end2 = begin2+gap-1;
			int i = 0;
			//处理边界问题
			if (end1 >= 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 < n; i++)
	{
		if (arr[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<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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;
	}
}

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio

同志们！排序的知识就到这里了！

后面博主会陆续更新；

如有不足之处欢迎来补充交流！

完结。。

【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）,排序算法,算法,数据结构,c语言,visualstudio文章来源地址https://www.toymoban.com/news/detail-715780.html

到了这里，关于【数据结构】计数排序 & 排序系列所有源代码 & 复杂度分析（终章）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】-计数排序

    【数据结构】-计数排序

    🎇作者：小树苗渴望变成参天大树 🎉 作者宣言：认真写好每一篇博客 🎊作者gitee:link 如 果 你 喜 欢 作 者 的 文 章 ，就 给 作 者 点 点 关 注 吧！ 答应大家的计数排序今天它来了，这也是一个非常巧妙的方法，不通过比较元素的大小就可以排序出来，通过用另一个人数组

    2023年04月17日
    浏览(24)
  • 数据结构——lesson13排序之计数排序

    数据结构——lesson13排序之计数排序

    hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页：大耳朵土土垚的博客 💥 所属专栏：数据结构学习笔记 、排序算法合集 💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行

    2024年04月10日
    浏览(33)
  • 数据结构——归并排序和计数排序的介绍

    数据结构——归并排序和计数排序的介绍

    归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

    2024年02月11日
    浏览(46)
  • 【数据结构初阶】八大排序(三)——归并排序&&计数排序

    【数据结构初阶】八大排序(三)——归并排序&&计数排序

    大家好我是沐曦希💕 往期博客：【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 【数据结构初阶】八大排序(二)——快速排序冒泡排序 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一

    2024年02月03日
    浏览(58)
  • 【数据结构】排序算法（二）—＞冒泡排序、快速排序、归并排序、计数排序

    【数据结构】排序算法（二）—＞冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕： 个人主页  🎥 个人专栏： 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子，都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(35)
  • 【C语言】数据结构——排序三（归并与计数排序）

    【C语言】数据结构——排序三（归并与计数排序）

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了排序，包括直接插入排序，希尔排序，选择排序，堆排序，冒泡排序和快排。 今天我们来讲一讲归并排序和计数排序。 关注博主或是订阅专栏，掌握第一消息。 归并排序的

    2024年01月19日
    浏览(29)

  • 数据结构与算法之排序: 计数排序 (Javascript版)

    排序 排序：把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例) 计数排序 核心思想 ：通过计数而非比较来进行排序，借助数组下标本身就是有序的原理实现 适用范围：较小的非负整数序列和最小值和最大值之间的数字范围比较合适 基数排序需要新增一个计数数

    2024年02月06日
    浏览(27)
  • 【数据结构】归并排序的两种实现方式与计数排序

    【数据结构】归并排序的两种实现方式与计数排序

    前言：在前面我们讲了各种常见的排序，今天我们就来对排序部分收个尾，再来对归并排序通过递归和非递归的方法进行实现，与对计数排序进行简单的学习。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博

    2024年01月18日
    浏览(33)
  • 数据结构：排序干货！（7大排序汇总+快速排序的优化+计数排序+基数排序+桶排序）

    数据结构：排序干货！（7大排序汇总+快速排序的优化+计数排序+基数排序+桶排序）

    目录 概念 插入排序 直接插入排序 希尔排序 选择排序 直接选择排序 双向选择排序 堆排序 交换排序 冒泡排序 快速排序 Hoare法 挖坑法 前后指针法 快排的优化 三数取中法 非递归快排 归并排序 分治算法+二路归并 非递归归并 应用 排序总结 其他排序 计数排序 简单版本 复杂

    2024年02月06日
    浏览(33)
  • 【数据结构】一文带你全面了解排序（下）——冒泡排序、快速排序、归并排序、计数排序

    【数据结构】一文带你全面了解排序（下）——冒泡排序、快速排序、归并排序、计数排序

      目录 一、常见排序算法的实现   1.1 交换排序 1.1.1 基本思想 1.1.2 冒泡排序  1.1.3 快速排序 1.2 归并排序 1.3 非比较排序 二、排序算法复杂度及稳定性分析  人总得为过去的懒惰而付出点代价！ 1.1.1 基本思想 基本思想：所谓交换，就是根据序列中两个记录键值的比较结

    2024年02月16日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包