八大基本排序方法_排列方式

目录

一、排序的概念

二、排序的分类

三、排序实现

1.插入排序

（1）基本思想：

（2）时间、空间复杂度及稳定性

 （3）代码实现

2.希尔排序

（1）基本思想：

（2）时间、空间复杂度及稳定性

（3）代码实现

3.直接选择排序

（1）基本思想：

（2）时间、空间复杂度及稳定性

（3）代码实现

4.堆排序

（1）基本原理：

（2）时间、空间复杂度及稳定性

（3）代码实现

5.冒泡排序

（1）基本原理

（2）时间、空间复杂度及稳定性

（3）代码实现

6.快速排序

（1）基本原理

（2）时间、空间复杂度及稳定性

（2）代码实现

7.归并排序

（1）基本原理

（2）时间、空间复杂度及稳定性

（3）代码实现

8.计数排序

（1）基本原理

（2）时间、空间复杂度及稳定性

（2）代码实现

---

一、排序的概念

排序，简而言之就是将一串数据按照一定的方式依次排列。例如按照数字大小升序或降序排列，按照英文字母的顺序依次排列等。在这些数据处于无序状态下的时候，都需要使用一定的方式来使其变得有序。

排序中还有一个概念，叫做稳定性。稳定性在排序中指的是数据经过排列后，相同数据的相对位置不会改变。比如现在有“8 9 8 5 5”这样一串数据，第一个8在第二个8之前，如果排序完成后第二个8依然在第二个8之前，则是稳定，反之若相对顺序被改变，则是不稳定。

二、排序的分类

为了能够将数据更加高效的排列好，由此而诞生了不同的排序方式。

常见的几种排序大致如下所示：

三、排序实现

1.插入排序

（1）基本思想：

把待排序的数据按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，以此得到一个有序序列

由此，在写代码时，我们可以设置一个end下标，[0，end]标志着一个局部有序序列，end+1的值便是需要插入的数据。将end+1代表的值依次与[0，end]中的数据对比，将大于end+1的数据依次往后挪动，当end+1小于某个数据或比下标0的位置的小时，就插入在该数据或下标0的位置上

（2）时间、空间复杂度及稳定性

时间复杂度：O（N^2）。逐个插入，最坏情况下比如逆序，每个数据都需要对比挪动

空间复杂度：O（1）。没有开辟额外的空间

稳定性：稳定。每个数据都需要对比一次，遇到相同的数据时就在该数据之后插入，可以做到相对位置不变

 （3）代码实现

在这里要注意，循环次数i应该是i < n - 1，因为n是数组的元素个数，如果是i < n，那么当i = n - 1时，就会有end + 1 = n，这样就会出现越界的情况

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

2.希尔排序

（1）基本思想：

希尔排序是插入排序的一个优化方案，本质上还是插入排序。但不同于插入排序的时间复杂度为O（N^2），希尔排序的时间复杂度大致为O（N^1.3）

希尔排序是利用一个gap值来划分数组，将整个数组划分为多个不同的组。假如有8个数据，gap = 3，划分方式如下所示

 假设要升序排列，那么就将每个组的数据按照插入排序的方式排列。排列好后缩小gap的值继续排列，直到gap = 1排列好后便能得到一个有序数列

（2）时间、空间复杂度及稳定性

时间复杂度：O（N^1.3）。此排序的时间复杂度不能没趟都根据最坏情况算，经过前人的大量实验，大致为O（N^1.3）

空间复杂度：O（1）。没有开辟额外的空间

稳定性：不稳定。希尔排序是分组排序的，且每个组内的数据不连续，无法保证每个组中的相同数据的相对位置不被改变

（3）代码实现

gap的取值是不能随便取的，通过前人大量的研究，得出了gap = n / 3 + 1或者gap = n / 2时的时间复杂度最小，所以一般在取gap时都是取的这两个值

这里部分人可能会有一个误区，就是在每组进行对比时而不是按照图中一组数据对比完再对比另一组数据，而是对比的数据是按照图中方式分组的。以上图为例，对比时是按照10与1对比，6与3对比，7与9对比的顺序逐渐向前对比的，而不是10与1对比，1与4对比的顺序

void ShellSort(int* a, int n)//希尔排序
{
	assert(a);
 
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//gap的值不断缩小，直到缩小到gap = 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.直接选择排序

（1）基本思想：

在元素集合array[i]~array[n - 1]中设置mini，为序列中的第一个元素下标，将该下标代表的值与序列后面的元素逐个对比，每遇到比tmin小的值就更新mini，直到遍历完整个序列，然后将该值放到序列的排列好的有序序列的下一个位置

 直接选择排序作为所有排序中最简单易解的排序，其效率也相应的很低，时间复杂度为O（N^2）,在实际中很少应用到

（2）时间、空间复杂度及稳定性

时间复杂度：O（N^2）。n个数每趟选一个最大或最小值，需要选n趟，时间复杂度O（N^2）

空间复杂度：O（1）。没有开辟额外的空间

稳定性：不稳定。直接选择排序看起来好像是稳定的，因为如果是选最小值时，遇到与min相等的数不更新就行了，但是这样只能保证min所表示的数的相对顺序不变，无法保证被交换的数的相对顺序不变，例如“8 9 8 5 5 ”这组数据，5的相对顺序不变，但是8的相对顺序被改变了

（3）代码实现

此处代码进行过一定的优化，因为遍历一遍序列既可以找到最小的值，也可以找到最大的值。

因此定义一个begin和end分别指向数组的头下标和尾下标，并定义mini和maxi分别表示最小值和最小值的下标，遍历序列，遇到大于a[maxi]的就更新maxi，遇到小于a[mini]的更新mini，遍历一遍后将a[mini]与放到序列前方，a[maxi]放到序列后面

此处要注意的是，优化过后需要注意maxi == begin的情况，在这种情况下，a[maxi]上的值会与a[mini]上的值交换，因此要提前将maxi置为mini

void SelectSort(int* a, int n)//直接选择排序
{
	assert(a);
 
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
 
		if (maxi == begin)
			maxi = mini;
 
		swap(&a[mini], &a[begin++]);
		swap(&a[maxi], &a[end--]);
	}
}

4.堆排序

（1）基本原理：

传入一组随机排序的数据，将其按照升序或降序的方式排序

要注意的是，在堆排序中，升序建大堆，降序建小堆。因为堆排序的逻辑是将堆顶的数据与堆尾的数据依次交换。这样，大堆排序后，堆尾的数据是最大的值并依次堆顶缩小；小堆排序后，堆尾的数据是最小的值并依次堆顶增大

 选数时，依次将堆顶与堆尾的数据相交换，如有10个数据，把最大或最小值放到下标为9的堆尾处，然后从堆顶向下调整堆。调整完后将堆顶的数据与下标为8的堆尾处交换，向下调整。直到堆尾的下标为0

（2）时间、空间复杂度及稳定性

时间复杂度：O（N * log(N)）。堆排序建堆的时间复杂度为O（N），但是选数时需要把每个数据都交换到堆顶，而堆的高度是log（N），建堆的时间复杂度可以忽略，因此为O（N * log(N)）

空间复杂度：O（1）。没有开辟额外的空间

稳定性：不稳定。建堆时数据的相对顺序就可能被改变，在选数时堆顶与堆尾数据交换也可能导致相对位置改变

（3）代码实现

void swap(int* left, int* right)
{
	int i = *left;
	*left = *right;
	*right = i;
}
 
void AdjustDown(int* a, int sz, int parent)
{
	assert(a);
 
	int minchild = parent * 2 + 1;
	int maxchild = parent * 2 + 2;
 
	if (sz <= 2)
	{
		minchild = 0;
		maxchild = 1;
	}
	while (minchild < sz)
	{
		if (maxchild < sz && a[minchild] > a[maxchild])
		{
			swap(&maxchild, &minchild);
		}
 
		if (a[parent] > a[minchild])
		{
			swap(&a[parent], &a[minchild]);
		}
 
		parent = minchild;
		minchild = parent * 2 + 1;
		maxchild = parent * 2 + 2;
	}
}
 
void HeapSort(int* a, int n)//堆排序
{
	assert(a);
 
	for (int parent = (n - 1 - 1) / 2; parent >= 0; --parent)
	{
		AdjustDown(a, n, parent);
	}
 
	int i = 1;
	while (i < n)
	{
		swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

5.冒泡排序

（1）基本原理

根据序列中两个记录值的比较结果来交换这两个记录在序列中的位置，一前一后两个下标的值进行比较，前一个值比后一个值大则交换

冒泡排序非常容易理解，每遍历一次就将最大值放到序列的尾部，遍历n次后将序列排序好，其时间复杂度为O（N）

（2）时间、空间复杂度及稳定性

时间复杂度：O（N ^2）。冒泡排序每次都要对比相邻的两个数对比n次，跑n躺，时间复杂度为O（N^2）

空间复杂度：O（1）。没有开辟额外的空间

稳定性：稳定。两两对比时如果是相同数据就不交换，相对位置不变

（3）代码实现

void BubbleSort(int* a, int n)//冒泡排序
{
	assert(a);
 
	for (int j = 0; j < n; ++j)
	{
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				swap(&a[i], &a[i - 1]);
			}
		}
	}
}

6.快速排序

（1）基本原理

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

快速排序的方法与二叉树的前序遍历极为相似，因此在一般情况下，是采用递归的方式构建二叉树的形式进行分解排序，但在某些极端情况下可能会出现栈溢出的，因此有时也会使用非递归的形式实现。

（2）时间、空间复杂度及稳定性

时间复杂度：O（N *log（N））。快排的三种方法都是运用了二叉树思想，不断分割数据进行排序

空间复杂度：O（log（N））。快速排序是采用递归的形式进行的，每次递归都会调用栈帧，调用的栈帧次数一般是log（N），函数的递归调用栈帧可以复用

稳定性：不稳定。快速排序的交换或覆盖都可能导致数据相对位置改变

（2）代码实现

在快速排序中，常见的有三种方法，分别是hoare法，挖坑法和前后指针法

因为快速排序法在某些极端情况下， 比如排逆序时的树的高度接近n。为了防止出现这类状况，一般会对快速排序的选key进行优化。快速排序的key一般是最左边的值或最右边的值，此处采用“三树取中法”，在最左边的值，最右边的值和中间的值三个值中选中位数，以此来选key，避免key为最大值或最小值的可能性

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

1.hoare法

该方法定义了一个left和right，分别指向序列最左边和最右边的值的下标，right先向左走，遇到比a[keyi]小的数就停下，然后left向右走，遇到比a[keyi]大的数就停下，交换a[left]和a[right]的值，不断重复这一过程，当left和right相遇时就将a[keyi]和la[left]的值交换，并把相遇的位置作为新的keyi。此时的a[keyi]就已经在序列排好序了。此时划分出[left, key - 1],key,[key + 1, right]三个区间，并对[left, key - 1]和[key + 1, right]不断重复上一步骤，直到所有的a[keyi]都排好序

代码实现

int PartSort1(int* a, int left, int right)//快速排序（hoare方式）
{
	int keyi = MidPower(a, left, right);
	swap(&a[keyi], &a[left]);
	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]);
	
	int meeti = left;
	return meeti;
}
void QuickSort(int* a, int begin, int end)//快速排序
{
	assert(a);
 
	if (begin >= end)
		return;
 
	int keyi = PartSort1(a, begin, end);
 
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

2.挖坑法

挖坑法和Hoare法差别不大，挖坑法同样是设置left和right两个下标分别指向最左和最右的数，不同的是挖坑法会先将left作为坑位，right先走，找比key小的值后，将a[hole]的值修改为a[right]，并将right看做坑位。然后left再走，找到比key大的值后将a[hole]的值修改为a[left]，两个值不断走直到相遇，相遇后将a[hole]的值修改为key。

代码实现

int PartSort2(int* a, int left, int right)//快速排序（挖坑法）
{
	int hole = MidPower(a, left, right);
	swap(&a[hole], &a[left]);
	hole = left;
	int key = a[hole];
 
	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;
}

3.前后指针法

该方法需要设置prev和cur两个变量分别存储序列最左边的下标和prev + 1的下标。两个变量一前一后，如果初始的a[cur] < key，那么就perv先走一步，然后cur再走一步，不断向前走，直到a[cur] > key。此时prev停下，a[cur]继续向前走，直到a[cur] < key，交换a[prev]和a[cur]的值。然后cur和prev同时继续往前走，重复上述过程。

代码实现

int PartSort3(int* a, int left, int right)
{
    assert(a);
    
    int keyi = MidPower(a, left, right);
    swap(&a[keyi], &a[left]);
    keyi = left;
    int prev = left;
    int cur = prev + 1;
 
    while(cur <= right && a[cur] < a[keyi])
    {
        ++prev;
        ++cur;
    }
 
    while(cur <= right)
    {
        while(cur <= right && a[cur] >= a[keyi])
        {
            ++cur;
        }
        if(cur <= right)
        {
            ++prev;
            swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    swap(&a[prev], &a[keyi]);
    return prev;
}
 
void QuickSort(int* a, int begin, int end)//快速排序
{
	assert(a);
 
	if (begin >= end)
		return;
 
	int keyi = PartSort3(a, begin, end);
 
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

上述的PartSort3部分的代码可以进行优化。因为该方法是prev先走，因此在cur和prev一起走时必然会导致cur == prev，而当a[cur] > a[keyi]后，cur和prev便不会再相等。利用这个条件，可以将代码优化成以下形式

int PartSort3(int* a, int left, int right)//快速排序（快慢指针法）
{
	int keyi = MidPower(a, left, right);
	swap(&a[keyi], &a[left]);
	keyi = left;
	int prev = left;
	int cur = prev + 1;
 
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			swap(&a[prev], &a[cur]);
 
		++cur;
	}
 
	swap(&a[keyi], &a[prev]);
	return prev;
}

4.快速排序的非递归

快速排序的本质是将一串序列划分成一个又一个的单独范围的数组，利用这个特点，可以使用栈的形式来写非递归

每次都将序列的左右边界传入，传入时因为栈的特性，要先传左边界，再传右边界，获取边界时则需要先取右边界，再取左边界。获取后要及时删除，避免影响获取栈的头节点数据

void QcickSortNonR(int* a, int begin, int end)//快速排序（非递归形式）
{
	assert(a);
 
	Stack ST;
	StackInit(&ST);
 
	StackPush(&ST, begin);
	StackPush(&ST, end);
 
	while (!StackEmpty(&ST))
	{
		int right = StackTop(&ST);
		StackPop(&ST);
		int left = StackTop(&ST);
		StackPop(&ST);
 
		if (left >= right)
			continue;
 
		int keyi = PartSort3(a, left, right);
 
		StackPush(&ST, keyi + 1);
		StackPush(&ST, right);
 
		StackPush(&ST, left);
		StackPush(&ST, keyi - 1);
	}
}

7.归并排序

（1）基本原理

归并排序同样也是运用了二叉树结构的思想。不同于快速排序一次排好一个数，归并是一次排好一组数。将一个序列从中间节点划分成两部分，每部分同样依次从中间划分，直到节点一组数据中只有一个数。此时该该数据视为有序，然后将每组数据两两合并，并将每组数数据都排成有序，不断向上返回，形式如下图所示

（2）时间、空间复杂度及稳定性

时间复杂度：O（N ^log（N））。归并排序也是采用了二叉树的思想。

空间复杂度：O（N）。开辟了一个额外的数组来存储数据

稳定性：稳定。以2的次方形式进行数据的变动，数据相同时先放入左边的数据即可保持稳定 

（3）代码实现

归并排序的实现需要借助一个额外的tmp空间放入排好序的值

在实现归并排序时，需要定义一个i = begin1来控制插入到tmp数组中的值。并且因为是两组数据对比，谁小谁放入tmp，因此必定会有一个数组的值没有放完，因此在一个组的数据插入完后，要再写循环将另一组的数据全部放到tmp中。

最后将tmp中的值拷贝回原数组，但并不需要全部拷贝，如果全部拷贝不仅浪费时间，还会使原数组中的值被修改。

在拷贝时，拷贝数组的起点也是有讲究的，以上图为例，4和8的下标为0和1，5和7的下标为2和3。当递归下来后，tmp[0] = 4.tmp[1] = 8。拷贝4和8的回原数组a[0]修改为4，a[1]修改为8。函数结束返回上一层，因为i = begin1，因此此时i = 2，向下走tmp[2] = 5,tmp[3] = 7，并拷贝回原数组。这样就可以使放入tmp数组和拷贝回原数组的数据始终保持一致，且在同一层的tmp数据不会被覆盖

1.递归形式

void PartMergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
 
	int mid = (left + right) / 2;
	PartMergeSort(a, left, mid, tmp);
	PartMergeSort(a, mid + 1, right, tmp);
 
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = begin1;
	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 + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* a, int n)//归并排序
{
	assert(a);
 
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	int begin = 0, end = n - 1;
	PartMergeSort(a, begin, end, tmp);
 
	free(tmp);
	tmp = NULL;
}

2.非递归形式

void MergeSortNonR(int* a, int n)//归并排序（非递归）
{
	assert(a);
 
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	int gap = 1;
	while (gap < n)
	{
		for (int j = 0; j < n; j += 2 * gap)
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
 
			if (end1 >= n)
			{
				break;
			}
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			
			int i = j;
			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 + j, tmp + j, (end2 - j + 1) * sizeof(int));
		}
		gap = 2 * gap;
	}
}

归并排序是从中间分开两两一组，直到把每组数据划分为只有一个后向上排序。因此非递归时我们可以直接将一组序列划分成单个数据的组，然后再两两一组合并排序。与递归不同的是，递归是以二叉树后序遍历的方式排序，非递归则采用从下至上的层序遍历的方式。

定义一个gap值，来划分每组之间的begin1和end2的位置。两两一组，当每组数据为1时，begin1 = 0， end2 = 1；当每组数据为2时，begin1 = 0，end2 = 3，数据个数呈2的次方增长。因此定义gap = 1，每次更新gap时gap = 2*gap。

在gap之下写一个循环来控制分组。要注意的是，因为两两一组，那么就要求数据个数必须是2的次方个，当数据个数为奇数或者不是2的次方时会造成越界。此时就需要对越界的组的范围进行修正

经试验，会有三种情况越界，第一种是end1越界，第二种是begin2越界，第三种则是end2越界。前两种越界都只会越到n的位置，而第三种越界则会越到离n稍远的位置。因此前两种的处理方式是直接break即可，第三种则将end2修改为n -1即可

8.计数排序

（1）基本原理

计数排序是一种非比较排序，主要思想是统计每个数出现的次数，以此为基础进行排序。那么统计出的数据次数放在哪里呢？这就需要新开辟一个数组来存储。而这个数组的开辟也是有讲究的。

数组空间的开辟数量一般是按照数据的最大值来开辟的，每个数据出现的次数就放在相应的下标下面。例如一组序列中数据的最大值是100，那么就开辟100个空间，其中的数据有个99，那么就在下标为99的位置+1，99再次出现，那么下标为99的位置存储的数据就继续+1。

但是这种方式会造成大量的空间浪费，例如一组序列的数据是在100~120之间，但是却需要开辟120个空间来存放这21个数据的出现次数，显然这样是不合理的。因此就对其进行了相应的优化

在优化后数组空间的开辟是按照整组序列的最大和最小值的差来开辟的，即n = a[max] - a[min] + 1，这里+1是因为数组下标是从0开始的，差值+1就是整个数组需要的空间。这样就只需要按照序列中数据的差值数来开辟空间，极大的减少了空间浪费

（2）时间、空间复杂度及稳定性

时间复杂度：O（N ）。计数排序的时间复杂度主要体现在选最大最小值，遍历数据记录统一数据出现次数和依次修改原序列数据上。三步的时间复杂度都是O（N），加起来是O（3N）,3可以忽略不计

空间复杂度：O（range）。开辟了一个range大小的数组空间

稳定性：不稳定。放回数据时无法保证谁先谁后，且本质上是修改原数组数据，而不是对原数组数据进行交换

（2）代码实现

实现时只需要四个步骤即可：算序列最大差值——>开辟数组空间——>统计同一数据出现次数并将次数放入到数组空间相应的位置——>按开辟的数组中的次数依次将数据放回原序列

void CountSort(int* a, int n)//计数排序
{
	assert(a);
 
	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* count = (int*)calloc(range, sizeof(int));//可以使用calloc函数，该函数会将开辟的空间初始化为0
	//int* count = (int*)malloc(sizeof(int) * range);也可以使用malloc函数，但要记得使用memset初始化数据
	/*memset(count, 0, sizeof(int));*/
	if (count == NULL)
	{
		perror("calloc fail");
		exit(-1);
	}
 
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}
 
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (count[i]--)
		{
			a[j++] = min + i;
		}
	}
}

要注意，这种排序方式只适合排整数，对于浮点数，字符串等都是无法排序的

同时，因为按照序列最大差值来开辟空间的，因此也比较适合数据相对集中的序列，如果像最小值是1，最大值是10000这种就不适合用计数排序