【数据结构】八大排序(二)

😛作者：日出等日落

📘 专栏：数据结构

在最黑暗的那段人生，是我自己把自己拉出深渊。没有那个人，我就做那个人。                                                                                                                                              ——中岛美嘉

😩快速排序：

Hoare版本(递归)：

基本思想：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，这个排序很重要

其基本思想为：

任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

(官方语言，接下来请看详细解释)

动图演示：

基本思路： 

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

★首先令key为最左边，右边先走找小，然后左边找大，然后交换位置继续，相遇则停止，相遇的值跟key对应的值交换

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

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

代码展示： 

//快速排序
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int keyi = left;
	while (left = a[keyi])
		{
			right--;
		}
		//左边找大
		while (left  a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	// a[begin] > a[mid]
	else
	{
		//a[mid] > a[end]
		if (a[mid] > a[end])
		{
			return mid;
		}
		//a[mid]  
完整快速排序代码：
 
//Hoare 版本
int PartSort1(int* a , int begin , int end)
{
	int mid = GetmidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);
	int left = begin;
	int right = end;
	int keyi = left;
	while (left = a[keyi])
		{
			right--;
		}
		//左边找大
		while (left  
 
挖坑法：
 
基本思想：
 
 
 
挖坑法的思想很简单：
 
 
一开始先将left下标对应的值保存起来，然后left位置空出来的位置就是一个坑位，右边先走，找大，找到后将右边的值的数据填进去，这个right的位置就是新的坑，左边找小，再将左边找到的填进坑位，这个left对应下标的位置就是新的坑位，最后left和right一定会在坑的位置相遇
 
 
 
  
 
代码展示： 
 
//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = GetmidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);
	int left = begin;
	int right = end;
	int key = a[left];
	int hole = left;
	while (left = key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		//左边找大于key的;
		while (left  
前后指针法：
 
 
 
动图演示:
 
 
 
  
 
基本思路：
 
 
 
1、cur下标对应的值找比key小的，找到后停下来
2、然后++prev, 交换prev位置和cur位置的值
 
 
最后重复上述操作
 
  
  
 
时间复杂度:O(NlogN) 
 
 
 
//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur