快速排序算法

算法介绍

快速排序算法是对冒泡排序的一种该改进，由C.A.R.Hoare(Charles Antony Richard Hoare,东尼·霍尔）在1962年提出。

算法思想：

快速排序算法运用了分治的思想，通过一趟排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据比另外一部分所有的数据要小，再按这种方法对两部分数据分别进行快速排序，整个排序过程递归进行，使整个数据变成有序序列。

算法原理

快速排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数。为了方便，我们一般选择第一个数作为基准数（选第几个没有多大关系）。接下来我们需要将待排序序列中小于基准数的元素移动到数列的左边，把大于基准数的元素移到待排序数列的右边。这时，左右两个分区的元素就相对有序了
然后重复以上过程。

算法的实现

#include<iostream>
using namespace std;
const int N=1e5+5;
int arr[N];
void quick_sort(int q[],int l,int r){
	if(l>=r) return;
	int i=l-1,j=r+1,mid=arr[l+r>>1];
	while(i<j){
		do i++;while(arr[i]<mid);
		do j--;while(arr[j]>mid);
		if(i<j) swap(arr[i],arr[j]);
	} 
	quick_sort(q,l,j),quick_sort(q,j+1,r);
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	quick_sort(arr,0,n-1);
	for(int i=0;i<n;i++) cout<<arr[i]<<" ";
	return 0; 
} 

算法特点与复杂度分析

快速排序在最坏情况下的复杂度为O(n2)，平均时间复杂度为O（nlogn)。该算法是基于分治法实现的，分治即是分而治之，把问题分为一个个小的部分分别解决，再把结果组合起来。
空间复杂度：由于快排只使用了原本的数组空间，所以空间复杂度为常量级，但是每次划分后是递归调用，递归调用会消耗一定的空间，一般为O(longn)，最坏情况下为O(n)。
快速排序算法是不稳定的排序算法，在排序后，可能对相同元素的相对位置造成改变。
快速排序被被认为是相同数量级的所有排序算法中，平均性能最好的。

快速排序

原文：https://www.cnblogs.com/zzjjblogs/p/14616624.html