排序算法 — 快速排序

核心思想：递归+分治

设置一个元素作为基准数，通过一轮排序将待排序元素分为两部分，其中一部分元素都小于基准数，另一部分元素都大于或等于基准数，然后分别对这两部分重复上述操作，直到整个序列有序。

1. 定义一个基准值
2. 从左往右找到第1个小于或等于基准值的数
3. 从右往左找到第1个大于或等于基准值的数
4. 交换找到的两个数
5. 重复以上操作，直到左、右相遇，和基准值交换（基准值位置确定）
6. 重复对左、右子序列进行以上操作，直到序列整体有序

假设有左、右两个哨兵帮助我们遍历

初始：基准数6，左哨兵位置0，右哨兵位置9

找到右边第1个小于基准数的元素，左边第1个大于基准数的元素

交换它们的值

继续遍历和交换

两个哨兵相遇，第一轮遍历结束

基准数和当前位置的值交换

  

第一轮完成，左边序列小于基准数，右边序列大于基准数，重复对左、右序列进行以上操作

代码实现

void QuickSort(int arr[],int left,int right){
	//遍历完待排序序列所有元素，结束递归 
	if(left>=right) return;
	//i指向待排序序列最左边元素 
	int i=left;
	//j指向待排序序列最右边元素 
	int j=right;
	//存储基准数 
	int tmp=arr[left];
	//从左右两边遍历当前待排序序列所有元素 
	while(i=tmp && i 
复杂度 
 
 
时间复杂度：O(n*log n)
 
 
        最坏情况O(n^2)：每次取到的基准数为当前序列的最小（或最大）元素，则每次只能排好一个元素，共需要n次划分
 
 
        最好情况O(n*log n)：每次刚好可以二分待排序序列
 
 
        平均情况的复杂度：O(n*log n)
 
 
空间复杂度：O(1)
 
稳定性 
不稳定的排序算法，在交换过程中元素的相对位置会发生改变
 
特点 
快速排序是在冒泡排序上的改进，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式
交换，交换的距离很大，因此总比较和交换次数少了很多
就地排序（原数组空间上进行排序），空间复杂度为常量级
虽然极端情况下时间复杂度为O(n^2)，但多数情况为O(n*log n)，所以在相同数量级的排序算法中平均性能最好
 
ps：学生做的小博客，发展进行时......点击这里可以查看
 
        导航主页，画风不错，点击这里