【数据结构】手撕八大排序算法

ゝ一纸荒年。 2024-03-30 17:12 19阅读 0赞

> 作者：一个喜欢猫咪的的程序员
> 
> 专栏：《数据结构》
> 
> **喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》**
> 
> **![e9d9d891852848a8b7c8add1996e8dd4.jpeg][]**
> 
> --------------------
> 
> **目录**
> 
>  1.排序的概念：
> 
>  2.八大排序的思路及其细节
> 
> 2.1直接插入排序
> 
> 2.2希尔排序
> 
> 2.3选择排序：
> 
> 2.4堆排序
> 
> 2.5冒泡排序
> 
> 2.6快速排序：
> 
> 2.6.1hoare版本（递归版本）
> 
> 2.6.2三数取中
> 
> 2.6.3挖坑法
> 
> 2.6.4前后指针法：
> 
> 2.6.5非递归写法：
> 
> 2.7归并排序
> 
> 2.7.1递归写法：
> 
> 2.7.2非递归写法：
> 
> 2.8计数排序
> 
> --------------------

![3c225f71929142be9637d0b96ecc99c4.gif][]

## 1.排序的概念： ##

**排序就是把集合中的元素按照一定的次序排序在一起**。一般来说有升序排列和降序排列2种排序，在算法中有八大基本排序：

![49025bc9938d4878ad798831b511d7b4.png][]

**算法的优良主要从4个方面进行评测：**

*  1.时间复杂度
 *  2.空间复杂度
 *  3.适用场景
 *  4.稳定性

## 2.八大排序的思路及其细节 ##

### 2.1直接插入排序 ###

动图演示：

![808fb41def7641bdaf36a4eac2966fa5.gif][]

当前n-1个已是有序的情况下，将第n个元素插入进去排序，插入到顺序正确的位置。

将此过程一直重复的话可以可以完成上图的情况。（以数组a为例，来观察一下各个过程）

int a[] = {9,1,2,5,7,4,8,6,3,5};

![e116e695c9854c1e98f39685372a6649.png][]

思路：

**用一个变量end=i，利用tmp记录下end位置的下一个位置a\[end+1\]的值，如果a\[end\]>tmp,a\[end\]=tmp然后end--。最后将tmp的值赋给end+1的位置。**

考虑极端情况：

当数组有n个数时，下标最大值为n-1

**当end=n-1时，end+1=n（此时造成了越界）**

void InsertSort(int* a, int n)
    {//插入排序
    	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;//防止end=-1
    	}
    }

**时间复杂度： O(N^2) 空间复杂度：O ( 1 )**

--------------------

### 2.2希尔排序 ###

对插入排序的时间复杂度进行分析，得出了以下结论：

*  ** 普通插入排序的时间复杂度最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序。**
 *  ** 普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序。**

动图演示：

![8c6da7ac6efe4ca5b61ffec2c25cd495.gif][]

待排序列先进行一次预排序，让待排序列变为接近有序的（接近需要的顺序）,然后再进行一次直接插入排序。

因为直接插入排序前的待排序列已是接近有序的情况了，因此时间复杂度为O（N），只要控制预排序阶段的时间复杂度不超过O(N^2)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。

![d648646919c34e1582b5f95405e0ae33.png][]

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

**设定一个gap=n/2，将相距gap位置的两个数作比较，如果前面的小于后面交换以此循环**

问题：为什么gap=n/2？  
answer：gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置）。

![5f596f95dbc942bc9eefbb813c822ef2.png][]

思路：

**单趟排序：当a\[end\]>a\[end+gap\]时，将end的值赋给end+gap后end-=gap，在end<0时退出循环**

**当有n个数时，因为比较是相距gap距离的两个数比较，因此循环次数要小于n-gap次**

**gap=n每次取半直到最终取到gap=1时，每次取半都是一次一次单趟排序**

![6c4a9bd9a9b540578f88e5e5587cc7ea.png][]

void ShellSort(int* a, int n)
    {
    	int gap = n;
    	while (gap > 1)
    	{
    		gap = gap/ 2;
    		for (int i = 0; i < n - gap; i++)//i++并排运算
    		{
    			int end = i;
    			int tmp = a[end + gap];
    			while (end >= 0)
    			{
    				if (a[end] > tmp)
    				{
    					//Swap(&a[end], &a[end + gap]);
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				     break;
    			}
    			a[end + gap] = tmp;//防止end<0
    		}
    	}
    }

**希尔排序详细的时间复杂度和空间复杂度：**

《数据结构(C语言版)》--- 严蔚敏

![57673520b2dc4c6b882f87bf0a8e427b.png][]

《数据结构-用面相对象方法与C++描述》--- 殷人昆

![34e9281e9f1b4665bb784ec2a988153e.png][]

**时间复杂度：O ( NlogN )   空间复杂度：O ( 1 )**

**平均时间复杂度：O ( N^ 1.3 )**

--------------------

### 2.3选择排序： ###

动图演示：

![5ea30ba5d2844795a9f66f3a4ee01078.gif][]

思路：

**设两个下标begin和end，begin初始化为0，end初始化为n-1**

**设置最大值和最小值的下标让他们指向begin**

**当a\[i\]的值比a\[begin\]小，更新min的值，当a\[i\]的值比a\[begin\]大，更新max的值**

**循环走完后确认了最小值的下标，将a\[begin\]和a\[min\]进行交换，以及a\[end\]和a\[max交换\]**

极端情况：

当最大值为数组的第一个时，max=min

**时间复杂度：O(N^2) 空间复杂度：O(1)**

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

--------------------

### 2.4堆排序 ###

堆排序：（以小堆为例）  
堆的分类：

**1.升序or降序  
2.大堆or小堆**

void test2()
    {//堆排序
    	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
    	Heapsort(array, sizeof(array) / sizeof(array[0]));
    	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
    	{
    		printf("%d ", array[i]);
    	}
    	printf("\n");
     
    }

Heapsort函数（堆排序）：  
i**nt array\[\] = \{ 27,15,19,18,28,34,65,49,25,37 \};**

需将这个数组进行大堆排列，分为两种调整形式：向上调整和向下调整。

向上调整和向下调整的思想可以参考我的例外一篇博客：[http://t.csdn.cn/UD52X][http_t.csdn.cn_UD52X]

void Ajustup(HPDataType*a, int child)
    {//N*logN
        assert(a);
        //int child = n - 1;
        while (child > 0)
        {
            int parent = (child - 1) / 2;
            if (a[child] > a[parent])
            {
                Swap(&a[child], &a[parent]);
                child = parent;
            }
            else
            {
                break;
            }
        }
    }
    void Ajustdown(HPDataType* a, int n,int parent)
    {//O(N)
        assert(a);
        int child = 2 * parent+1;
        while (child<n)
        {
            if (child + 1 < n && a[child] < a[child + 1])//  <假设左子树大
            {
                child++;
            }
            if (a[child] > a[parent])//>大堆，<为小堆
            {
                Swap(&a[child], &a[parent]);
                parent = child;
                child = child * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }

向上调整和向下调整具体的时间复杂度是多少呢？

向下调整具体的时间复杂度：

> **假设树高为h**
> 
> **第h层，有2^(h-1）个节点，需要向下调整0次（直接不算，从第h-1层开始算）。**
> 
> **第h-1层，有2^（h-2）个节点，需要向下调整1层。**
> 
> **第h-2层，有2^（h-3）个节点，需要向下调整2层。**
> 
> **......**
> 
> **第4层，有2^3个节点，需要向下调整h-4层。**
> 
> **第3层，有2^2个节点，需要向下调整h-3层。**
> 
> **第2层，有2^1个节点，需要向下调整h-2层。**
> 
> **第1层，有2^0个节点，需要向下调整h-1层。**![005619af4b584ae884a80054c7400b68.gif][]

当h高的次数，最多调整层数为：

F（h）=2^0\*（h-1）+2^1\*(h-2)+2^2\*(h-3)+...+2^(h-3)\*2+2^(h-2)\*1+2^(h-1)\*0 ——①

2\*F（h）=2^1\*（h-1）+2^2\*(h-2)+2^3\*(h-3)+...+2^(h-2)\*2+2^(h-1)\*1+2^(h)\*0 ——②

有错位相减②-①可得：

F（h）=-2^0\*（h-1）+2^1+2^2+....+2^(h-2)+2^(h-1)

F（h）=2^h-1-h ——③

当树高为h时，节点总个数N为：

N=2^0+2^1+...+2^（h-2）+2^（h-1）

N=2^h-1 ——④

有④可得：h=log（N+1） ——⑤

综合③④⑤可得：

F（N）=N-log（N+1）

*   **因此时间复杂度为O（N）**

> **向上调整具体的时间复杂度：  
> 在一层，需要向上调整0次**
> 
> **第二层，向上调整1次**
> 
> **第三层，向上调整2次**
> 
> **...**
> 
> **第h-1层，向上调整h-2次**
> 
> **第h层，向上调整h-1次**
> 
> **F（h）=2^1\*1+2^2\*2+....+2^(h-1)\*(h-1)。**
> 
> **由错位相减可得：**
> 
> **F(N)=2N(1-log(N+1))。**

**时间复杂度为O（N\*logN）**  
如何实现堆排序  
**显然向下调整优于向上调整。**

先利用Ajustdown排序好数组，然后再用交换Ajustdown实现小堆。

void Heapsort(int*a,int n)//堆排序
    {//向上调整
    	for (int i = 1; i <n; i++)
    	{
    		Ajustup(a, i);
    	}
    	//向下调整
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		Ajustdown(a, n, i);
    	}
    	int end = n - 1;
    	while (end>0)
    	{
    		Swap(&a[0], &a[end]);
    		Ajustdown(a, end, 0);
    		end--;
    	}
    	//N*logN
    }
    void test2()
    {//堆排序
    	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
    	Heapsort(array, sizeof(array) / sizeof(array[0]));
    	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
    	{
    		printf("%d ", array[i]);
    	}
    	printf("\n");
     
    }

--------------------

### 2.5冒泡排序 ###

动图演示：

![d586f8aa6359477a90ba061ed432ea53.gif][]

代码：

void BubbleSort(int* a, int n)
    {
    	for (int j = 0; j < n; j++)
    	{
    		for (int i = 1; i < n - j; i++)
    		{
    			if (a[i] < a[i - 1])
    			{
    				Swap(&a[i],& a[i - 1]);
    			}
    		}
    	}
    }

**时间复杂度：O(N^2) 空间复杂度：O(1)**

--------------------

### 2.6快速排序： ###

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

快速排序有三种写法：

**1.hoare版本**

**2.挖坑法**

**3.前后指针法**

以及优化：

**1.三数取中**

#### **2.6.1hoare版本（递归版本）** ####

动图演示：

![37da68d607ef4667ae92ef14dd46aa96.gif][]

hoare版本思路：

**单趟排序，key一般选最左边或者最右边**

**当key为最左边，右边找小，左边找大，然后交换继续，相遇停止，相遇的值跟key交换**

**当key为最右边相反**

**当左区间有序，右区间有序那整体就ok了，如果左右区间不有序，左右区间就是单趟的子问题**

**当区间只有一个值，就不排了，返回**

![91d38a7561c64208bb5c0aac6d08bf5a.png][]

**问题：为什么是key为最左边时，右边先走，最右边做key时，左边先走**

answer：左边做key，右边先走，可以保证相遇位置比key要小

此时有两种情况：

1.相遇，left是停着(一定>=key)，right向后走，相遇的位置是left的位置

2.相遇，right是停着（一定<=key），left向前走，相遇的位置是right的位置

单趟有两个意义

**1.分割出左右区间，左比key小，右比key大**

**2.key到了正确位置（排序后的最终位置）**

key以后不用变了，到了正确位置

![2aa04346cd8a4e8a813c1b0254b023ee.png][]

代码：

int Partsort1(int* a, int begin, int end)
    {//hoare版本
    	int mid = GetMidIndex(a, begin, end);
    	Swap(&a[mid], &a[begin]);
    	int left = begin;
    	int right = end;
    	int keyi = begin;
    	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[left], &a[keyi]);
    	keyi = left;
    	return keyi;
    }
    void QuickSort(int* a, int begin, int end)
    {
    	if (begin >= end)
    	{
    		return;
    	}
    	if (end-begin+1 < 10)
    	{
    		InsertSort(a + begin, end - begin + 1);
    	}
    	else
    	{
    		int keyi=Partsort1(a, begin, end);
    		//int keyi=Partsort2(a, begin, end);
    
    		//int keyi = Partsort3(a, begin, end);
    
    		QuickSort(a, begin, keyi - 1);
    		QuickSort(a, keyi + 1, end);
    	}
    }

时间复杂度:O(NlogN)

### 2.6.2三数取中 ###

每次排序都会将数组分为三个部分：

【left-key-1】【key】【keyi+1-right】

在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：

![1bb16386c96d4ccfa735b753ce5e32ca.png][]

若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。

但事实上可能会遇到极端情况：就是我们每次取到的都是最大值或者最小值，那么快排的时间复杂度达到最低O（N^2）

![81f431c734e4475ca6276f86384b94ef.png][]

可以看到，这种情况下，快速排序的时间复杂度退化为O(N^2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：  
 三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码：

int GetMidIndex(int* a, int begin, int end)
    {
    	int mid = (begin + end) / 2;
    	if (a[begin] < a[mid])
    	{
    		if (a[mid] < a[end])
    		{
    			return mid;
    		}
    		else if (a[begin] > a[end])//a[mid]>a[end]的前提下
    		{
    			return begin;
    		}
    		else//a[mid]>a[end]&&a[begin] < a[end]的前提下
    		{
    			return end;
    		}
    	}
    	else//a[begin] > a[mid]
    	{
    		if (a[end] < a[mid])
    		{
    			return mid;
    		}
    		else if (a[begin] > a[end])//a[end] > a[mid]
    		{
    			return end;
    		}
    		else//a[end] > a[mid]&&a[begin] < a[end]
    		{
    			return begin;
    		}
    	}
    }

#### 2.6.3挖坑法 ####

动图演示：

![3756b136044341fd907993b2119f5852.gif][]

思路：

**将一开始的left保存起来，然后左边 空出来一个坑，右边先走，右找大，然后将右边的值的数据填进去，找到的位为坑，左边找小将右边的坑填进去，最后一定会在坑的位置相遇**

代码：

int Partsort2(int* a, int begin, int end)
    {//挖坑法
    	int mid = GetMidIndex(a, begin, end);
    	Swap(&a[mid], &a[begin]);
    	int left = begin;
    	int right = end;
    	int keyi = a[left];
    	int hole = left;
    
    	while (left < right)
    	{
    		while (left < right && a[right] >= keyi)
    		{
    			right--;
    		}
    		a[hole] = a[right];
    		hole = right;
    		while (left < right && a[left] <= keyi)
    		{
    			left++;
    		}
    	    a[hole]=a[left];
    		hole = left;
    	}
    	a[hole] = keyi;
    	keyi = left;
    	return hole;
    }
    void QuickSort(int* a, int begin, int end)
    {
    	if (begin >= end)
    	{
    		return;
    	}
    	if (end-begin+1 < 10)
    	{
    		InsertSort(a + begin, end - begin + 1);
    	}
    	else
    	{
    		//int keyi=Partsort1(a, begin, end);
    		int keyi=Partsort2(a, begin, end);
    
    		//int keyi = Partsort3(a, begin, end);
    
    		QuickSort(a, begin, keyi - 1);
    		QuickSort(a, keyi + 1, end);
    	}
    }

**时间复杂度:O(NlogN)**

--------------------

#### 2.6.4前后指针法： ####

动图演示：

![b13441c709664a588c471a7f43bf0ec1.gif][]

思路：

**1、cur找比key小，找到后停下来  
2、++prev, 交换prev位置和cur位置的值**  
代码：

int Partsort3(int* a, int begin, int end)
    {
    	int  prev = begin;
    	int cur = begin + 1;
    	int keyi = begin;
    	while (cur<=end)
    	{
    		/*if (a[cur] < a[keyi])
    		{
    			Swap(&a[++prev], &a[cur]);
    		}*/
    		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;
    	}
    	if (end-begin+1 < 10)
    	{
    		InsertSort(a + begin, end - begin + 1);
    	}
    	else
    	{
    		/*int keyi=Partsort1(a, begin, end);
    		int keyi=Partsort2(a, begin, end);*/
    
    		int keyi = Partsort3(a, begin, end);
    
    		QuickSort(a, begin, keyi - 1);
    		QuickSort(a, keyi + 1, end);
    	}
    }

**时间复杂度:O(NlogN)**

--------------------

#### 2.6.5非递归写法： ####

思路：

**通过非递归的方式实现递归的情况的话，递归从底层是先排左边再排右边因此类推，因此写非递归我们从顶层到底层就需要反过来。**

**借助栈的内存结构让先入的后出，所以要先压begin再压end，取出来的话就是先出右再出左**

**再先排右边再排左边。**

代码：

void QuickSortNonR(int* a, int begin, int end)
    {//非递归
    	ST st;
    	StackInit(&st);
    	StackPush(&st, begin);
    	StackPush(&st, end);
    	while (!StackEmpty(&st))
    	{
    		int right = StackTop(&st);
    		StackPop(&st);
    		int left = StackTop(&st);
    		StackPop(&st);
    		int keyi = Partsort3(a, left, right);//单趟排序
    		if (keyi + 1 < right)
    		{
    			StackPush(&st, keyi+1);
    			StackPush(&st, right);
    		}
    		if (left < keyi-1)
    		{
    			StackPush(&st, left);
    			StackPush(&st, keyi - 1);
    		}
    	}
    	StackDestory(&st);
    }

--------------------

### 2.7归并排序 ###

#### 2.7.1递归写法： ####

动图讲解：

![5ac89977c025445097d54eacee055154.gif][]

思路：

**将两端有序序列取各种较小的值比较排序成一个有序序列。**

![9069e14decee4df2b38e7d80c2e46c07.png][]

![3632454b75f9435eafce933de25169ff.png][]

代码：

void _MergeSort(int* a, int begin, int end, int* tmp)
    {
    	if (begin >= end)
    	{
    		return;
    	}
    	int mid = (begin + end) / 2;
    	_MergeSort(a, mid+1, end, tmp);
    	_MergeSort(a, begin, mid, tmp);
    	int begin1 = begin;
    	int end1 = mid;
    	int begin2 = mid+1;
    	int 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);
    	if (tmp == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	_MergeSort(a, 0, n-1, tmp);
    	free(tmp);
    	tmp = NULL;
    }

#### 2.7.2非递归写法： ####

极端情况：

越界有三种情况

**1.end1越界 begin2越界end2越界**

![6611fc2ee4c34e5289e187f678e0f61b.png][]

**2.begin2越界end2越界**

![7c1fed8ca73842c89d7a09609c906559.png][]

**3.end2越界**

![84a0a3101d934ce1814212d5843e52aa.png][]

整体拷贝的话会有覆盖丢失

![2700152f42b245159a22392a77e682ea.png][]代码：

void MergeSortNonrR(int* a, int n)
    {
    	int* tmp = (int*)malloc(sizeof(int) * n);
    	if (tmp == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	int RangN = 1;
    	while (RangN < n)
    	{
    		for (int i = 0; i < n; i += 2 * RangN)
    		{
    			int begin1 = i;
    			int end1 = i + RangN - 1;
    			int begin2 = i + RangN;
    			int end2 = i + 2 * RangN - 1;
    			int j = i;
    			if (end1>=n)// 修正区间  ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝
    			{
    				end1 = n - 1;
    				begin2 = n;// 不存在区间
    				end2 = n - 1;
    			}
    			else if (begin2 >= n)
    			{
    				begin2 = n;
    				end2 = n - 1;
    			}
    			else 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));
    		}
    		RangN *= 2;
    	}
    	free(tmp);
    	tmp = NULL;
    }

**时间复杂度：O（NlogN） 空间复杂度：O（N）**

### 2.8计数排序 ###

思路：

![166972a8ac0949e89e43ae4f67541d31.png][]

**绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。  
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。**

代码：

void CountSort(int* a, int n)
    {
    	int min = a[0];
    	int max = 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* CoutA = (int*)calloc(range, sizeof(int));
    	if (CoutA == NULL)
    	{
    		perror("calloc fail");
    		exit(-1);
    	}
    	for (int i = 0; i < n; i++)
    	{
    		CoutA[a[i] - min]++;
    	}
    	int k = 0;
    	for (int i = 0; i < range; i++)
    	{
    		while (CoutA[i]--)
    		{
    			a[k++] = i + min;
    		}
    
    	}
    	free(CoutA);
    }

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

[e9d9d891852848a8b7c8add1996e8dd4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d4501016e03148a1a51a756ece4bb374.jpeg
[3c225f71929142be9637d0b96ecc99c4.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c3b5b8abb87e4abb88bbbd2f69f156a7.gif
[49025bc9938d4878ad798831b511d7b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/37dbfd6dddf845cbb79229d35652d38a.png
[808fb41def7641bdaf36a4eac2966fa5.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5f885c14da6e43ff8806b91f58169ff9.gif
[e116e695c9854c1e98f39685372a6649.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7b285ccc4eef447899e1d4a47bab98de.png
[8c6da7ac6efe4ca5b61ffec2c25cd495.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/413541c48cc347c5bf6e84fd5573326a.gif
[d648646919c34e1582b5f95405e0ae33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c3133d2ed8c34ee0b34b9dec51f7c8aa.png
[5f596f95dbc942bc9eefbb813c822ef2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/014315228e8b4139b12ba7bbeb8230ef.png
[6c4a9bd9a9b540578f88e5e5587cc7ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3da65d8b8a6f48eaa7b1adb156e835b3.png
[57673520b2dc4c6b882f87bf0a8e427b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6f7e9ab08a8d40af9e17a1c581bbb7b0.png
[34e9281e9f1b4665bb784ec2a988153e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0258adc14d164fbf970355f24c79e77d.png
[5ea30ba5d2844795a9f66f3a4ee01078.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bce326094d174ae493759b3eab713c68.gif
[http_t.csdn.cn_UD52X]: http://t.csdn.cn/UD52X
[005619af4b584ae884a80054c7400b68.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5a3dff34a15d41cd962e88cdabd5781b.gif
[d586f8aa6359477a90ba061ed432ea53.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2279e0d2e7ac405f94c58935d270512d.gif
[37da68d607ef4667ae92ef14dd46aa96.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a117f5bcee574feea80c8b4884eb41dc.gif
[91d38a7561c64208bb5c0aac6d08bf5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fa7ac8759f864a16bce8c7b71acf70f5.png
[2aa04346cd8a4e8a813c1b0254b023ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3d36b689d5454603a153a0a801827f4b.png
[1bb16386c96d4ccfa735b753ce5e32ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3fa62db54ebf4e66a5ba7f5f42a832ad.png
[81f431c734e4475ca6276f86384b94ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2491bffd9bf6407cb7e88bfc49d30cad.png
[3756b136044341fd907993b2119f5852.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/976e28cb785f43be8acd2d9d217f5f3f.gif
[b13441c709664a588c471a7f43bf0ec1.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/83423d6e1fcb4e609ff31a88afc482de.gif
[5ac89977c025445097d54eacee055154.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/598bad4a31144811bed8fd3fcabf26c2.gif
[9069e14decee4df2b38e7d80c2e46c07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8358038a679644709c8fe5c94378a6d2.png
[3632454b75f9435eafce933de25169ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7cc1cd37614f4dde8ec9f56ce1755a37.png
[6611fc2ee4c34e5289e187f678e0f61b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d7f1f49dc6404e3193dd47e538048a05.png
[7c1fed8ca73842c89d7a09609c906559.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fe0f54dfa6ec4fb690cb24b32cee900e.png
[84a0a3101d934ce1814212d5843e52aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/28c8721ea90c433c97eafcbc8ed3026e.png
[2700152f42b245159a22392a77e682ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/893c1d9c3dc848dea1a9903e4544cda1.png
[166972a8ac0949e89e43ae4f67541d31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8f93c78fd561427890670327e0e9073e.png