数据结构：10、排序

本文将会介绍8种排序，并在文章末附上代码

一、排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排
序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二、排序的实现

1、直接插入排序

直接插入排序就是判断这个数是否比前面的数小，如果小就放在这个地方，然后一趟一趟的，他的排序在越接近有序就越快，代码和测试结果如下。

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end>=0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

2、希尔排序

希尔排序就是一个叫希尔的大佬发明出来的，既然直接插入排序越接近有序就越快，那么给他划分成一块一块，对每一块进行排序，然后在进行总体排序，代码和测试结果如下。

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;  
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}

			a[end + gap] = tmp;
		}
	}
}

3、选择排序

这个选择排序的原理就是选出这组数据的最大或者最小插在最前或者最后，听起来就很慢，所以这里进行了一点点优化，一下排序两个数据，但是依然还是很慢很拉跨，在文章末进行所有测试的比较时可以看出，代码与测试结果如下。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (begin == maxi)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
}

4、堆排序

堆排序首先就是建堆，这里是升序所以就是建大堆，当建堆完成后，交换首尾两个数然后进行调整，这个就是堆排序，代码以及测试结果如下。

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

5、冒泡排序

冒泡排序，肯定都不陌生，我接触的第一个排序就是他，之前一直认为他最好用，直到接触了本文的其他排序，瞬间不香了，他的原理就是每一趟都依次进行比较交换，代码与测试结果如下。

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		bool exchange = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				int tmp = a[i];
				a[i] = a[i - 1];
				a[i - 1] = tmp;

				exchange = true;
			}
		}

		if (exchange == false)
		{
			break;
		}
	}
}

6、快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

有三种划分方式，第一种也是他本人发明的，就是选一个做为key然后左边找比key小的数右边找比key大数，找了停止，然后交换左右两边，直到两边相遇，再把相遇的值和key交换，这样就完成了一次排序，就会形成key左边的比key小，右边的比key大。

第二种就是挖坑法，把key的值保存在临时变量里面，然后形成一个坑，然后右边大的左找到比他的小放到坑里，在找到的地方形成一个坑，左边在走找到大的放到坑里，在挖个坑，直到遇到然后把key放到相遇的这个坑里。

第三种就是前后指针的方法，就是prev每次都需要指向从左到它本身之间最后一个小于基准值的数，如果cur的值大于基准值，这时只让cur++,如果cur指向的位置小于基准值，这时我们让prev++后，判断是否与cur的位置相等，若不相等，则交换cur和prev的值。直到cur>end后，我们再交换prev和基准值，这样基准值的位置也就确定了。

普通的递归快排结束了，就是利用栈中进行排序的方式，方法和上面一样，就是把数据的存储利用栈进行压入与取出，代码与测试结果如下。

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else 
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

int PartSort1(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);

	return left;
}

int PartSort2(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;

	return hole;
}

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort1(a, left, right);
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}

	StackDestroy(&st);
}

7、归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤就是分解合并，不过在合并时要注意边界的问题，代码实现与测试结果如下。

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		//printf("\n");
		gap *= 2;
	}
	free(tmp);
}

8、计数排序

计数排序的原理就是统计相同元素出现次数，根据统计的结果将序列回收到原来的序列中，他的排序很快， 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限，代码与测试结果如下。

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
		{
			a[k++] = j + min;
		}
	}
}

9、排序的稳定以及时间复杂度

排序方法平均情况最好情况最坏情况辅助空间稳定性
冒泡排序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(n*longn)~O(n^2)O(n^1.3)O(n^2)O(1)不稳定
堆排序O(n*longn)O(n*longn)O(n*longn)O(1)不稳定
归并排序O(n*longn)O(n*longn)O(n*longn)O(n)稳定
快速排序O(n*longn)O(n*longn)O(n^2)O(logn)~O(n)不稳定

三、代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
#include <time.h>

void TestInsertSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestShellSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestBubbleSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestSelectSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestHeapSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	HeapSort(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestQuickSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	//QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestMergeSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	//MergeSort(a, sizeof(a) / sizeof(int));
	MergeSortNonR(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestCountSort()
{
	int a[] = { 9,5,3,4,1,5,3,6,1,2 };
	PrintfArry(a, sizeof(a) / sizeof(int));
	CountSort(a, sizeof(a) / sizeof(int));
	PrintfArry(a, sizeof(a) / sizeof(int));
}

void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);


	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];

	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	BubbleSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	SelectSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	HeapSort(a5, N);
	int end5 = clock();

	int begin6 = clock();
	QuickSort(a6, 0, N - 1);
	int end6 = clock();

	int begin7 = clock();
	MergeSort(a7, N);
	int end7 = clock();

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("BubbleSort:%d\n", end3 - begin3);
	printf("SelcetSort:%d\n", end4 - begin4);
	printf("HeapSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("MergeSort:%d\n", end7 - begin7);
	printf("CountSort:%d\n", end8 - begin8);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
}

int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestBubbleSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestQuickSort();
	//TestMergeSort();
	//TestCountSort();
	TestOP();
	return 0;
}

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
#include "ST.h"
void PrintfArry(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end>=0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;  
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}

			a[end + gap] = tmp;
		}
	}
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		bool exchange = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				int tmp = a[i];
				a[i] = a[i - 1];
				a[i - 1] = tmp;

				exchange = true;
			}
		}

		if (exchange == false)
		{
			break;
		}
	}
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (begin == maxi)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else 
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

int PartSort1(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);

	return left;
}

int PartSort2(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;

	return hole;
}

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort1(a, left, right);
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}

	StackDestroy(&st);
}

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin == end)
		return;
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		//printf("\n");
		gap *= 2;
	}
	free(tmp);
}

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
		{
			a[k++] = j + min;
		}
	}
}

Sort.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
void InsertSort(int* a,int n);
void PrintfArry(int* a, int n);
void ShellSort(int* a, int n);
void BubbleSort(int* a, int n);
void Swap(int* p1, int* p2);
void SelectSort(int* a, int n);
void AdjustDown(int* a, int n, int parent);
void HeapSort(int* a, int n);
void QuickSort(int* a, int begin, int end);
int PartSort1(int* a, int left, int right);
int PartSort2(int* a, int left, int right);
int PartSort3(int* a, int left, int right);
void QuickSortNonR(int* a, int begin, int end);
void _MergeSort(int* a, int begin, int end, int* tmp);
void MergeSort(int* a, int n);
void MergeSortNonR(int* a, int n);
void CountSort(int* a, int n);

ST.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ST.h"

// 初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

// 入栈
void StackPush(ST* ps, STDatetype data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ST* newnode = (ST*)realloc(ps->a, newcapacity * sizeof(STDatetype));
		if (newnode == NULL)
		{
			perror("recalloc fail");
			return;
		}
		ps->a = newnode;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

// 获取栈顶元素
STDatetype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top-1];
}

// 获取栈中有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

// 销毁栈
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

ST.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDatetype;

typedef struct Stack
{
	STDatetype* a;
	int top;
	int capacity;
}ST;

// 初始化栈
void StackInit(ST* ps);
// 入栈
void StackPush(ST* ps, STDatetype data);
// 出栈
void StackPop(ST* ps);
// 获取栈顶元素
STDatetype StackTop(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);

这个测试结果十分惊人，可以看出冒泡排序和选择排序有多拉跨，值得一提的是计数排序，这个时间是在1ms内所以是0，本来想跑一百万个数但是跑了十分钟没出来，就跑了十万个数了。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/472580.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

二、阅读器的开发（初始）-- 1、阅读器简介及开发准备工作

二、阅读器的开发（初始）-- 1、阅读器简介及开发准备工作

1、阅读器工作原理及开发流程 1.1阅读器工作原理简介 电子书&#xff08;有txt、pdf、epub、mobi等格式&#xff09;->解析&#xff08;书名、作者、目录、封面、章节等&#xff09;->&#xff08;通过阅读器引擎&#xff09;渲染 -> 功能&#xff08;字号、背景色、…
阅读更多...
学生信息管理系统--修改信息（非常详细的修改，更新，撤销，删除逻辑）

学生信息管理系统--修改信息（非常详细的修改，更新，撤销，删除逻辑）

目录 概述修改包括的操作修改在每个模块中的应用 详解修改与更新取消删除 特殊概念数据集游标 总结 概述 学生信息管理系统&#xff0c;功能相对简单且代码重复性高&#xff0c;应该采用复用的思想来减少代码的冗余和提高代码的可维护性。然而&#xff0c;对于基础入门项目来说…
阅读更多...
SQL数据库和事务管理器在工业生产中的应用

SQL数据库和事务管理器在工业生产中的应用

本文介绍了关系数据库在工业生产中的应用以及如何使用事务管理器将生产参数下载到PLC&#xff0c;以简化OT/IT融合过程。 一 什么是配方&#xff08;Recipe&#xff09; 我们以一家汽车零件制造商的应用举例&#xff0c;该企业专业从事汽车轮毂生产制造。假设该轮毂的型号是“…
阅读更多...
echart trigger 为 axis 的时候不显示 tooltip 解决办法

echart trigger 为 axis 的时候不显示 tooltip 解决办法

echart trigger 为 axis 的时候不显示 tooltip 解决办法 在项目 vitetsvue3 中使用 echart 显示了一个曲线图&#xff1a; 但当把图表的 trigger 设置成 axis 的时候&#xff0c;鼠标扫过并不显示具体的数值&#xff0c;如上图所示。 但 trigger item 的时候是正常的。 解决…
阅读更多...
浏览器工作原理与实践--仅仅打开了1个页面，为什么有4个进程？

浏览器工作原理与实践--仅仅打开了1个页面，为什么有4个进程？

无论你是想要设计高性能Web应用&#xff0c;还是要优化现有的Web应用&#xff0c;你都需要了解浏览器中的网络流程、页面渲染过程&#xff0c;JavaScript执行流程&#xff0c;以及Web安全理论&#xff0c;而这些功能是分散在浏览器的各个功能组件中的&#xff0c;比较多、比较散…
阅读更多...
idea创建maven-archetype-quickstart框架无法显示src/目录

idea创建maven-archetype-quickstart框架无法显示src/目录

一、配置好idea中Maven目录 1、不使用idea自带Maven&#xff0c; 2、配置好Maven环境变量M2_HOME 3、修改maven中 setting.xml文件 <?xml version"1.0" encoding"UTF-8"?><settings xmlns"http://maven.apache.org/SETTINGS/1.2.0"…
阅读更多...
【C语言】—— 指针三 ： 参透数组传参的本质

【C语言】—— 指针三 ： 参透数组传参的本质

【C语言】—— 指针三 &#xff1a; 参透数组传参的本质 一、数组名的理解二、使用指针访问数组2.1、指针访问数组2.2、[ ] 的深入理解2.3、数组与指针的区别 三、一维数组的传参本质四、数组指针变量4.1、数组指针变量是什么4.2、 数组指针的初始化 五、二维数组传参的本质 一…
阅读更多...
【LabVIEW FPGA入门】插值、输出线性波形

【LabVIEW FPGA入门】插值、输出线性波形

概述 NI 的可重配置 I/O (RIO) 硬件使开发人员能够创建自定义硬件&#xff0c;以在坚固耐用、高性能和模块化架构中执行许多任务&#xff0c;而无需了解低级 EDA 工具或硬件设计。使用 RIO 硬件轻松实现的此类任务之一是模拟波形生成。本教程介绍了使用 CompactRIO 硬件和 LabV…
阅读更多...
计算机网络：计算机网络概述

计算机网络：计算机网络概述

计算机网络&#xff1a;计算机网络概述 因特网概述网络&#xff0c;互连网&#xff0c;因特网因特网发展的三个阶段因特网的标准化工作因特网组成 计算机网络的定义计算机网络的分类按使用者分类按传输介质分类按网络的覆盖范围分类按拓扑结构分类 因特网概述 网络&#xff0c…
阅读更多...
投简历没回复？9位DBA公众号集结，快上车！

投简历没回复？9位DBA公众号集结，快上车！

&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&#x1f61c;&#x1f61c; 中国DBA联盟(ACD…
阅读更多...
Unicode转码 [ASIS 2019]Unicorn shop1

Unicode转码 [ASIS 2019]Unicorn shop1

打开题目 我们买最贵的试试看&#xff0c;结果提示只能输入一个字符 抓包分析一下看看 从中可以发现源代码是如何处理price的 使用的是unicodedata.numeric() 但是我们查看页面源代码&#xff0c;发现页面的编码是utf-8编码 所以&#xff0c;前端html使用的是utf-8&#xff0…
阅读更多...
【学习】CMMI评估认证的意义和需要注意的问题

【学习】CMMI评估认证的意义和需要注意的问题

​ CMMI认证是软件能力成熟度集成模型&#xff0c;是软件行业中的一种质量管理体系&#xff0c;旨在评估软件开发组织的成熟度和能力&#xff0c;以帮助企业提高软件质量、降低成本、控制风险&#xff0c;并获得更好的商业效益。 一、CMMI评估认证的意义 1. 提高软件质量&am…
阅读更多...
win提权第二弹服务提权

win提权第二弹服务提权

阅读须知&#xff1a; 探索者安全团队技术文章仅供参考,未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作,由于传播、利用本公众号所提供的技术和信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者 本人负责&#xff0c;作者不为此承担任何责任,如…
阅读更多...
Windows 10中打开控制面板的13种方法，总有一种适合你

Windows 10中打开控制面板的13种方法，总有一种适合你

前言 虽然有传言称微软将取消控制面板，但它不会那么快消失。一些重要的设置仅在Windows 10的经典控制面板中找得到，它们不在设置应用程序中。本文有13种方法可以打开控制面板。 搜索开始菜单 你可以使用“开始”菜单的搜索功能搜索PC上的任何应用程序。在任务栏左侧的搜索…
阅读更多...
基于微信小程序的电影交流平台

基于微信小程序的电影交流平台

技术&#xff1a;springbootmysqlvue 一、背景 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。所以各行业&#xff0c;尤其是规…
阅读更多...
[蓝桥杯 2015 省 B] 生命之树

[蓝桥杯 2015 省 B] 生命之树

水一水的入门树形DP #include<iostream> #include<algorithm> #include<vector> using namespace std; using ll long long; #define int long long const int N 2e610; const int inf 0x3f3f3f3f; const int mod 1e97;int n; int w[N]; vector<vecto…
阅读更多...
环境检测LIMS系统 环境检测实验室信息管理系统

环境检测LIMS系统 环境检测实验室信息管理系统

环境检测行业在所有检测领域流程最长&#xff0c;数据量最大&#xff0c;专家组不同&#xff0c;认证体系的记录单/报告模板也是各自不同&#xff0c;因此如何选择一套适用本企业的LIMS也成为重中之重的工作&#xff0c;好的系统可以给企业带来非常大的便捷&#xff0c;也能大大…
阅读更多...
4 Redis持久化

4 Redis持久化

Redis 是一个内存数据库&#xff0c;所以其运行效率非常高。但也存在一个问题&#xff1a;内存中的数据是不持久的&#xff0c;若主机宕机或 Redis 关机重启&#xff0c;则内存中的数据全部丢失。当然&#xff0c;这是不允许的。Redis 具有持久化功能&#xff0c;其会按照设置以…
阅读更多...
让AI给你写代码（五）—— 应用Agent，理解Agent，走进现实世界

让AI给你写代码（五）—— 应用Agent，理解Agent，走进现实世界

本文想解决一个问题&#xff0c;理解Agent有啥具体的作用&#xff1f; 所谓读书千遍&#xff0c;不如动手一试&#xff0c;我们还是借助于上一篇&#xff0c;让AI给你写代码&#xff08;四&#xff09;—— 初步利用LangChain Agent根据输入生成&#xff0c;保存&#xff0c;执…
阅读更多...
基于springboot的药房进销存管理系统

基于springboot的药房进销存管理系统

光明医院药品库房信息管理系统的设计与实现医院管理员 1.医院管理员信息管理—增加删除修改人员信息(人员信息包括年龄性别学历) 2医院管理员账号密码修改 3发布公告—医院管理者发布医院公告对药库管理者可见 4查看药品入库出库信息 (药品厂商&#xff0c;生产日期&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023