数据结构排序——计数排序和排序总结

现在常见算法排序都已讲解完成，今天就再讲个计数排序。再总结一下

---

---

1.计数排序

计数排序是一种非基于比较的排序算法，它通过统计数组中每个元素出现的次数，然后根据元素的值和出现次数重新构造数组，从而实现排序。计数排序适用于元素范围比较小且元素非负的情况

步骤：

1. 找出待排序的数组中最大和最小的元素：min和max
2. 统计数组中每个值为 i 的元素出现的次数，存入新建数组 C 的第 i-min 项(c初始化时都是0)，每遇到一次，对应下标上的数就++
3. 反向填充目标数组：利用新建的数组把数据覆盖回去

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

void CountSort(int* a, int n)
{
	//先找最大最小，确定范围
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}

	int range = max - min + 1;
	int* count= (int*)calloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	//开始想count中累加了
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	//赋值覆盖
	int a_index = 0;
	for (int i = 0; i < range; i++)
	{
		for (int j = 0; j < count[i]; j++)
		{
			a[a_index] = i + min;
			a_index++;
		}
	}
}

int main()
{
	int a[] = { 2,4,1,7,9 };
	CountSort(a, 5);
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);
	}

	return 0;
}

2.排序总结

排序算法	时间复杂度	空间复杂度	稳定性
直接插入排序	O(N^2)	O(1)	稳定
希尔排序	O(N^1.3)	O(logN)	不稳定
选择排序	O(N^2)	O(N)	不稳定
堆排序	O(N*logN)	O(N)	不稳定
冒泡排序	O(N^2)	O(1)	稳定
快速排序	O(N*logN)	O(logN)	不稳定
归并排序	O(N*logN)	O(N)	稳定

不稳定的情况之一：

1. 希尔：根据gap分组不在一个组
2. 选择：3 3 1 1…
3. 堆排序：向下调整过程
4. 快排：相同的数字其中一个在keyi的位置

---

3.排序oj（排序数组）

题目详情

912. 排序数组 - 力扣（LeetCode）

代码

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

int GetMid(int* a,int left, int right)//找中间的
{
	// a[left]      a[mid]           a[right]
	int mid = left+(rand()%(right-left));
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int cur = left + 1;
	int key = a[left];//储存一下，后面比较来用，用a[left]会被替代
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			cur++;
			left++;
		}
		else if (a[cur] == key)
		{
			cur++;
		}
		else
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
	}
	QuickSort(a, begin, left - 1);
	QuickSort(a, right + 1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
    srand(time(0));

    QuickSort(nums,0,numsSize-1);
    *returnSize=numsSize;
    return nums;
}

1. Swap函数： 这是一个用于交换两个整数值的简单函数。
2. GetMid函数： 用于在数组中找到三个位置（左、中、右）的元素，从而选取合适的中间值。它通过比较这三个位置的元素，找到其中介于最小和最大之间的值。
3. QuickSort函数：实现了快速排序的核心逻辑
   • 选择中间值，并将其与数组的第一个元素交换，作为基准值。
   • 遍历数组，将小于基准值的元素移到基准值左侧，大于基准值的元素移到右侧，相等的元素留在中间。
   • 对基准值左右两侧的子数组递归地进行快速排序，直到左右两侧都排好序

思路

这题有根据快排的痛点进行特地进行测试用例的编写

一开始大家肯定就直接放上去一个快排，结果发现：超时了（过不去的测试用例是有序的）

• 所以第一次我们要加上三选一
• 发现还不行（过不去的是数字全部一样），现在就考虑换上三路划分
• 最后发现测试用例可以，但是时间过长，就改一下Getmid函数，之前mid是$(left+right)/2$,现在是left+(rand()%(right-left))

好啦，排序的内容也到这里啦。下面就要开启c++的内容了