数据结构——排序（2）

数据结构——排序(2)

文章目录

数据结构——排序(2)
- 前言：
- 1.快速排序（非递归版本）
- - 基本步骤：
  - 代码实现
- 2.归并排序
- - 算法思想：
  - 核心步骤：
  - 代码实现：
  - 特征总结：
- 3.计数排序（非比较排序）
- - 算法概念：
  - 核心步骤：
  - 代码实现：
  - 特征总结：
- 4.排序算法的时间复杂度及稳定性分析

前言：

前面已经介绍了直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序已经递归版本的快速排序，在本篇将接着介绍快速排序的非递归版本、归并排序以及计数排序。

1.快速排序（非递归版本）

非递归版本的快速排序需要借助数据结构：栈

基本步骤：

1.初始化栈

2.推入初始区间：将整个数组的起始和结束索引推入栈中。

3.循环处理栈中的区间

4.推入新的区间：将基准元素的左右两个子区间压入栈中

5.重复步骤 3 和 4

6.结束

代码实现

//⾮递归版本快排
//借助数据结构---栈
void QuickSortNonR(int* arr, int left, int right)
{
	ST st; 
	STInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		//取栈顶元素---取两次
		int begin = StackTop(&st);
		StackPop(&st);

		int end = StackTop(&st);
		StackPop(&st);

		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;

		while (cur<=end)
		{
			if (arr[cur] <= arr[keyi] && ++prev != cur) 
			{
				Swap(&arr[cur], &arr[prev]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);

		keyi = prev;

		//根据基准值划分左右区间
	
		if (keyi + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
		if (keyi - 1 > begin)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
	STDestroy(&st);
}

2.归并排序

算法思想：

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。

核心步骤：

在这里插入图片描述

代码实现：

//归并排序
void _MergeSort(int*arr,int left,int right,int*tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//合并
	//[left,mid]  [mid+1,right]
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;

	while (begin1<=end1 && begin2<=end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}
	//要么begin1越界 要么begin2越界
	while (begin1<=end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2<=end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//把tmp中的数据拷贝回arr中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

特征总结：

时间复杂度：O(nlogn)

空间复杂度：O(n)

3.计数排序（非比较排序）

算法概念：

计数排序（Counting Sort）计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。它是一种非比较排序算法，其核心思想是通过计数每个元素的出现次数来进行排序，适用于整数或有限范围内的非负整数排序。

核心步骤：

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

2）根据统计的结果将序列回收到原来的序列中
在这里插入图片描述

代码实现：

//计数排序
void CountSort(int* arr, int n)
{
	//根据最大值最小值确定数组大小
	int max = arr[0], min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max) 
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int)* range);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//初始化range属组中所有的数据为0
	memset(count, 0, range * sizeof(int));

	//统计数组中每个数据出现的次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	//取count中的数据，往arr中放
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}

	}
}

特征总结：

计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限。

时间复杂度： O(N + range)

空间复杂度： O(range)

稳定性：稳定.

4.排序算法的时间复杂度及稳定性分析

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
直接选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(nlogn)~O(n²)	O(n^1.3)	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(nlogn)~O(n)	不稳定