最开始学习编程，遇到排序问题，一般都是用冒泡法，因为冒泡法好理解，代码量少。但是这种算法时间复杂度高，当需要排序的元素较多时，程序运行时间很长，因此产生了快速排序算法。该算法的实现可分为以下几步：
 
1. 在数组中选一个基准数（通常为数组第一个）；
 
2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；
 
3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。
 
例如有一需要排序的数组为：23,45,17,11,13,89,72,26,3,17,11,13（从小到大排序）：
 
选取数组第一个数23为基准数，存入temp变量中，从数组的左右两边界向中间进行遍历，定义两个指针 i 和 j，i 最开始指向数组的第一个元素，j 最开始指向数组的最后一个元素。指针 i 从左向右移动，指针 j 从右向左移动。先移动 j 指针（从右忘左移），当 j 指向的数大于基准数时，略过，j 继续往左移动，直到遇到小于等于基准数的数arr[j]，将arr[j]填入arr[i]中；再移动 i 指针，当 i 指向的数小于等于基准数时，略过，i 继续往右移动，直到遇到不比基准数小的数arr[i]，将arr[i]填入arr[j]中；再移动 i 指针，再移动 j 指针...(轮换移动)，直到 i 和 j 指针相遇，此时将temp（基准数）填入arr[i]中即完成算法的第2个步骤。接下来分别将基准数左边和右边的数组按照以上方法进行聚合，直到每个子集只有一个元素，即排序完成。
 
可能描述得有些抽象，接下来用图一步一步的示意：
 
将数组第一个数23赋给temp变量，指针 i 指向数组第一个元素，指针 j 指向数组最后一个元素
 
 
从 j 开始遍历（从右往左），遇到13时，因为13<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为13；
 
 
再从 i 遍历（从左往右），遇到45时，因为45>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为45；
 
 
继续从 j 遍历，遇到11时，因为11<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为11；
 
 
从 i 遍历，遇到89时，因为89>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为89；
 
 
从 j 遍历，遇到17时，因为17<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为17；
 
 
从 i 遍历，遇到72时，因为72>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为72；
 
 
从 j 遍历，遇到3时，因为3<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为3；
 
 
从 i 遍历，遇到26时，因为26>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为26；
 
 
从 j 遍历，和 i 重合；
 
 
将 temp（基准数23）填入arr[i]中。
 
 
此时完成算法的第2个步骤，接下来将23左边和右边的子区间分别用以上方法进行排序，直到区间只有一个元素即排序完成。
 
代码如下：
 
// Quick_Sort.cpp : Defines the entry point for the application.
// 快速排序算法

#include "stdafx.h"
#include<iostream>
using namespace std;

//快速排序算法(从小到大)
//arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界
void quickSort(int *arr,int begin,int end)
{
	//如果区间不只一个数
	if(begin < end)
	{
		int temp = arr[begin]; //将区间的第一个数作为基准数
		int i = begin; //从左到右进行查找时的“指针”，指示当前左位置
		int j = end; //从右到左进行查找时的“指针”，指示当前右位置
		//不重复遍历
		while(i < j)
		{
			//当右边的数大于基准数时，略过，继续向左查找
			//不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
			while(i<j && arr[j] > temp)
				j--;
			//将右边小于等于基准元素的数填入右边相应位置
			arr[i] = arr[j];
			//当左边的数小于等于基准数时，略过，继续向右查找
			//(重复的基准元素集合到左区间)
			//不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
			while(i<j && arr[i] <= temp)
				i++;
			//将左边大于基准元素的数填入左边相应位置
			arr[j] = arr[i];
		}
		//将基准元素填入相应位置
		arr[i] = temp;
		//此时的i即为基准元素的位置
		//对基准元素的左边子区间进行相似的快速排序
		quickSort(arr,begin,i-1);
		//对基准元素的右边子区间进行相似的快速排序
		quickSort(arr,i+1,end);
	}
	//如果区间只有一个数，则返回
	else
		return;
}
int main()
{
	int num[12] = {23,45,17,11,13,89,72,26,3,17,11,13};
	int n = 12;
	quickSort(num,0,n-1);
	cout << "排序后的数组为：" << endl;
	for(int i=0;i<n;i++)
		cout << num[i] << ' ';
	cout << endl;
	system("pause");
	return 0;
}
 
运行结果如下：
 
 
 

十大经典排序算法
 
十大经典排序算法-冒泡排序算法详解
十大经典排序算法-选择排序算法详解
十大经典排序算法-插入排序算法详解
十大经典排序算法-希尔排序算法详解
十大经典排序算法-快速排序算法详解
十大经典排序算法-归并排序算法详解
十大经典排序算法-堆排序算法详解
十大经典排序算法-计数排序算法详解
十大经典排序算法-桶排序算法详解
十大经典排序算法-基数排序算法详解
 
一、什么是快速排序
 
1.概念
 
快速排序（Quick Sort）是从冒泡排序算法演变而来的，实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分
 
2.算法原理
 
这是一个无序数列：4、5、8、1、7、2、6、3，我们要将它按从小到大排序。按照快速排序的思想，我们先选择一个基准元素，进行排序
 
 我们选取4为我们的基准元素，并设置基准元素的位置为index，设置两个指针left和right，分别指向最左和最右两个元素
 
 接着，从right指针开始，把指针所指向的元素和基准元素做比较，如果比基准元素大，则right指针向左移动，如果比基准元素小，则把right所指向的元素填入index中
 
3和4比较，3比4小，将3填入index中，原来3的位置成为了新的index，同时left右移一位
 
 然后，我们切换left指针进行比较，如果left指向的元素小于基准元素，则left指针向右移动，如果元素大于基准元素，则把left指向的元素填入index中
 
5和4比较，5比4大，将5填入index中，原来5的位置成为了新的index，同时right左移一位
 
 接下来，我们再切换到right指针进行比较，6和4比较，6比4大，right指针左移一位
 
 2和4比较，2比4小，将2填入index中，原来2的位置成为新的index，left右移一位
 
 随着left右移，right左移，最终left和right重合
 
 此时，我们将基准元素填入index中，这时，基准元素左边的都比基准元素小，右边的都比基准元素大，这一轮交换结束
 
 第一轮，基准元素4将序列分成了两部分，左边小于4，右边大于4，第二轮则是对拆分后的两部分进行比较
 
此时，我们有两个序列需要比较，分别是3、2、1和7、8、6、5，重新选择左边序列的基准元素为3，右边序列的基准元素为7
 
 第二轮排序结束后，结果如下所示
 
 此时，3、4、7为前两轮的基准元素，是有序的，7的右边只有8一个元素也是有序的，因此，第三轮，我们只需要对1、2和5、6这两个序列进行排序
 
 第三轮排序结果如下所示
 
 至此所有的元素都是有序的
 
3.算法实现
 
function sort(arr, startIndex, endIndex) {
    // 递归结束条件：startIndex大于等于endIndex的时候
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素的位置
    let pivotIndex = partition(arr, startIndex, endIndex);
    sort(arr, startIndex, pivotIndex - 1);
    sort(arr, pivotIndex + 1, endIndex);
}

function partition(arr, startIndex, endIndex) {
    // 选择第一个位置的元素作为基准元素
    let pivot = arr[startIndex];
    let left = startIndex;
    let right = endIndex;
    let index = startIndex;

    // 外循环在左右指针重合或者交错的时候结束
    while (right > left) {
        // right指针从右向左进行比较
        while (right > left) {
            if (arr[right] < pivot) {
                arr[left] = arr[right];
                index = right;
                left++;
                break;
            }
            right--;
        }
        // left指针从左向右进行比较
        while (right > left) {
            if (arr[left] > pivot) {
                arr[right] = arr[left];
                index = left;
                right--;
                break;
            }
            left++;
        }
    }
    arr[index] = pivot;
    return index;
}

let arr = [4, 5, 8, 1, 7, 2, 6, 3];
sort(arr, 0, arr.length - 1);
console.log(arr);
 
三、快速排序算法特点
 
1.时间复杂度
 
快速排序算法在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止，平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是O(nlogn)
 
在极端情况下，快速排序算法每一轮只确定基准元素的位置，时间复杂度为O(N^2)
 
2.空间复杂度
 
快速排序算法排序过程中只是使用数组原本的空间进行排序，因此空间复杂度为O(1)
 
3.稳定性
 
快速排序算法在排序过程中，可能使相同元素的前后顺序发生改变，所以快速排序是一种不稳定排序算法

前言
 
排序算法非常多，几乎每个人学的第一个排序算法都是冒泡算法，但是冒泡算法的时间复杂度是很高的，是一种效率很低的算法。而目前来说，快速排序是相对比较好的一种算法：实现难度低，时间复杂度低。但快速排序在一些情况下也可能出现退化到和冒泡算法一样的时间复杂度，所以需要读者注意一下，下面我会讲到。那么接下来就来看看这个算法。
 
 
 
笔者才疏学浅，有不同观点欢迎评论区或私信讨论。如需转载请留言告知。
 另外欢迎阅读笔者的个人博客一只修仙的猿的个人博客，更精美的UI，拥有更好的阅读体验。
 
 
算法思路
 
递归算法的思路其实很简单：
 
 
 
从数据中取出一个数，即为mid
比mid小的数放在左边，比mid大的数放在右边
最后把mid放在中间
对左右两边的子数组进行递归排序，直到只剩下一个元素则全部排序完成。
 
 
具体的实现思路我们举一个例子：
 
现在有一个数组：
 
 
这里细心的读者会发现诶第三个数怎么后面有一点，这个不是手滑打出来的。而是为了证明在排序的过程中，两个3的顺序是否会发生颠倒，从得出这是否是一个稳定的排序。
 
 
首先我们取出一个数，当成哨兵。这里我们取第一个数5当成哨兵。然后我们把这个数和最后一个数交换。为什么需要交换呢？这样我们就不需要去额外设置一个变量存储哨兵了。如图：
  
 
接下来我们设置两个变量：min和max们分别表示比mid小的数的最大的下标，和比mid大的数最小的坐标。
 
  
 
   
举个例子如下图：
 
    
  
  
 
接下来我们从左边开始，如果min指向的数比哨兵小，则min = min+1，否则则停下来。执行完之后如下图：
  
 
然后从右边开始，如果max指向的数大于等于哨兵，则max = max-1，否则则停下来，执行完成之后如下图：
  
 
然后把min和max指向的数字进行交换：（这里可以看到两个3的顺序发生了颠倒，所以这是一个不稳定的排序）
  
 
重复3,4,5步骤直到min==max
  
 
把下标为min的数字和哨兵进行交换，至此一轮的排序已经完成：
  
 
对前后的子数组进行递归排序。完成排序。
  
 
快速排序的核心就是利用递归分治的思路来降低时间复杂度。如果我们每次都刚好选到中位数，那么递归树的高度就是logn(这里的n代表元素的个数)，每一层递归都需要遍历一次数组，那么时间复杂度最好的情况就是：
 
 
 
O(logn)
 
 
但是，如果每次都取到最小或者最大的数，那么快排的递归树高度则为n，那么他的时间复杂度将退化为：
 
 
 
O(n^2)
 
 
由于只需要常量空间，所以空间复杂度为：
 
 
 
O(1)
 
 
代码示范
 
下面使用java语言做一个规范。接口参数为：整型数组，数组的开始下标，数组的结束下标。（因可能是子数组所以需要下标参数）
 
private void fastSort(int[] nums,int start,int end) {
    // 终止条件：start>=end
    if(start>=end) return;
    
    // 记录原始的下标
    int startRow = start;
    int endRow = end;
    
    // 采用随机数获取下标，可以降低退化到n^2的概率
    int random = new Random().nextInt(end-start)+start;
    // 交换两个数
    swap(nums,random,end);
   
    // 重复上述的3,4,5步骤
    while(start<end){
        // 记得这里的每一步都必须判断start<end
        while( nums[start]<nums[endRow] && start<end ){
            start++;
        }
        while( nums[end]>=nums[endRow] && start<end ){
            end--;
        }
        // 如果相同则把哨兵放到中间，排序结束
        // 否则start和end交换位置，继续循环
        if(start==end) swap(nums,start,endRow);
        else{
            swap(nums,start,end);
        }
    }
    // 最后对子数组进行递归排序
    paixu(nums,startRow,start-1);
    paixu(nums,start+1,endRow);
}

// 交换数组中的两个数
private void swap(int[] nums,int one,int two){
    int temp = nums[one];
    nums[one] = nums[two];
    nums[two] = temp;
}

 
快速排序算法的三种方式及其优化java实现
 
1、快速排序算法的简绍
2、快速排序的基本思想
3、快速排序左右指针法图解
4、快速排序左右指针法核心代码
5、快速排序挖坑法图解
6、快速排序挖坑法核心代码
7、快速排序前后指针法图解
8、快速排序前后指针法核心代码
9、快速排序基准点优化及其核心代码
10、快速排序算法的时间复杂度
11、快速排序的稳定性
11、快速排序与其他排序的比较
 

 
1、快速排序算法的简绍
 
快速排序算法(QuickSort)又称为划分交换排序，快速排序是对冒泡排序的一种改进方法，在冒泡排序中，记录关键字的比较和交换是在相邻记录之间进行的，记录每次交换只能上移或下移一个相邻位置，因而总的比较和移动次数较多；在快速排序中，记录关键字的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面的单元，关键字较小的记录一次就能交换到前面的单元(升序)，记录每次移动的距离较远，因而总的比较和移动次数较少，速度很快，所以被称为快速排序。
 
2、快速排序的基本思想
 
首先当前无序区data[low…high]中任取一个记录作为排序比较的基准（不妨设为x,其位置为i），用次基准将当前无序区划分为两个较小的无序区：data[low…i-1]和data[i+1…high]，并使左边的无序区中所有的记录的关键字均小于等于基准的关键字，右边的无序区中所有的记录的关键字均大于等于基准的关键字，即data[low…i-1]中的关键字<=x.key<=data[i+1…high]中的关键字，这个过程称为一趟快速排序（或一次划分）。当data[low…i-1]和data[i+1…high]均非空时，分别对它们进行上诉划分过程，直到所有无序区中的记录均已排序好为止。
 
3、快速排序左右指针法图解
 
1、选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。 设置两个变量left = 0;right = N - 1。
 2、 从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
 3、重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。
 
 
4、快速排序左右指针法核心代码
 

public class Quick_Sort4 {
	public static void quickSort(int[] arrays, int low, int hi) {

		if (low < hi) {

			// 求每次分治的分割线
			int divideIndex = getDivideIndex(arrays, low, hi);
			// 再递归分别对分割的俩个子数组进行递归排序
			quickSort(arrays, low, divideIndex - 1);
			quickSort(arrays, divideIndex + 1, hi);

		}

	}

	public static int getDivideIndex(int[] arrays, int low, int hi) {
		// 设定arrays[low]为基准值,从右到左移动hi,找到大于第一个大于基准值的数字。
		// 从左向右移动low指针,找到第一个小于基准值的数,交换low和high位置上的值
		// 直到low=high的时候，将基准值填入arrays[low]
		int baseValue = arrays[low];
		int oldLow = low;
		while (low < hi) {
			while (low < hi && arrays[hi] >= baseValue) {

				hi--;
			}

			while (low < hi && arrays[low] <= baseValue) {
				low++;
			}
			if (low < hi) {
				swap(arrays, low, hi);
			}
		}

		if (low == hi) {
			arrays[oldLow] = arrays[low];
			arrays[low] = baseValue;

		}
		return low;
	}

	public static void swap(int[] arrays, int low, int high) {

		int temp = 0;
		temp = arrays[low];
		arrays[low] = arrays[high];
		arrays[high] = temp;

	}

	public static void main(String[] args) {
		// 显示排序前的序列

		int[] arrays = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
		System.out.println("快速排序之左右指针排序前:");
		for (int data : arrays) {
			System.out.print(data + " ");
		}
		System.out.println();
		getDivideIndex(arrays, 0, arrays.length - 1);
		System.out.println("第一趟排序结果:");
		for (int data : arrays) {
			System.out.print(data + " ");
		}
		System.out.println();
		quickSort(arrays, 0, arrays.length - 1);
		System.out.println("快速排序之左右指针排序后:");
		for (int data : arrays) {
			System.out.print(data + " ");
		}
	}

}
 
运行结果：
 
 
5、快速排序挖坑法图解
 
1、选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序 列最后一个数为枢轴，也是初始的坑位。
 2、设置两个变量left = 0;right = N - 1;
 3、从left一直向后走，直到找到一个大于key的值，然后将该数放入坑中，坑位变成了array[left]。
 4、right一直向前走，直到找到一个小于key的值，然后将该数放入坑中，坑位变成了array[right]。
 5、重复3和4的步骤，直到left和right相遇，然后将key放入最后一个坑位。
 6、当left >= right时，将key放入最后一个坑，就完成了一次排序。
 注意：left走的时候right是不动的，反之亦然。因为left先走，所有最后一个坑肯定在array[right]。
 
 
6、快速排序挖坑法核心代码
 

 
 
 运行结果：
 
 
 
7、快速排序前后指针法图解
 
定义变量cur指向序列的开头，定义变量pre指向cur的前一个位置。
 当array[cur] < key时，cur和pre同时往后走，如果array[cur]>key，cur往后走，pre留在大于key的数值前一个位置。
 当array[cur]再次 < key时，交换array[cur]和array[pre]。
 通俗一点就是，在没找到大于key值前，pre永远紧跟cur，遇到大的两者之间机会拉开差距，中间差的肯定是连续的大于key的值，当再次遇到小于key的值时，交换两个下标对应的值就好了。
 
 
8、快速排序前后指针法核心代码
 

public class Quick_Sort3 {
	public static void main(String[] args) {

		int[] arrays = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
		System.out.println("快速排序之左右指针排序前:");
		for (int data : arrays) {
			System.out.print(data + " ");
		}
		System.out.println();
		partion(arrays, 0, arrays.length - 1);
		System.out.println("第一趟排序结果:");
		for (int data : arrays) {
			System.out.print(data + " ");
		}
		System.out.println();
		quickSort(arrays, 0, arrays.length - 1);
		System.out.println("快速排序之左右指针排序后:");
		for (int data : arrays) {
			System.out.print(data + " ");
		}

	}

	static int partion(int arr[], int left, int right) {
		int pCur = left;
		int prev = pCur - 1;
		int key = arr[right];
		while (pCur <= right) {
			if (arr[pCur] <= key && (++prev) != pCur)
				swap(arr, prev, pCur);
			pCur++;
		}
		return prev;
	}

	static void quickSort(int arr[], int left, int right) {
		if (left < right) {
			int mid = partion(arr, left, right);
			quickSort(arr, left, mid - 1);
			quickSort(arr, mid + 1, right);
		}

	}

	public static void swap(int[] arrays, int low, int high) {

		int temp = 0;
		temp = arrays[low];
		arrays[low] = arrays[high];
		arrays[high] = temp;

	}
}

 
运行结果：
 
 
9、快速排序基准点优化及其核心代码
 
对于基准点的优化一般有三种：固定切分，随机切分和三数取中法。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N^2)。对于三数取中选择基准点是最理想的一种。
 下面给出三个数取中间数的算法实现：
 

public class Quick_Sort {
	public static void quickSort(int[] a, int low, int high) {
		if (low >= high) {
			return;
		}
		// 进行第一轮排序获取分割点
		int index = partSort(a, low, high);
		// 排序前半部分
		quickSort(a, low, index - 1);
		// 排序后半部分
		quickSort(a, index + 1, high);
	}

	public static int partSort(int[] a, int low, int high) {
		// 调用三数取中
		int mid = Quick_Sort.getMid(a, low, high);
		swap(mid, a[high]);
		int key = a[high];
		while (low < high) {
			// 从前半部分向后扫描
			while (low < high && a[low] <= key) {
				++low;
			}
			a[high] = a[low];
			// 从后半部分向前扫描
			while (low < high && a[high] >= key) {
				--high;
			}
			a[low] = a[high];
		}
		// 最后把基准点存入
		a[high] = key;
		return low;
	}

	public static int getMid(int[] a, int low, int high) {
		int mid = low + (high - low) / 2;
		// 下面两步保证了a[high]是最大的
		if (a[mid] > a[high]) {
			swap(a[mid], a[high]);
		}
		if (a[low] > a[high]) {
			swap(a[low], a[high]);
		}
		// 将a[low]和a[mid]比较，让较小的在啊[low]的位置
		if (a[mid] > a[low]) {
			swap(a[mid], a[low]);
		}
		int key = a[low];
		return key;
	}

	public static void swap(int a, int b) {
		int temp = a;
		a = b;
		b = temp;
	}

	public static void main(String[] args) {
		// 显示排序前的序列
		int[] array = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
		System.out.print("排序前:");
		for (int data : array) {
			System.out.print(data + " ");
		}
		System.out.println();
		// 显示排序后的序列
		Quick_Sort.quickSort(array, 0, 9);
		System.out.print("排序后：");
		for (int data : array) {
			System.out.print(data + " ");
		}
	}
}

 
运行结果：
 
 
10、快速排序算法的时间复杂度
 
10.1最优情况下
 快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；
 此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；
 下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
 T[n] = 2T[n/2] + n ----------------第一次递归
 令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----------------第二次递归
 = 2^2 T[ n/ (2^2) ] + 2n
 令：n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n ----------------第三次递归
 = 2^3 T[ n/ (2^3) ] + 3n
 …
 令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束)
 当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
 得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
 T[n] = 2^m T[1] + mn ；其中m = logn;
 T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数
 又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；
 综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )
 10.2最差情况下
 最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
 这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
 综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )
 10.3平均时间复杂度
 快速排序的平均时间复杂度是：O(nlogn)
 
11、快速排序的稳定性
 
因为在快速排序的时候，即使待排序元素可基数相等也需要移动待排序元素的位置使得有序，所以快速排序是不稳定的
 
11、快速排序与其他排序的比较