快速排序的思想是在数组[p,r]中选择一个分区点q，将数组一分为2，同时将小于分区点的数值的放到分区点左侧[p,q-1]，大于分区点的数值的放到分区点右侧[q+1,r],重复这个过程。
快速排序也是用到了分治思想和递归实现方式，这一点跟归并排序是一样的，但是快速排序的实现跟归并是完全不一样的。
归并排序是先分解再合并，从下到上解决问题。
快速排序是从上到下进行分区实现排序。俯视这个过程像是层次不同的拼图一般，完整组合成有序序列。
/** * 快速排序 * @param arr * @param n */ public static void quickSort(int[] arr,int n){ quickSort(arr,0,n-1); } /** * 根据分区点，递归继续分解子分区 * @param arr * @param p * @param r */ public static void quickSort(int[] arr,int p,int r){ if(p>=r){ return; } int q = partition(arr,p,r); quickSort(arr,p,q-1); quickSort(arr,q+1, r); } /** * 快排分区 *随机生成[p,r]区间内pivot,将比pivot大的放在其右侧，比pivot小的放在其左侧 * @param arr * @param p * @param r */ public static int partition(int[] arr,int p,int r){ int pivot = arr[r]; int i=p; for (int j = p; j < r; j++) { //当前元素比分区点小，则交换当前元素arr[j]到arr[i],也就是将小的移动到左侧，大的移动到右侧，而这个大小也是相对于分区点来说的，将来分区点会放到中间位置 if(arr[j] < pivot){ int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; //交换完位置（每确定完一个小元素后）以后，移动i指针到下一位（这个位置也是为下一个小元素准备的），只要arr[j]比分区点小，就将其交换到指针i的位置，并将i后移 i++; } } //迭代完成后，所有相对于pivot小的元素都被移动到靠左的位置（i指针动态指向的位置），所有相对于pivot大的元素都被移动到右侧，但是还是需要pivot将大小区间分割开 int temp = arr[i]; arr[i]=arr[r]; arr[r]=temp; return i; }用一张图片解读下代码，这里描述的分区过程，将大于pivot的放在左边，将小于pivot的放在右边：
快速排序是原地排序算法吗？
快速排序是原地排序算法，不需要额外存储空间。内部元素交换完成排序。
快速排序是稳定排序算法吗？6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个6的顺序会变，所以快速排序不是稳定排序算法。
快速排序算法的时间复杂度是多少？因为快速排序跟归并排序一样都是采用的分治思想使用递归实现，所以归并排序的时间复杂度计算公式也一样适用，前提是每次快速排序选择的pivot都可以将数组正好一分为二。
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
但是，这种情况很难实现。极端情况下一个数组已经是有序，如果pivot每次都选择数组最后一个，那每次分区得到的两个子区间都是不均等的。大约需要n次分区才能完成整个快排。所以这种非常坏的情况下时间复杂度就从极好情况下的O(nlogn)退化成O(n^2).那么平均时间复杂度呢？这里可以说大部分情况下可以做到O(nlogn)，极端情况下才会退化O(n^2),但是这个是可以用很多办法去避免的。