数据结构知识点总结--排序

冷不防 2022-05-30 03:24 308阅读 0赞

\#数据结构知识点总结–排序  
主要是结合代码和动图总结  
目录：

## 文章目录  @\[toc\] ##

\#\#插入排序  
均以排升序进行解释

\#\#\#直接插入排序

1.先用动图演示一次插入，以在数组\{1，3，4\}中插入2为例：  
文字描述：

> ①找到数组末尾，用指针end标记  
> ②2与末尾元素4进行对比，2 < 4，插入  
> ③2与前一个元素3进行对比，2 < 3，插入  
> ④2与前一个元素1进行对比，2 > 1，停止

![这里写图片描述][70]  
2.下面动图演示使用插入法进行排序，以数组\{2，4，3，1\}为例进行排序  
文字描述：

> ①先将第一个元素视作一个数组，再将第二个元素视作待插入元素，进行一次插入；  
> ②一次插入完成后，前两个元素便是有序的，将前两个元素视作一个数组，再将第三个元素视作待插入元素，进行一次插入；  
> ③又一次插入完成后，前三个元素便是有序的，将前三个元素视作一个数组，再将第四个元素视作待插入元素，进行一次插入；  
> ④以此类推，直到将最后一个元素进行一次插入，排序完成。  
> ![这里写图片描述][70 1]

代码如下：

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

\#\#\#希尔排序  
是直接插入排序的一种优化，**先进行预排序再进行直接插入排序**

1.先用动图演示希尔排序的过程，以最坏情况：逆序 为例进行演示  
文字描述：

> ①先将数组分成多个小的数组，图中是每隔两个元素选取一个  
> ②对每个小数组分别进行直接插入排序，整个数组的顺序重新排序后会变得更接近有序  
> ③再对整个数组进行直接插入排序，就可以得到升序的数组  
> ![这里写图片描述][70 2]

2.再来解释希尔排序的好处，仍以上图数据为例

![这里写图片描述][70 3]  
![这里写图片描述][70 4]

void ShellSort(int* a, size_t n)//希尔排序
    {
    	assert(a != NULL);
    
    	//预排序
    	int gap = n / 3 + 1;//希尔排序所需要的跨度
    	while (gap > 1)
    	{
    		for (int i = 0; i < n - gap; ++i)
    		{
    			int end = i;
    			while (end >= 0)
    			{
    				if (a[end] > a[end + gap])
    				{
    					Swap(&a[end], &a[end + gap]);
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    		}
    		gap = gap / 3 + 1;
    	}
    	//直接插入排序
    	InsertSort(a, n);
    }

<table> 
 <thead> 
  <tr> 
   <th>对比</th> 
   <th>直插排序</th> 
   <th>希尔排序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>时间复杂度</td> 
   <td>最好情况O（n）;最坏情况O（n^2）</td> 
   <td>大约在O（n<sup>1.25）~O(1.6n</sup>1.25)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O（1）</td> 
   <td>O（1）</td> 
  </tr> 
 </tbody> 
</table>

\#\#选择排序

\#\#\#选择排序  
1.最简单的选择排序  
文字描述：

> ①每次遍历选取最小（大）的数，然后与最左（右）边的元素交换位置  
> ②再将从下一个元素开始遍历选取剩下元素中最小（大）的数，然后与最左（右）边的元素交换位置  
> ③重复以上步骤直到剩下最后一个元素。  
> ![这里写图片描述][70 5]

代码如下：

void SelectSort(int* a,size_t n)//选择排序
    {
    	assert(a != NULL);
    	
    	for (int i = 0; i < n; i++)
    	{
    		int min = i;
    		for (int j = i+1; j < n; j++)
    		{
    			if (a[min] > a[j])
    			{
    				min = j;
    			}
    		}
    		Swap(&a[min], &a[i]);
    	}
    }

2.优化的选择排序  
文字描述：

> 每次遍历要选取出当前数组中最大和最小的数，采用两个指针，从最左和最右同时开始排序

代码如下：

void SelectSort(int* a, size_t n)//选择排序
    {
    	assert(a != NULL);
    
    	int left = 0;
    	int right = n - 1;
    	while (left < right)
    	{
    		int min = left;
    		int max = left;
    		for (int i = left; i <= right;i++)
    		{
    			if (a[min] > a[i])
    			{
    				min = i;
    			}
    			if (a[max] < a[i])
    			{
    				max = i;
    			}
    		}
    		Swap(&a[left],&a[min]);
    		if (left != max)
    		//防止出现max在最左，min在最右，min与left交换后,max的值被改变的情况
    		{
    			Swap(&a[right],&a[max]);
    		}
    		left++;
    		right--;
    	}
    }

\#\#\#堆排序

1.先将数组建堆，如果要**排升序，就建大堆；排降序，就建小堆**  
文字说明：

> ①先找到第一个非叶子结点，下标为(n-2)/2;  
> ②找出该结点中左右孩子中较大的值，与之交换；  
> ③交换完毕后，下标减一，即找第二个非叶子结点，重复以上操作  
> ④直到找到根结点，建堆完毕  
> ![这里写图片描述][70 6]

2.建堆完毕后，使用替换法进行排序  
文字说明：

> ①先将建大堆之后的首尾交换，则最大的数在最末尾，将末尾向前移动一个位置  
> ②再从首到尾进行建大堆，找出数组中第二大的数，再进行首尾交换，再将末尾向前移动一个位置  
> ③重复以上操作，直到找到根结点，排序完毕。  
> ![这里写图片描述][70 7]

void AdjustDown(DataType* a, size_t n, int root)//建大堆
    {
    	int parent = root;
    	int child = parent * 2 + 1;
    
    	while (child < n)
    	{
    		if ((child+1)<n && a[child] < a[child+1])
    		{
    			child++;
    		}
    		if (a[parent] < a[child])
    		{
    			DataType tmp = a[parent];
    			a[parent] = a[child];
    			a[child] = tmp;
    
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    void MakeHeap(DataType* a, size_t n)//建堆
    {
    	int i = (n - 1) >> 1;
    	for (; i >= 0; --i)
    	{
    		AdjustDown(a,n,i);
    	}
    }
    
    void HeapSort(DataType* a, size_t n)
    {
    	MakeHeap(a,n);
    	int end = n-1;
    	while (end > 0)
    	{
    		DataType tmp = a[end];
    		a[end] = a[0];
    		a[0] = tmp;
    		AdjustDown(a,end,0);
    		end--;
    	}
    }

<table> 
 <thead> 
  <tr> 
   <th>对比</th> 
   <th>选择排序</th> 
   <th>堆排序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>时间复杂度</td> 
   <td>O（n^2）</td> 
   <td>O(n*log n）</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O（1）</td> 
   <td>O（1）</td> 
  </tr> 
 </tbody> 
</table>

\#\#交换排序

\#\#\#冒泡排序  
冒泡排序比较简单，直接上代码：

void Bubble(DataType* a,size_t n)
    {
    	assert(a != NULL && n > 0);
    	for(int end = n;end > 0;--end)
    	{
    		int flag = 0;
    		for(int i = 1;i < end;++i)
    		{
    			if(a[i-1] > a[i])
    			{
    				Swap(&a[i-1],&a[i]);
    				flag=1;
    			}
    		}
    		if(flag == 0)
    		{
    			break;
    		}
    	}	
    }

\#\#\#快速排序  
\#\#\#\#快排的三种方法  
1.左右指针法

> 文字描述：  
> ①首先选取数组最右（或最左）的元素为key，下标begin=left；end=right；  
> ②begin从左往右寻找比key大的元素，找到就停下来；end从右往左寻找比key小的元素，找到就停下来；然后交换下标begin和end对应的元素  
> ③重复 ① 和 ② 步骤，直到不再满足begin < end  
> ④将下标begin对应的元素与数组最右边的元素交换，**注意：不是和key交换，key只是保存最右元素的值的临时变量**  
> ![这里写图片描述][70 8]  
> ⑤至此，**最右元素一定被交换到了属于自己顺序序号的位置**，而其左右两边可看作被分成两个新的数组，即划分子问题，进行递归，递归停止条件是**left >= right**，即只有一个元素  
> ![这里写图片描述][SouthEast]  
> 代码如下：

int LeftRightPointer(int* a,int left,int right)//左右指针快排
    {
    	int begin = left;
    	int end = right;
    	
    	//选key的优化
    	int mid = Mid(a, left, right);
    	Swap(&a[mid], &a[right]);
    
    	int key = a[right];
    	while (begin < end)
    	{
    		while (begin < end && a[begin] <= key)
    		{
    			begin++;
    		}
    		while (begin < end && a[end] >= key)
    		{
    			end--;
    		}
    		Swap(&a[begin], &a[end]);
    	}
    	Swap(&a[begin], &a[right]);
    	return begin;
    }
    
    void QuickSort(int* a,int left,int right)//快排
    {
    	assert(a != NULL);
    
    	if (left >= right)
    	{
    		return;
    	}
    
    	int div = LeftRightPointer(a, left, right);
    	QuickSort(a, left, div - 1);
    	QuickSort(a, div + 1, right);
    }

2.挖坑法  
文字描述：

> ①与左右指针法类似，稍微有点区别的是挖坑法需要一个额外的下标index记录位置  
> ②不再是a\[begin\]和a\[end\]交换,而是a\[index\]=a\[begin\];index=begin;以及a\[index\]=a\[end\];index=end;  
> ③其他部分基本没什么变化

代码如下：

int Digging(int* a, int left, int right)//挖坑快排
    {
    	int begin = left;
    	int end = right;
    	int key = a[right];
    	int index = right;
    	while (begin < end)
    	{
    		while (begin < end && a[begin] <= key)
    		{
    			begin++;
    		}
    		a[index] = a[begin];
    		index = begin;
    
    		while (begin < end && a[end] >= key)
    		{
    			end--;
    		}
    		a[index] = a[end];
    		index = end;
    	}
    	a[index] = key;
    	return index;
    }
    
    void QuickSort(int* a,int left,int right)//快排
    {
    	assert(a != NULL);
    
    	if (left >= right)
    	{
    		return;
    	}
    
    	int div = Digging(a, left, right);
    	QuickSort(a, left, div - 1);
    	QuickSort(a, div + 1, right);
    }

3.前后指针法  
文字描述：

> ①与上两种算法思路也类似，区别在于不再是从两端向中间出发，而是定义两个指针，int prev=left;int post=prev-1;  
> ②主要算法：  
> 1.a\[prev\] < key,prev停下来，post++，如果prev != post，则交换两位置的数值；  
> 2.a\[prev\] >= key，prev++  
> ③其他部分基本没什么变化

代码如下：

int PrevPostPointer(int* a, int left, int right)//前后指针法
    {
    	int prev = left;
    	int post = prev - 1;
    	int key = a[right];
    	while (prev < right)
    	{
    		if (a[prev] < key)
    		{
    			post++;
    			if (post != prev)
    			{
    				Swap(&a[post], &a[prev]);
    			}
    		}
    		prev++;
    	}
    	post++;
    	Swap(&a[prev], &a[post]);
    	return post;
    }
    
    void QuickSort(int* a,int left,int right)//快排
    {
    	assert(a != NULL);
    
    	if (left >= right)
    	{
    		return;
    	}
    	
    	int div = PrevPostPointer(a, left, right);
    	QuickSort(a, left, div - 1);
    	QuickSort(a, div + 1, right);
    }

\#\#\#\#快排的优化  
快排只有进行优化之后才能达到O（n\*log n ）的时间复杂度

1.选key的优化

> 以排升序为例，如果当前顺序比较接近降序，即最小的值在最右边，如数组\{7，8，5，4，2，3，1，0\}，对它进行划分子问题时，很容易出现数据集中在右边，而左边要么没有元素或者只有一个元素的情况，这样的话效率就会变低，因此为了防止这种情况出现，进行选key的优化。

方法：三数取中法

> 取数组最左、最右和中间三个数，再取这三个数中的第二小的数，即中间值，作为key；这样最起码能保证，就算是最坏的情况，取到的也是整个数组中第二小的数值。

代码如下：

//以左右指针法为例
    int Mid(int* a,int left,int right)//三数取中,返回中间值的下标
    {
    	int mid = left + ((right - left) >> 1);
    	if (a[left] > a[right])
    	{
    		if (a[left] < a[mid])
    		{
    			return left;
    		}
    		else if (a[right] < a[mid])
    		{
    			return mid;
    		}
    		else
    		{
    			return right;
    		}
    	}
    	else//a[left] <= a[right]
    	{
    		if (a[right] < a[mid])
    		{
    			return right;
    		}
    		else if (a[left] < a[mid])
    		{
    			return mid;
    		}
    		else
    		{
    			return left;
    		}
    	}
    }
    
    int LeftRightPointer(int* a,int left,int right)//左右指针快排
    {
    	int begin = left;
    	int end = right;
    	
    	//选key的优化
    	int mid = Mid(a, left, right);
    	Swap(&a[mid], &a[right]);
    
    	int key = a[right];
    	while (begin < end)
    	{
    		while (begin < end && a[begin] <= key)
    		{
    			begin++;
    		}
    		while (begin < end && a[end] >= key)
    		{
    			end--;
    		}
    		Swap(&a[begin], &a[end]);
    	}
    	Swap(&a[begin], &a[right]);
    	return begin;
    }

2.小区间优化

> 当数组的区间比较小的时候，如果还用快排的话，效率反而不高，因为有栈帧的消耗会降低效率，因此当区间达到一定范围的时候，换成别的效率高的排序算法会更高效一些

代码如下：

void QuickSort(int* a,int left,int right)//快排
    {
    	assert(a != NULL);
    
    	if (left >= right)
    	{
    		return;
    	}
    
    	//小区间优化
    	if (right - left > 10)//当数组区间大于10时，使用快排
    	{
    		//int div = LeftRightPointer(a, left, right);
    		//int div = Digging(a, left, right);
    		int div = PrevPostPointer(a, left, right);
    		QuickSort(a, left, div - 1);
    		QuickSort(a, div + 1, right);
    	}
    	else//小于10时，使用直插排序
    	{
    		InsertSort(a, right - left + 1);
    	}
    }

\#\#\#\#非递归的快排

> 使用栈来存储下标

代码如下：

void QuickSortNR(int* a, int left, int right)//快排，非递归
    {
    	assert(a != NULL);
    	Stack s;
    	StackInit(&s);
    	StackPush(&s, left);
    	StackPush(&s, right);
    	while (StackEmpty(&s) != 0)//栈不为空
    	{
    		int end = StackTop(&s);
    		StackPop(&s);
    		int begin = StackTop(&s);
    		StackPop(&s);
    
    		//int div = LeftRightPointer(a, begin, end);
    		//int div = Digging(a, begin, end);
    		int div = PrevPostPointer(a, begin, end);
    
    		if (begin < div-1)
    		{
    			StackPush(&s, begin);
    			StackPush(&s, div - 1);
    		}
    		if (end > div + 1)
    		{
    			StackPush(&s, div + 1);
    			StackPush(&s, end);
    		}
    	}
    }

\#\#归并排序  
文字描述：

> ①与快速排序类似，但是归并排序不使用key，而是将数组进行递归二分  
> ②当二分为只剩下两个或一个元素的时候，比较大小排序  
> ③递归回溯时，将数组两两进行合并，并且合并后保持有序  
> ④回溯完毕后，整个数组就有序了  
> **注意：和“单链表的合并”不同的是，归并排序是对数组进行操纵，因此需要额外创建一个数组保存数据**  
> 如图：  
> 1.递归二分  
> ![这里写图片描述][SouthEast 1]  
> 2.排序后回溯  
> ![这里写图片描述][SouthEast 2]  
> 3.回溯时进行合并，并保持合并后的数组依然有序  
> ![这里写图片描述][SouthEast 3]  
> 4.递归回溯完毕后，整个数组有序  
> ![这里写图片描述][SouthEast 4]  
> \#\#计数排序  
> 文字描述：  
> 原理跟哈希表的K-V模型比较相似  
> ①遍历一遍数组，得出数组的范围range，创建一个大小为range的数组，即哈希表，初始化为全0  
> ②再从头开始遍历数组，数字重复出现一次，在其相应的位置对应的数值加一  
> ③从左到右开始遍历哈希表，将数值不为0的位置的下标存储到原数组中，且数值是多少就存储多少个  
> ![这里写图片描述][SouthEast 5]

\#对比

<table> 
 <thead> 
  <tr> 
   <th>排序</th> 
   <th>直插排序</th> 
   <th>选择排序</th> 
   <th>堆排序</th> 
   <th>冒泡排序</th> 
   <th>快速排序</th> 
   <th>归并排序</th> 
   <th>计数排序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>时间复杂度</td> 
   <td>最好O(n)最坏O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n*log n)</td> 
   <td>O(n^2)</td> 
   <td>优化后O(n*log n)</td> 
   <td>O(n*log n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>递归O(1)非递归O(n)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>优缺点</td> 
   <td>越接近有序越快</td> 
   <td>效率最低，唯一的优点是直观</td> 
   <td>所有排序方式中“整体”而言最快</td> 
   <td>效率不是很快</td> 
   <td>效率快，难理解</td> 
   <td>最稳定，但需要额外空间</td> 
   <td>只适合范围比较聚集的数据</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>稳定</td> 
   <td>不稳定</td> 
   <td>不稳定</td> 
   <td>稳定</td> 
   <td>不稳定</td> 
   <td>稳定</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

[70]: /images/20220530/f9fa583605f740beaeac0e2ab0314a85.png
[70 1]: /images/20220530/d43b38593f79433397a1d16edea968fd.png
[70 2]: /images/20220530/d1702f26d0a047afa00b0e322c2f1ab7.png
[70 3]: /images/20220530/24188aa2f39a4eea88308955aaed62a9.png
[70 4]: /images/20220530/b93d0327c75f45b888f748fc2c5e07c7.png
[70 5]: /images/20220530/8637c8b5cffc471399f38309e176ac7f.png
[70 6]: /images/20220530/6883bcad160245929f32e99fca522e77.png
[70 7]: /images/20220530/f7aae43798774e97b0bb2c46eb79a58f.png
[70 8]: /images/20220530/083ed84f064048d0b8b497bef2eed3e2.png
[SouthEast]: /images/20220530/c231e50557834bffadcc08e2419369d2.png
[SouthEast 1]: /images/20220530/ca113b0b14cc4794a3b75aaeeae4a587.png
[SouthEast 2]: /images/20220530/7b41e789723545bcadcf9035613ae5c6.png
[SouthEast 3]: /images/20220530/4db4a33cb5ac4fc39030846c11eaa957.png
[SouthEast 4]: /images/20220530/b81a3ff0c1c44f7999c995af0adaec66.png
[SouthEast 5]: /images/20220530/a300fc390ac04f5c8c009df62ee79f48.png