有意思的排序算法快速排序
快速排序对于含有n个元素的数组，最坏情况的运行时间为O(n 2 )，虽然这个最坏情况的运行时间比较差，但是快速排序通常是用于排序的最佳的实用选择，这是因为其平均性能相当好，而且我们可以采用随机化的快速排序算法，来减少出现最坏情况的机会，其期望运行时间为O(nlgn)，而且该记号中含的常数因子很小。
像合并排序算法一样，快速排序也是基于分治法进行排序的。其排序过程分为三个步骤：
分解 ：数组A[p..r]被划分为两个（可能空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A(q)，而且小于等于A[q+1..r]中的元素。下标q也在这个划分过程中计算。
解决 ：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序。
合并 ：因为两个子数组是就地排序的，将它们合并不需要操作：整个数组A[p..r]已排序。
Java实现为：
1 import java.util.Random;
2
3 public class QuickSort implements SortAlgorithm {
4
5 private Random rand = null ;
6
7 public QuickSort() {
8 rand = new Random();
9 }
10
11 @Override
12 public void sort( int [] A) {
13 randomizedQuickSort(A, 1, A.length, true );
14 }
15
16 @Override
17 public void sort( int [] A, boolean isInc) {
18 randomizedQuickSort(A, 1 , A.length, isInc);
19 }
20
21 /**
22 * 随机化的快速排序
23 * @param A 要排序的int数组
24 * @param p 起始位置
25 * @param r 终止位置
26 * @param isInc 是否升序，true为升序，false为降序
27 */
28 private void randomizedQuickSort( int [] A, int p, int r, boolean isInc) {
29 if (p < r) {
30 int q = randomizedPartition(A, p, r, isInc);
31 randomizedQuickSort(A, p, q - 1 , isInc);
32 randomizedQuickSort(A, q + 1 , r, isInc);
33 }
34 }
35
36 /**
37 * 随机化的对数组的划分
38 * @param A 要划分的int数组
39 * @param p 起始位置
40 * @param r 终止位置
41 * @param isInc 是否升序，true为升序，false为降序
42 * @return 划分数组的下标
43 */
44 private int randomizedPartition( int [] A, int p, int r, boolean isInc) {
45 int i = rand.nextInt(r - p);
46 exchange(A, r, i + p);
47 return partition(A, p, r, isInc);
48 }
49
50 /**
51 * 对数组进行划分
52 * @param A 要划分的int数组
53 * @param p 起始位置
54 * @param r 终止位置
55 * @param isInc 是否升序，true为升序，false为降序
56 * @return 划分数组的下标
57 */
58 private int partition( int [] A, int p, int r, boolean isInc) {
59 int x = A[r - 1 ];
60 int i = p - 1 ;
61 for ( int j = p; j <= r - 1; j++ ) {
62 if (isInc ? A[j - 1] <= x : A[j - 1] >= x) {
63 i++ ;
64 exchange(A, i, j);
65 }
66 }
67 exchange(A, i + 1 , r);
68 return i + 1 ;
69 }
70
71 private void exchange( int [] A, int i, int j) {
72 int temp = A[i - 1 ];
73 A[i - 1] = A[j - 1 ];
74 A[j - 1] = temp;
75 }
76 }
到此为止，写完了比较排序的几种最常用的排序算法，不对的地方，请大家批评指正。
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did49193