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

前面说的冒泡排序是一种交换排序。交换排序还有一种算法，就是快速排序算法。

快速排序的核心思想是分而治之。意思就是选出一个基准（可以是第一个元素，也可以是最后一个。为了方便我们选取第一个），将小于这个基准的全部元素都放在这个基准的左边，大于这个基准的全部元素都放在基准的右边。然后分别对左右两个数组在进行同样的操作。这里我们就可以用到递归。也就是说我们每次进行上述操作后，都可以得到一个相对有序的数组。通过不断缩小范围，就会得到一个个小的有序数组。然后这个些数组组合起来就可以得到一个完整的有序数组。

直接撸代码（代码实现多种多样）

//分治的思想，以数组首个元素为基准元素，小于基准的放到左边，大于基准的放在右边，然后将基准数归位void quicksort(int a[],int start, int end) {    int i, j, t, base;    if (start>= end)    	return;    base= a[start]; //base中存的就是基准数    i = start;    j = end;    while (i != j)     {     	while (a[j] >= base&& i < j)	    	j--;    	while (a[i] <= base&& i < j)//再找左边的    		i++;    	if (i < j)//交换两个数在数组中的位置    	{    		t = a[i];    		a[i] = a[j];        	a[j] = t;    	}    }    //最终将基准数归位    a[start] = a[i];    a[i] = temp;    quicksort(a,start, i - 1);//继续处理左边的，这里是一个递归的过程    quicksort(a,i + 1, end);//继续处理右边的 ，这里是一个递归的过程    return；}

复杂度分析

时间复杂度并不好分析，因为快速排序的时间复杂度和选取的元素有关。当然也和数组本身元素的次序有关。平均来说，时间复杂度是O(nlogn)。

空间复杂度：算法本身只是用到了一个临时变量，可以看做不需要额为的空间。但是用到了递归，所以有栈的开销。空间复杂度为O(nlogn)。

适用场景分析：

可以看出，快速排序的时间复杂度是比较低的。所以即使数据量较大，快速排序也能hold住。但是要注意，如果本身数组已经是基本有序的，而且是倒序的，快速排序就退化成冒泡排序了，时间复杂度就变成O(n^2)了。所以当适合数据量大，待排序数组乱序程度高的时候，用快速排序是比较合适的。

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