快速排序是目前应用最广泛的排序算法。但快速排序是一种不稳定的排序算法。
快速排序算法是C.R.A. Hoare于1962年提出的一种划分交换的方法,它采用分治法(divide and conquer)进行排序。其基本思想是任取待排序元素序列中的某个元素(例如取第一个元素)作为基准,按照该元素的排序码大小,将整个元素序列划分为左右两个子序列:左侧子序列中所有元素的排序码都小于基准元素的排序码,右侧子序列中所有元素的排序码都大于或等于基准元素的排序码,基准元素则排在这两个子序列中间(这也是该元素最终应安放的位置)。然后分别对这两个子序列重复施行上述方法,直到所有的元素都排在相应位置上为止。
/** * Created by xiu on 2018/10/17. */ public class QuickSort { public static void main(String[] args) { int[] data = {8,7,9,3,5,2,3,1}; quickSort(data, 0, data.length-1); for(int e:data){ System.out.print(e+" "); } } //快速排序算法 public static void quickSort(int[] data, int left, int right){ //pivot = data[left]是基准元素,排序结束后它的位置在pivotPos,把排序序列分成两部分 //排在它左边的元素都小于它,排在它右边的元素都大于等于它 if(left < right){ int pivotPos = partition(data, left, right); quickSort(data, left, pivotPos - 1); quickSort(data, pivotPos + 1,right); } } //一次划分算法 public static int partition(int[] data, int low, int high){ //pivotPos为(小于基准元素列表)的最后一个元素位置,pivotPos=low除外 //pivot为基准元素,取最左边元素 int pivotPos = low, pivot = data[low]; for(int i = low + 1; i <= high; i++){ if(data[i] < pivot){ pivotPos++; //小于基准的交换到左侧去 if(pivotPos != i){ int temp = data[pivotPos]; data[pivotPos] = data[i]; data[i] = temp; } } } //基准元素就位:将low位置元素(pivot)与pivotPos位置元素(小于基准元素列表的最后一个元素)交换位置 data[low] = data[pivotPos]; data[pivotPos] = pivot; return pivotPos; //返回基准元素位置 } }
划分过程如下图所示
函数QuickSort的平均计算时间也是O(nlog2n)。我们每次都选用序列的第一个元素作为比较的基准元素。这样的选择简单但不理想。在最坏的情况,即待排序元素序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,如图9.6所示。每次划分只得到一个比上一次少一个元素的子序列。
基本的快速排序算法,对于n较大的平均情况而言,快速排序是“快速”的,但是当n很小时,这种排序方法往往比其他简单排序方法还要慢。