排序算法—快速排序-白红宇

排序算法—快速排序

阅读量：2230 次

发布时间：2019-05-09

本文共 8165 字，大约阅读时间需要 27 分钟。

1. 快速排序的算法思想

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

2. 快速排序的三种基本方法（递归实现）

hoare法（又称作左右指针法）

定义两个指针begin和end，其初值分别为待排序区间左端点、右端点，begin从左往右走，寻找比基准值大的元素，end从右往左走，寻找比基准值小的元素。当begin停下时，说明此时的元素大于基准值；当end停下时，表明此时的元素小于基准值。此时交换对应的两个元素，继续上述过程。最后当begin和end相等时，交换其中一个元素和基准值，并返回基准值此时的下标。

总结两点：

① 实现升序时，基准值 key 如果在右边，则左边指针先动（左边找比基准值大的值，右边找比基准值小的值）；基准值 key 如果在左边，则右边指针先动（左边找比基准值大的值，右边找比基准值小的值）

② 实现降序时，基准值 key 如果在右边，则左边指针先动（左边找比基准值小的值，右边找比基准值大的值）；基准值 key 如果在左边，则右边指针先动（左边找比基准值小的值，右边找比基准值大的值）

以基准值在右边，数组{ 2, 9, 3, 6, 7, 5 }为例，图示如下：

走到这里时候，基准值 5 将数组分成两个区间，然后再重复以上操作就好，直到整个数组有序。具体代码实现如下：

int part_lrpoint_quick(int* arr,int left,int right)//左右指针法{
   	int key_index = Getmid_index(arr, left, right);	Swap(&arr[key_index], &arr[right]);	int key = arr[right];//key如果定在右边，则左边指针先动       	int right_index = right;	while (left < right)	{
   		while (left < right&&arr[left] <= key)//left
   
    = key)		{
   			right--;		}		//此时end所指向的元素比基准值小		Swap(&arr[left], &arr[right]);	}	              	Swap(&arr[left], &arr[right_index]);	return right;}

挖坑法

先将基准值保存起来，此时相当于基准值的位置就空出来了。然后定义两个指针begin和end，其初始值分别为待排序区间的左端点和右端点，begin寻找比基准值大的元素，end寻找比基准值小的元素。当begin找到比基准值大的元素之后，此时将其赋给end所指位置，那么begin所指位置便又空出来了；当end找到比基准值小的元素之后，此时将其赋给begin所指位置，那么此时end所指位置又空出来了。重复上述过程，直到begin==end。此时将基准值赋给begin所指位置并返回下标begin。

以基准值在右边，数组{ 2, 9, 3, 6, 7, 5 }为例，图示如下：

走到这里时候，基准值 5 将数组分成两个区间，然后再重复以上操作就好，直到整个数组有序。具体代码实现如下：

int part_wakeng_quick(int* arr, int left, int right)//挖坑法{
   	int key = arr[right];	int right_index = right;	while (left < right)	{
   		while (left < right&&arr[left] <= key)//左边找大的，放右边的坑		{
   			left++;		}         arr[right] = arr[left];//填坑		while (left < right&&arr[right] >= key)//右边找小的，放在左边的坑		{
   			right--;		}		arr[left] = arr[right];//填坑	}	arr[left] = key;	return left;}

前后指针法

定义两个指针div和cur，初始值均为待排序区间的左端点，其中div所指位置之前表示比基准值小或等的元素，div和cur之间表示比基准值大的元素，cur之后表示待排序部分。在cur遍历整个待排序区域期间，如果cur所指元素小于div所指元素，则交换，此时div++。最后交换div所指元素和基准值，并返回基准值此时的下标。

以基准值在右边，数组{ 2, 9, 3, 6, 7, 5 }为例，图示如下：

走到这里时候，基准值 5 将数组分成两个区间，然后再重复以上操作就好，直到整个数组有序。具体代码实现如下：

int part_flpoint_quick(int* arr, int left, int right)//前后指针法 former / latter{
   	int cur = left;	int prev = left - 1;	int key = arr[right];	while (cur < right) //cur找比key小的元素再进行交换	{
   		if (arr[cur] < key && ++prev != cur)//prev紧贴着cur		{
   			Swap(&arr[cur], &arr[prev]);		}		cur++;	}	++prev;//这个条件不能丢	Swap(&arr[right], &arr[prev]);	return prev;}

快速排序在某种程度下还要进行优化才能体现出它的快：

①：三数取中法

思想：因为key的值最好每次都能把数组分成二分的两半，所以key的值最好是区域内比较居中的值，所以每次把区域内的首元素、尾元素、中间的元素做比较，选出不大不小的那个，然后把选出来的这个值，交换到数组的尾部，以便调整后它能回到数组中间的位置

代码实现：

int Getmid_index(int* arr, int left, int right)//三数取中法(快速排序的优化){
   	int mid = left + (right - left) / 2;	if (arr[left] < arr[right])	{
   		if (arr[right] < arr[mid])		{
   			return right;		}		else if (arr[left] < arr[mid])		{
   			return mid;		}		else			return left;	}	//arr[left] > arr[right]	else	{
   		if (arr[left]

②：递归到小的子区间时，可以考虑使用插入排序，一般到元素个数小于 10 个时，考虑使用插入排序算法，代码实现：

void Insert_Sort(int* arr, int n){
   	int i = 0;	for (i = 0; i < n - 1; i++)	{
   		if (arr[i + 1] < arr[i])//找到比前一个数相比较小的当前数		{
   			int tmp = arr[i + 1];//先把当前数保存下来			int j = i;//用J来记录当前数前一个数的下标			for (j; tmp < arr[j] && j >= 0; j--)			{
   				if (tmp < arr[j])				{
   					arr[j + 1] = arr[j];				}			}			arr[j + 1] = tmp;		}	}}

左右指针法通过优化后的代码实现

int Getmid_index(int* arr, int left, int right)//三数取中法(快速排序的优化){
   	int mid = left + (right - left) / 2;	if (arr[left] < arr[right])	{
   		if (arr[right] < arr[mid])		{
   			return right;		}		else if (arr[left] < arr[mid])		{
   			return mid;		}		else			return left;	}	//arr[left] > arr[right]	else	{
   		if (arr[left]
   
    = key)		{
   			right--;		}		//此时end所指向的元素比基准值小		Swap(&arr[left], &arr[right]);	}	              	Swap(&arr[left], &arr[right_index]);	return left;}void quick_Sort1(int* arr, int left, int right){
   	if (left >= right)		return;	if (right - left + 1 > 10)//快速排序的优化	{
       	int key_index = part_lrpoint_quick(arr, left, right);//左右指针法		quick_Sort1(arr, left, key_index - 1);		quick_Sort1(arr, key_index + 1, right);	  }   else 	{
   	   Insert_Sort(arr + left, right - left + 1);	}}void quickSort_test1(){
   	int arr[] = {
    4, 3, 2, 8, 0, 9, 7, 8, 5, 4, 8, 9, 5, 6, 4 };	int n = sizeof(arr) / sizeof(int);	int left = 0;	int right = n - 1;	quick_Sort1(arr, left, right);	printf("左右指针法—快速排序结果：");	for (int i = 0; i < n; i++)	{
   		printf("%d ", arr[i]);	}	printf("\n");}int main(){
      quickSort_test1();   system("pause");   return 0;}

挖坑法通过优化后的代码实现

int Getmid_index(int* arr, int left, int right)//三数取中法(快速排序的优化){
   	int mid = left + (right - left) / 2;	if (arr[left] < arr[right])	{
   		if (arr[right] < arr[mid])		{
   			return right;		}		else if (arr[left] < arr[mid])		{
   			return mid;		}		else			return left;	}	//arr[left] > arr[right]	else	{
   		if (arr[left]
   
    = key)//右边找小的，放在左边的坑		{
   			right--;		}		arr[left] = arr[right];//填坑	}	arr[left] = key;	return left;}void quickSort_test1(){
   	int arr[] = {
    4, 3, 2, 8, 0, 9, 7, 8, 5, 4, 8, 9, 5, 6, 4 };	int n = sizeof(arr) / sizeof(int);	int left = 0;	int right = n - 1;	quick_Sort1(arr, left, right);	printf("左右指针法—快速排序结果：");	for (int i = 0; i < n; i++)	{
   		printf("%d ", arr[i]);	}	printf("\n");}int main(){
      quickSort_test1();   system("pause");   return 0;}

前后指针法通过优化后的代码实现

int Getmid_index(int* arr, int left, int right)//三数取中法(快速排序的优化){
   	int mid = left + (right - left) / 2;	if (arr[left] < arr[right])	{
   		if (arr[right] < arr[mid])		{
   			return right;		}		else if (arr[left] < arr[mid])		{
   			return mid;		}		else			return left;	}	//arr[left] > arr[right]	else	{
   		if (arr[left]

3. 快速排序的另外一种方法（非递归实现，通过自己实现的栈实现该算法）

利用栈的后进先出特征，代码如下：

#define _CRT_SECURE_NO_WARNINGS 1#include
   
    #include
    
     #include
     
      #include 
      
       #include 
       
        typedef int STDataType;typedef struct Stack{
   	STDataType* _array;	int _top;       // 栈顶	int _capacity;  // 容量}Stack;void StackInit(Stack* ps){
   	assert(ps);	ps->_top = 0;	ps->_capacity = 6;	ps->_array = (STDataType*)malloc(sizeof(STDataType)*ps->_capacity);}void StackDestory(Stack* ps){
   	assert(ps);	if (ps->_array == NULL)	{
   		free(ps->_array);		ps->_array = NULL;		ps->_capacity = ps->_top = 0;	}}void StackPush(Stack* ps, STDataType x){
   	assert(ps);	if (ps->_top == ps->_capacity)	{
   		size_t newcapacity = ps->_capacity == 0 ? 2 : ps->_capacity * 2;		ps->_array = (STDataType*)realloc(ps->_array, sizeof(STDataType)*newcapacity);		ps->_capacity = newcapacity;	}	ps->_array[ps->_top] = x;	++ps->_top;}void StackPop(Stack* ps){
   	assert(ps);	if (ps->_top == 0)	{
   		return;	}	--ps->_top;}STDataType Stacktop(Stack* ps){
   	assert(ps);	if (ps->_top == 0)	{
   		return;	}	return ps->_array[ps->_top - 1];//此处的ps->_top 需要减 1}bool StackEmpty(Stack* ps){
   	assert(ps);	return ps->_top == 0 ? 0 : 1;}int StackSize(Stack* ps){
   	assert(ps);	return ps->_top;};void quick_Sort2(int* arr, int left, int right){
   	Stack s;	StackInit(&s);	StackPush(&s, left);	StackPush(&s, right);	while (StackEmpty(&s))	{
   		int end = Stacktop(&s);		StackPop(&s);		int begin = Stacktop(&s);		StackPop(&s);		int key_index = part_flpoint_quick(arr, begin, end);//左右指针法		//[begin,key_index - 1] key_index [ key_index + 1,end]		if (begin < key_index - 1)		{
   			StackPush(&s, begin);			StackPush(&s, key_index - 1);		}		if (key_index + 1 < end)		{
   			StackPush(&s, key_index + 1);			StackPush(&s, end);		}	}}int main(){
   	quickSort_test2();	system("pause");	return 0;}

4.快速排序的特性总结

时间复杂度分析
①最优情况下时间复杂度：O( nlogn )，具体证明比较复杂就不详细说了，可以查阅其他资料。

②最差情况下时间复杂度：O( n^2 ),此时待排序的序列为正序或者逆序，每次划分只得到一个比上次划分少一个记录的子序列，注意另一个为空，如果递归树画出来，它就是一棵斜树，此时需要执行 n-1 次递归调用，且第 i 次划分需要经过 n-1 次关键字的比较才能找到第 i 个记录，也就是枢轴的位置，因此比较次数为，如图：

空间复杂度分析
首先就快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；快速排序每次递归都会返回一个中间值的位置，必须使用栈。所以空间复杂度就是栈用的空间。所以快速排序的空间复杂度为：
①：最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况。
②：最差的情况下空间复杂度为：O( n ) ；待排序的序列为正序或者逆序的情况。

稳定性分析
快排是不稳定的,这个不稳定表现在如果相同的比较元素,可能顺序不一样,假设我们有这样一个序列：2 , 2 ,2 ,但是这三个 2 是有区别的,我们标记为2a,2b,2c,快排后的结果不一定就是 2a, 2b, 2c 这样的排列，可能这三个 2 的顺序发生了变化，所以在某些特定场合我们要用结构体来使其稳定。

转载地址：http://jrwbb.baihongyu.com/

你可能感兴趣的文章