教你JAVA语言快速排序的原理

　　快速排序（QuickSort ）是常用到的效率比较高的一种排序算法，在面试过程中也经常提及。下面就详细讲解一下他的原理、给出一个Java版本的实现。

　　快速排序思想：

　　通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序，直到独立的元素只有一个，此时整个元素集合有序。

　　快速排序的过程——挖坑填数法（这是一个很形象的名称），对一个元素集合R[ low ... high ] ,首先取一个数（一般是R[low] ）做参照，以R[low]为基准重新排列所有的元素。

　　所有比R[low]小的放前面，所有比R[low] 大的放后面，然后以R[low]为分界，对R[low ... high] 划分为两个子集和，再做划分。直到low >= high 。

　　比如：对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的过程如下(注:下面描述的`内容中元素下表从 0 开始)：

　　原始序列3740384246157912一：high-->low1240384246157912一：low --> high1240384246157940二：high-->low129384246157940二：low --> high1293842461573840三：high --> low129742461573840三：low -->high1297424615423840四：high --> low129754615423840四：low --> high12975461461423840一趟排序结果1297537461423840

　　开始选取基准 base = 37，初始位置下表 low = 0 ， high = 8 ，从high=8，开始如果R[8] < base , 将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;

　　从low开始探测，由于low=1 ， R[low] > base ,所以将R[low]写入到R[high] , high = high -1 ;

　　检测到low < high ,所以第一趟快速排序仍需继续:

　　此时low=1，high=7，因为 R[high] < base ,所以将 R[high] 写入到到R[low]中,low = low + 1;

　　从low开始探测,low = 2 , R[low] >base ,所以讲R[low]写入到R[high]，high=high-1;

　　继续检测到 low 小于high

　　此时low=2，high=6，同理R[high] < base ,将R[high] 写入到R[low]中，low=low+1;

　　从low继续探测,low = 3 , high=6 , R[low] > base , 将R[low]写入到R[high]中，high = high-1;

　　继续探测到low小于high

　　此时low=3，high=5，同理R[high] < base,将R[high]写入到R[low]中，low = low +1；

　　从low继续探测，low = 4，high=5，由于R[low] > base , 将R[low]写入到R[high]中，high = high -1 ;

　　此时探测到low == high == 4 ；该位置即是base所在的位置，将base写入到该位置中.

　　然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一个元素，或没有元素。

　　（注: 在以上表单中可以看到一趟排序中有一些重复的数据（原始数据中没有重复的数据），这是因为没有清除该位置的数据，我们在特定的时间看该内存块的数据依然是它，直到下一次将数据写入该位置位置 —— 在此该位置的数据是一个没有意义脏数据，称之为 “坑”）

　　快速排序的Java实现：

　　复制代码代码如下:

　　private static boolean isEmpty(int[] n) {

　　return n == null || n.length == 0;

　　}

　　// ///////////////////////////////////////////////////

　　/**

　　* 快速排序算法思想——挖坑填数方法：

　　* @param n 待排序的数组

　　public static void quickSort(int[] n) {

　　if (isEmpty(n))

　　return;

　　quickSort(n, 0, n.length - 1);

　　}

　　public static void quickSort(int[] n, int l, int h) {

　　if (isEmpty(n))

　　return;

　　if (l < h) {

　　int pivot = partion(n, l, h);

　　quickSort(n, l, pivot - 1);

　　quickSort(n, pivot + 1, h);

　　}

　　private static int partion(int[] n, int start, int end) {

　　int tmp = n[start];

　　while (start < end) {

　　while (n[end] >= tmp && start < end)

　　end--;

　　if (start < end) {

　　n[start++] = n[end];

　　}

　　while (n[start] < tmp && start < end)

　　start++;

　　if (start < end) {

　　n[end--] = n[start];

　　}

　　n[start] = tmp;

　　return start;

　　}

　　在代码中有这样一个函数：

　　复制代码代码如下:

　　public static void quickSortSwap(int[] n, int l, int h)

　　该函数可以实现，元素集合中特定的 l 到 h 位置间的数据元素进行排序。

　　关于快速排序就写到这里了。

【教你JAVA语言快速排序的原理】相关文章：

冒泡排序的原理以及java代码实现12-02

C语言快速排序算法及代码10-06

冒泡排序算法原理及JAVA实现代码方法12-02

C语言中qsort快速排序使用实例10-03

C语言中使用快速排序算法对元素排序的实例10-02