无敌快排

谁践踏了优雅 2022-02-15 03:28 329阅读 0赞

## 快速排序 ##

既然人家名称就叫快速排序，那么自然排序速度快，但是快也是相对而言的，不过大家知道就行了，这是哲学问题，万事万物都是相对的，原谅我也不咋的懂哲学，换一种不同的场景，也许它并没有其它常见排序算法快。

~~接下来让我们看看快速排序到底是什么样的

\-基本思想  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]  
这就是快排的基本思路，那么到底如何让比基准值小的在左边，比基准值大的在右边呢？这里我给大家介绍两种种方法。

*  快排一 ： 利用Hover法（实质为双指针，先将基准值保存，然后从右向左找小于基准值的数停下来，再从左向右找大于基准值的数停下来，两数交换并重复步骤即可，最后将基准值放置正确位置）
 *  快排二 ： 利用填坑法（原理相同，先保存基准值，然后从右向左找小于基准值的数填入基准值位置，此时它原来的位置已空，再从左向右找大于基准值的数填入空位置，又空出一个位置，重复步骤，最后将基准值放置正确位置，这种方法比Hover法有点在于它不用交换数据，直接进行变量赋值）
 *  具体实现思路

#include<iostream>
    #include<stack>
    using namespace std;
    
    /*
    快速排序:选择一个基准值，让基准值左边的数都小于基准值，右边的数都大于基准值
    每一层的 Partition
    	时间复杂度是 O(n)
    	空间复杂度是 O(1)
    数多少个 O(n)，二叉树高度个 O(n)
    空间消耗在于递归调用的栈帧消耗，最终消耗的情况是二叉树的高度
    	二叉树的高度是 log(n) - n 在变化
    					最好						平均					最坏
    时间复杂度		O(n * log(n))				O(n * log(n))			O(n^2)
    空间复杂度		O(log(n))					O(log(n))				O(n)
    
    稳定性: 不稳定
    */
    
    
    //打印数组内容
    void print(int array[], int size) {
    	for (int i = 0; i < size; i++) {
    		cout << array[i] << " ";
    	}
    	cout << endl;
    }
    //交换函数
    void swap(int array[], int i, int j) {
    	int tmp = array[i];
    	array[i] = array[j];
    	array[j] = tmp;
    }
    
    
    //利用填坑法快速排序
    void QuickSort1(int array[], int left,int right) {
    	int i = left;
    	int j = right;
    	//设置基准值
    	int temp = array[left];
    	if (i < j) {
    		while (i < j) {
    			//从后往前找小于基准值的数
    			while (i < j && array[j] >= temp) {
    				j--;
    			}
    			//填坑
    
    			if (i < j) {
    				array[i] = array[j];
    				i++;
    			}
    			//从前往后找大于基准值的数
    			while (i < j && array[i] < temp) {
    				i++;
    			}
    			//填坑
    			if (i < j) {
    				array[j] = array[i];
    				j--;
    			}
    		}
    		//循环结束 i == j,将基准值放入正确位置
    		array[i] = temp;
    		//递归左半边
    		QuickSort1(array, left, i - 1);
    		QuickSort1(array, i + 1, right);
    	}
    }
    
    //利用hover法快速排序
    void QuickSort2(int array[], int left, int right) {
    	int i = left;
    	int j = right;
    	//设置基准值
    	int temp = array[left];
    	if (i < j) {
    		while (i < j) {
    			//从后往前找一个小于基准值的数
    			while (i < j && array[j] >= temp) {
    				j--;
    			}
    			//从前往后找一个大于基准值的数
    			while (i < j && array[i] < temp) {
    				i++;
    			}
    			//将两个数进行交换
    			if (i < j) {
    				swap(array, i, j);
    				j--;
    				i++;
    			}
    		}
    		//i == j 结束循环，交换基准值
    		swap(array, temp, array[i]);
    		QuickSort2(array, left, i - 1);
    		QuickSort2(array, i + 1, right);
    	}
    }
    
    int main(void) {
    	int array[] = {9,5,3,7,3,2,8,6};
    	int size = sizeof(array) / sizeof(int);
    	cout << "排序前：";
    	print(array, size);
    	cout << "排序后：";
    	QuickSort1(array,0,size - 1);
    	print(array, size);
    	cout << "排序后：";
    	QuickSort2(array, 0, size - 1);
    	print(array, size);
    	system("pause");
    	return 0;
    }

*  快速排序总结

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

**注意事项：**  
1、如何选择基准值  
（1）选择到边上很容易遇到最坏情况，逆序/顺序  
（2）随机选择法 rand()  
（3）三数取中法 mid = (left + right) / 2;  
后两种方法选择之后，然后可以将基准值转换到头部或者尾部就和我们写的是一样的了。  
2、快排主要应用了一种分治算法，即将大问题转换成小问题，分开处理小问题，就简单了很多，这种思想值得我们学习。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220215/92f04dd0f0f9489fb6e0c04f3dc43123.png