与归并排序一样，快速排序也是一个分治算法，需要选择一个基准（第一个元素，最后一个元素，随机一个元素），以此基准作为划分；快速排序的关键是划分 partion() ；。每一趟划分，我们就可以将作为基准值 x 放到排序数组的正确位置，并且将所有比 x 小的放到 x 的左边，所有比 x 大的元素放到 x 的右边。
class QuickSort
{ /*将最后一个元素作为 pivot 进行划分操作*/int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // 比 pivot 小的元素的下标for (int j = low; j < high; j++) { // 如果当前的元素小于 pivot if (arr[j] < pivot) { i++; // 交换 arr[i] 和 arr[j]int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 交换 arr[i+1] 和 arr[high] (也就是pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } /*分的阶段，利用递归调用实现快速排序*/void sort(int arr[], int low, int high) { if (low < high) { /* pi 就是 pivot 排序后位置的下标*/int pi = partition(arr, low, high); // 递归调用 pivot 的前后数组sort(arr, low, pi-1); sort(arr, pi+1, high); } } /* 打印输出 */static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } // 主函数 public static void main(String args[]) { int arr[] = {1,8,3,9,4,5,4,7}; int n = arr.length; QuickSort ob = new QuickSort(); ob.sort(arr, 0, n-1); System.out.println("sorted array"); printArray(arr); }
}
快速排序的实现中，我们仅使用了一个临时变量用于交换操作，也就是其空间复杂度为 1，所以快速排序也是一个原地排序算法；
在归并排序中，数组总被划分为两半（即n/2 )；而快速排序，数组可能被划分为任意比例，而不是强制要求将数组划分为相等的两部分。
归并排序适用于任何类型的数据集，不受数据集大小限制；而快速排序不适用于大规模数据集（简单来说，就是数组太大，快速排序效果并不好）