1、概述

排序就是将一组对象按照某种逻辑顺序重新排列的过程。

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

快速排序基本思想：

（1）先从数列中取出一个数作为基准数；

（2）分区过程中，将比这个数大的数全放到它的右边，小于或等于它的数全放在它的左边；

（3）在左右区间递归调用重复第二步，直到各区间只有一个数。

2、代码实现

package com.chunsoft.sort; /** * @author chunsoft * 通过一趟排序将要排序的数据分割成独立的两部分， * 其中一部分的所有数据都比另外一部分的所有数据都要小， * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行， * 以此达到整个数据变成有序序列。 */ public class QuickSort { public static void main(String[] args) { int data[] = {9,8,7,6,5,4,3,2,8}; F_QuickSort(data,0,data.length-1); for(int num :data) { System.out.println(num); } } //排序方法 public static void F_QuickSort(int data[], int l, int r) { if (l < r) { int i = l, j = r, x = data[l]; while (i < j) { while(i < j && data[j] >= x) // 从右向左找第一个小于x的数 j--; //找到后，将这个数赋值给i的位置，并将i向后移动位置 if(i < j) data[i++] = data[j]; while(i < j && data[i] < x) // 从左向右找第一个大于等于x的数 i++; //找到后，将这个数赋值给j的位置，并将j向前移动1位 if(i < j) data[j--] = data[i]; } data[i] = x; F_QuickSort(data, l, i - 1); // 递归调用 F_QuickSort(data, i + 1, r); } } }

3、复杂度和稳定性

（1）复杂度

将长度为N的无重复数组排序，快速排序平均需要2NLogN次比较。 快速排序最多需要N*N／2次比较，但随机打乱数组会防止这种情况发生。

时间复杂度：最差：O(N*N)，平均：O(nlog2n) 空间复杂度：O(log2n)~O(n)

（2）稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

不稳定的： 快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

（3）特点

快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。这种简洁性也是快速排序的一个优点。例如，归并排序和希尔排序一般都比快速排序慢，其原因就是它们在内循环中移动数据。

快速排序的最好情况是每次将数组对半分。