快速排序

概念介绍

QuickSort快速和归并排序一样，是采用分治法解决问题的一个典型应用。它选择一个元素作为基准元素，并围绕选定的基准元素对给定数组进行分区。

quickSort有很多不同的版本，它们以不同的方式选择基准元素。

选择第一个元素作为基准元素。选择最后一个元素作为基准元素选择一个随机元素作为基准元素选择中值作为基准元素

QuickSort中的关键进程是partition()。

目标分区：给定一个数组和数组的一个元素x作为基准元素，将x放在已排序数组中正确的位置，并将所有较小的元素(小于x的)放在x之前，将所有较大的元素(大于x的)放在x之后。所有这些都应该在线性时间内完成。

实现思路

/* low --> Starting index, high --> Ending index */quickSort(arr[], low, high){if (low < high){/* pi is partitioning index, arr[pi] is nowat right place */pi = partition(arr, low, high);quickSort(arr, low, pi - 1); // Before piquickSort(arr, pi + 1, high); // After pi}}

适用场景

适用于大数据的比较

比较的元素越多，快速排序比冒泡排序越快

代码示例

选取最后一个值作为基准元素

public class SortExample {// Driver codepublic static void main(String args[]) {int[] arr = {1, 20, 6, 4, 5,2,3,1,8,2 };quickSort(arr,0,arr.length-1);printArray(arr);}static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}static int partition(int[] arr, int low, int high) {// pivotint pivot = arr[high];// Index of smaller element and indicates the right position of pivot found so farint i = (low - 1);for(int j = low; j <= high - 1; j++) {// 升序排列,如果修改为>,则是倒序if (arr[j] < pivot) {// Increment index of smaller elementi++;swap(arr, i, j);}}swap(arr, i + 1, high);return (i + 1);}/* The main function that implements QuickSortarr[] --> Array to be sorted,low --> Starting index,high --> Ending index*/static void quickSort(int[] arr, int low, int high) {if (low < high) {// pi is partitioning index, arr[p] is now at right placeint pi = partition(arr, low, high);// Separately sort elements before partition and after partitionquickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}/* A utility function to print array of size n */private 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 class QuickSortExample {public static void main(String[] args) {int arr[] = {981,8, 3, 2, 7, 4, 6, 8,23,23,11,8,9,11,5,50,101};quickSort(arr,0,arr.length-1);print(arr);}public static void quickSort(int arr[], int low, int high) {if (low<high) {int pivot = partition(arr, low, high);//算出枢轴值quickSort(arr, low, pivot - 1); //对低子表递归排序quickSort(arr, pivot + 1, high);//对高子表递归排序}}/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/public static int partition(int arr[],int low,int high) {int mid = low + ((high - low) >> 1); //计算数组中间的元素的下标//使用三数取中法选择枢轴if (arr[mid] > arr[high]) {swap(arr,mid,high);}if (arr[low] > arr[high]) {swap(arr,low,high);}if (arr[mid] > arr[low]) {swap(arr,mid,low);}//此时，arr[mid] <= arr[low] <= arr[high]int pivotkey = arr[low];int i = low, j = high;//从表的两端交替向中间扫描,当没有相遇while(i<j) {while (arr[j] >= pivotkey && i<j){j--;}while (arr[i] <= pivotkey && i<j){i++;}if (i<j) {swap(arr, i, j);}}//最终将基准数归位swap(arr, low, i);//返回枢轴所在的位置return i;}static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}static void print(int arr[]) {int n = arr.length;for (int i = 0; i < n; i++) {System.out.print(arr[i] + " ");}System.out.println();}}

3区快速排序

快速排序面对重复的元素时的处理方法是，把它放在了左部分数组或右部分数组，下次进行分区时，还需检测它。如果需要排序的数组含有大量重复元素，则这个问题会造成性能浪费。

解决方法：新增一个相同区域，并把重复元素放进去，下次进行分区时，不对相同区域进行分区。

这就是3区快速排序，3区如下：

a[l…i] contains all elements smaller than pivota[i+1…j-1] contains all occurrences of pivota[j…r] contains all elements greater than pivot */

代码示例

import mons.lang3.tuple.Pair;public class SortExample{// Driver codepublic static void main(String args[]) {int[] arr = {1, 20, 4,4,4,6, 4, 5,2,3,1,8,2 };quickSort(arr,0,arr.length-1);printArray(arr);}static void quickSort(int a[], int l, int r) {if (r <= l) {return;}//返回相同区域左,右的边界-1Pair<Integer, Integer> pair = partition(a, l, r);quickSort(a, l, pair.getLeft());quickSort(a, pair.getRight(), r);}/* This function partitions a[] in three partsa) a[l..i] contains all elements smaller than pivotb) a[i+1..j-1] contains all occurrences of pivotc) a[j..r] contains all elements greater than pivot */static Pair<Integer, Integer> partition(int[] a, int l, int r) {int i = l - 1,j = r;int p = l - 1, q = r;int v = a[r];while (true) {// From left, find the first element greater than or equal to v. This loop will definitely terminate as v is last elementwhile (a[++i] < v) {// do nothing}// From right, find the first element larger than or equal to vwhile (v < a[--j]) {if (j == l) {break;}}// If i and j cross, then we are doneif (i >= j) {break;}// Swap, so that smaller goes on left greater goes on rightint temp = a[i];a[i] = a[j];a[j] = temp;// Move all same left occurrence of pivot to beginning of array and keep count using pif (a[i] == v) {p++;temp = a[i];a[i] = a[p];a[p] = temp;}// Move all same right occurrence of pivot to end of array and keep count using qif (a[j] == v) {q--;temp = a[q];a[q] = a[j];a[j] = temp;}}// Move pivot element to its correct indexint temp = a[i];a[i] = a[r];a[r] = temp;// Move all left same occurrences from beginning to adjacent to arr[i]j = i - 1;for (int k = l; k < p; k++, j--) {temp = a[k];a[k] = a[j];a[j] = temp;}// Move all right same occurrences from end to adjacent to arr[i]i = i + 1;for (int k = r - 1; k > q; k--, i++) {temp = a[i];a[i] = a[k];a[k] = temp;}return Pair.of(j,i);}/* A utility function to print array of size n */private static void printArray(int arr[]) {int n = arr.length;for (int i = 0; i < n; ++i) {System.out.print(arr[i] + " ");}System.out.println();}}