快捷導(dǎo)航

快速排序的原理及java代碼實(shí)現(xiàn)

更新時間：2016年02月02日 08:58:23 投稿：hebedich

網(wǎng)上關(guān)于快速排序的算法原理和算法實(shí)現(xiàn)都比較多，不過java是實(shí)現(xiàn)并不多，而且部分實(shí)現(xiàn)很難理解，和思路有點(diǎn)不搭調(diào)。所以整理了這篇文章。如果有不妥之處還請建議。

概述

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項(xiàng)目要Ο(nlogn)次比較。事實(shí)上，快速排序通常明顯比其他Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來，并且在大部分真實(shí)世界的數(shù)據(jù)，可以決定設(shè)計(jì)的選擇，減少所需時間的二次方項(xiàng)之可能性。

快速排序，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對這兩部分記錄繼續(xù)進(jìn)行排序,以達(dá)到整個序列有序的目的。

形象圖示：

步驟

選擇一個基準(zhǔn)元素，通常選擇第一個元素或者最后一個元素
通過一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的元素值均比基準(zhǔn)值大
此時基準(zhǔn)元素在其排好序后的正確位置
然后分別對這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個序列有序。

實(shí)例

原始數(shù)據(jù)：

3 5 2 6 2
選擇 3 作為基準(zhǔn)

第一輪

從右往左找比3小的，2符合，將2和3對調(diào)
2 5 2 6 3
對調(diào)一次，查找的方向反向，從左向右找比3大的，5符合，對調(diào)
2 3 2 6 5
再從右往左找比3小的，2符合，對調(diào)
2 2 3 6 5
一輪結(jié)束

第二輪

對 [2 2] 采用同上的方式進(jìn)行，得到
2 2 3 6 5

第三輪

對 [6 5] 采用同上的方式進(jìn)行，得到
2 2 3 5 6

最終結(jié)果

2 2 3 5 6

代碼實(shí)現(xiàn)(Java)

package com.coder4j.main.arithmetic.sorting;

public class Quick {

 private static int mark = 0;

 /**
  * 輔助交換方法
  * 
  * @param array
  * @param a
  * @param b
  */
 private static void swap(int[] array, int a, int b) {
  if (a != b) {
   int temp = array[a];
   array[a] = array[b];
   array[b] = temp;
   // 找到符合的，對調(diào)
   System.out.println("對調(diào)" + array[a] + "與" + array[b] + ",得到");
   for (int i : array) {
    System.out.print(i + " ");
   }
   System.out.println();
  }
 }

 /**
  * 新一輪分隔
  * 
  * @param array
  * @param low
  * @param high
  * @return
  */
 private static int partition(int array[], int low, int high) {
  int base = array[low];
  mark++;
  System.out.println("正在進(jìn)行第" + mark + "輪分隔，區(qū)域：" + low + "-" + high);
  while (low < high) {
   while (low < high && array[high] >= base) {
    high--;
    System.out.println("從右往左找比" + base + "小的，指針變動：" + low + "-" + high);
   }
   swap(array, low, high);
   while (low < high && array[low] <= base) {
    low++;
    System.out.println("從左往右找比" + base + "大的，指針變動：" + low + "-" + high);
   }
   swap(array, low, high);
  }
  return low;
 }

 /**
  * 對數(shù)組進(jìn)行快速排序，遞歸調(diào)用
  * 
  * @param array
  * @param low
  * @param heigh
  * @return
  */
 private static int[] quickSort(int[] array, int low, int heigh) {
  if (low < heigh) {
   int division = partition(array, low, heigh);
   quickSort(array, low, division - 1);
   quickSort(array, division + 1, heigh);
  }
  return array;
 }

 /**
  * 快排序
  * 
  * @param array
  * @return
  */
 public static int[] sort(int[] array) {
  return quickSort(array, 0, array.length - 1);
 }

 public static void main(String[] args) {
  int[] array = { 3, 5, 2, 6, 2 };
  int[] sorted = sort(array);
  System.out.println("最終結(jié)果");
  for (int i : sorted) {
   System.out.print(i + " ");
  }
 }

}

測試輸出結(jié)果：

全選復(fù)制放進(jìn)筆記正在進(jìn)行第1輪分隔，區(qū)域：0-4
對調(diào)2與3,得到
2 5 2 6 3 
從左往右找比3大的，指針變動：1-4
對調(diào)3與5,得到
2 3 2 6 5 
從右往左找比3小的，指針變動：1-3
從右往左找比3小的，指針變動：1-2
對調(diào)2與3,得到
2 2 3 6 5 
從左往右找比3大的，指針變動：2-2
正在進(jìn)行第2輪分隔，區(qū)域：0-1
從右往左找比2小的，指針變動：0-0
正在進(jìn)行第3輪分隔，區(qū)域：3-4
對調(diào)5與6,得到
2 2 3 5 6 
從左往右找比6大的，指針變動：4-4
最終結(jié)果
2 2 3 5 6

經(jīng)測試，與實(shí)例中結(jié)果一致。

您可能感興趣的文章: