1 using System;
 2  using System.Collections.Generic;
 3 
 4 namespace Com.Colobu.Algorithm.Exchange
 5 {
 6     /// <summary>
 7     /// <b>快速排序</b>是所有排序算法中最高效的一种.
 8     /// 它采用了分治的思想：先保证列表的前半部分都小于后半部分，
 9     /// 然后分别对前半部分和后半部分排序，这样整个列表就有序了。
10     /// 这是一种先进的思想，也是它高效的原因。
11     /// 因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，
12     /// 而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后
13     /// 都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。
14     /// 
15     /// 平均时间复杂度:O(nlogn)
16     /// Stability:No
17     /// </summary>
18     public class QuickSortAlgorithm
19     {
20         // QuickSort implementation
21         public static void QuickSort<T>(IList<T> szArray, int nLower, int nUpper) where T : IComparable
22         {
23             if (nLower < nUpper)
24             {
25                 int nSplit = Partition(szArray, nLower, nUpper);
26                 QuickSort(szArray, nLower, nSplit - 1);
27                 QuickSort(szArray, nSplit + 1, nUpper);
28             }
29         }
30         // QuickSort partition implementation
31         private static int Partition<T>(IList<T> szArray, int nLower, int nUpper) where T:IComparable
32         {
33             T szPivot = szArray[nLower]; //分隔点的值，用数字第一个值代替
34 
35             int nLeft = nLower + 1;//左边开始点
36             int nRight = nUpper; //右边开始点
37 
38             T szSwap; //交换变量
39 
40             //开始查找
41             //将小于分隔点的值都挪到左边
42             //将小于分隔点的值都挪到右边
43             while (nLeft <= nRight)
44             {
45                 //找到左边第一个大于分隔点的值
46                 while (nLeft <= nRight && szArray[nLeft].CompareTo(szPivot) <= 0)
47                     nLeft = nLeft + 1;
48 
49                 //找到右边第一个小于分隔点的值
50                 while (nLeft <= nRight && szArray[nRight].CompareTo(szPivot) > 0)
51                     nRight = nRight - 1;
52 
53                 //如果左右还没有交叉(碰头)，交换左右两个值
54                 if (nLeft < nRight)
55                 {
56                     szSwap = szArray[nLeft];
57                     szArray[nLeft] = szArray[nRight];
58                     szArray[nRight] = szSwap;
59                     nLeft = nLeft + 1;
60                     nRight = nRight - 1;
61                 }
62             }
63 
64             //将分隔点移动到最后那个点,此时nRight = nLeft - 1
65             //所以那个点的值小于分隔点，可以与分隔点进行交换
66             szSwap = szArray[nLower];
67             szArray[nLower] = szArray[nRight];
68             szArray[nRight] = szSwap;
69 
70             //现在在nRight左边的值都小于分隔点，nRight右边的值都大于分隔点
71             return nRight;
72         }
73 
74     }
75 }
76