排序算法之快速排序

矫情吗；* 2023-07-03 04:53 4阅读 0赞

## 快速排序 ##

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置为止。  
将区间按照基准值划分为左右两半部分的常见方式有：  
1、hoare版本  
2、挖坑法  
3、前后指针法

## Hoare版本 ##

基准值的选择：一般情况下我们会选择待排序序列的最后一个元素或第一个元素作为基准值。但是，若待排序序列的最后一个元素是最值或者接近于最值的情况，就会使排序后的左右序列元素个数相差巨大，效率降低。所以我们一般采用三数取中法，找出序列开始结点、序列之间结点、序列最后结点的中间值作为基准值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]

//三数取中选key法
    int GetMidKey(int* a, int begin, int end)
    { 
    	int mid = begin + ((end - begin) >> 1);
    	if (a[begin] < a[mid])
    	{ 
    		if (a[mid] < a[end])
    			return mid;
    		else if (a[begin] < a[end])
    			return end;
    		else
    			return begin;
    	}
    	else
    	{ 
    		if (a[mid] > a[end])
    			return mid;
    		else if (a[end] < a[begin])
    			return end;
    		else
    			return begin;
    	}
    }
    
    int PartSort(int* a, int begin, int end)
    { 
    	int key = GetMidKey(a, begin, end);
    	Swap(&a[begin], &a[key]);
    	key = begin;
    	while (begin < end)
    	{ 
    		while (a[end] >= a[key] && begin < end)
    			end--;
    		while (a[begin] <= a[key] && begin < end)
    			begin++;
    		Swap(&a[begin], &a[end]);
    	}
    	Swap(&a[end], &a[key]);
    	return end;
    }
    
    void QuickSort(int* a, int left, int right)
    { 
    	if (left >= right)
    		return;
    	int div = PartSort(a, left, right);
    	QuickSort(a, left, div - 1);
    	QuickSort(a, div + 1, right);
    }

## 挖坑法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 1]  
代码如下：

int PartSort(int* a, int begin, int end)
    { 
    	int tmp = a[begin];
    	while (begin < end)
    	{ 
    		while (begin < end && a[end] >= tmp)
    		{ 
    			end--;
    		}
    		a[begin] = a[end];
    		while (begin < end && a[begin] <= tmp)
    		{ 
    			begin++;
    		}
    		a[end] = a[begin];
    	}
    	a[begin] = tmp;
    	return begin;
    }
    
    void QuickSort(int* a, int left, int right)
    { 
    	if (left >= right)
    		return;
    	int div = PartSort(a, left, right);
    	QuickSort(a, left, div - 1);
    	QuickSort(a, div + 1, right);
    }

## 前后指针法 ##

int PartSort(int* a, int begin, int end)
    { 
    	int prev = begin;
    	int cur = begin + 1;
    	while (cur <= end)
    	{ 
    		if (a[cur] < a[begin] && ++prev != cur)
    			Swap(&a[cur], &a[prev]);
    		++cur;
    	}
    	Swap(&a[begin], &a[prev]);
    	return prev;
    }
    
    void QuickSort(int* a, int left, int right)
    { 
    	if (left >= right)
    		return;
    	int div = PartSort4(a, left, right);
    	QuickSort4(a, left, div - 1);
    	QuickSort4(a, div + 1, right);
    }

## 快速排序非递归 ##

int PartSort(int* a, int begin, int end)
    { 
    	int key = begin;
    	while (begin < end)
    	{ 
    		while (a[end] >= a[key] && begin < end)
    			end--;
    		while (a[begin] <= a[key] && begin < end)
    			begin++;
    		Swap(&a[begin], &a[end]);
    	}
    	Swap(&a[end], &a[key]);
    	return end;
    }
    
    void QuickSortNonP(int* a, int left, int right)
    { 
    	Stack st;
    	StackInit(&st);
    	StackPush(&st, right);
    	StackPush(&st, left);
    	while (StackEmpty(&st) != 0)
    	{ 
    		int begin = StackTop(&st);
    		StackPop(&st);
    		int end = StackTop(&st);
    		StackPop(&st);
    		int div = PartSort5(a, begin, end);
    		if (begin < div - 1)
    		{ 
    			StackPush(&st, div - 1);
    			StackPush(&st, begin);
    		}
    		if (div + 1 < end)
    		{ 
    			StackPush(&st, end);
    			StackPush(&st, div + 1);
    		}
    	}
    }

快速排序的特性总结：  
1、快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序  
2、时间复杂度：O(N\*logN)  
3、空间复杂度：O(logN)  
3、稳定性：不稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200202171007698.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200203150122141.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70