从题目中可以发现，每个查询串最常为255个字节，1000万个字符串需要占用2.55G内存，因此无法把所有的字符串全部读入到内存中处理。对于这类型的题目，分治法是一个非常实用的方法。
   方法一：分治法
   对字符串设置一个hash函数，通过这个hash函数把字符串划分到更多更小的文件中，从而保证每个小文件中的字符串都可以直接被加载到内存中处理，然后求出每个文件中出现次数最多的10个字符串；最后通过一个小顶堆统计出所有文件中出现最多的10个字符串。
   从功能角度出发，这种方法是可行的，但是由于需要对文件遍历两遍，而且hash函数也需要被调用1000万次，所以性能不是很好，针对这道题的特殊性，下面介绍另外一种性能较好的方法。
   方法二：hash_map法
   虽然字符串的总数比较多，但是字符串的种类不超过300万个，因此可以考虑把所有字符串出现的次数保存在一个hash_map中(键为字符串，值为字符串出现的次数)。hash_map所需要的空间为300万*(255+4)=3M*259=777M(其中，4表示用来记录字符串出现次数的整数占用4个字节)。由此可见1G的内存空间是足够用的。基于以上的分析，本题的求解思路为：
   1)遍历字符串，如果字符串在hash_map中不存在，则直接存入hash_map中，键为这个字符串，值为1。如果字符串在hash_map中已经存在了，则把对应的值直接+1。这一步操作的时间复杂度为O(n)，其中n为字符串的数量。
   2)在第一步的基础上找出出现频率最高的10个字符串。可以通过小顶堆的方法来完成，遍历hash_map的前10个元素，并根据字符串出现的次数构建一个小顶堆，然后接着遍历hash_map，只要遍历到的字符串的出现次数大于堆顶字符串的出现次数，就用遍历的字符串替换堆顶的字符串，然后把对调整为小顶堆。
   3)对所有剩余的字符串都遍历一遍，遍历完成后堆中的10个字符串就是出现次数最多的字符串。这一步的时间复杂度为O(nlog₂¹⁰)。
   方法三：trie树法
   方法二中使用hash_map来统计每个字符串出现的次数。当这些字符串有大量相同前缀的时候，可以考虑使用trie树来统计字符串出现的次数。可以在树的结点中保存字符串出现的次数，0表示没有出现。具体的实现方法为，在遍历的时候，在trie树中查找，如果找到，则把结点中保存的字符串出现的次数加1，否则为这个字符串构建新的结点，构建完成后把叶子结点中字符串的出现次数设置为1。这样遍历完字符串后就可以知道每个字符串的出现次数，然后通过遍历这个树就可以找出出现次数最多的字符串。
   trie树经常被用来统计字符串的出现次数。它的另外一个大的用途就是字符串查找，判断是否有重复的字符串等。

[考点] 如何查询最热门的查询串

这个题目从本质上而言也是求解数据重复的问题，对于这类问题一般而言，首先会考虑位图法。对于本题而言，8位电话号码可以表示的范围为：0000 0000～9999 9999，如果用1bit表示一个号码，总共需要1亿个bit，总共需要大约100M的内存。
   通过上面的分析可知，这道题的主要思路为：申请一个位图并初始化为0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后，如果bit值为1则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。所以bit值为1的数量则为不同电话号码的个数。
   那么对于这道题而言，最核心的算法是如何确定电话号码对应的是位图中的哪一位。下面重点介绍这个转化的方法，这里使用下面的对应方法。
   00000000对应位图最后一位：0x0000……000001。
   00000001对应位图倒数第二位：0x0000……0000010(1向左移…位)。
   00000002对应位图倒数第三位：0x0000……0000100(1向左移2位)。
   00000012对应位图的倒数十三为：0x0000……0001 0000 0000 0000。
   通常而言位图都是通过一个整数数组来实现的(这里假设一个整数占用4个字节)。由此可以得出通过电话号码获取位图中对应位置的方法为(假设电话号码为P)：
   1)通过P/32就可以计算出该电话号码在bitmap数组的下标。(因为每个整数占用32bit，通过这个公式就可以确定这个电话号码需要移动多少个32位，也就是可以确定它对应的bit在数组中的位置。)
   2)通过P%32就可以计算出这个电话号码在这个整型数字中具体的bit的位置，也就是1这个数字对应的左移次数。因此可以通过这把1向左移P%32位然后把得到的值与这个数组中的值做或运算，这样就可以把这个电话号码在位图中对应的为设置为1。
   这个转换的操作可以通过一个非常简单的函数来实现：
   void phoneToBit(int phone)
   {
   bitmap[phone/(8*sizeof(int))]|=1＜＜(phone%(8*sizeof(int)));
   //bitmap表示申请的位图
   }

[考点] 如何统计不同电话号码的个数

如果这道题目没有内存大小的限制，可以把所有的数字排序后找出中位数，但是最好的排序算法的时间复杂度都是O(nlog₂ⁿ)(n为数字的个数)。这里介绍另外一种求解中位数的算法：双堆法。
   方法一：双堆法
   这个算法的主要思路是维护两个堆，一个大顶堆，一个小顶堆，且这两个堆需要满足如下两个特性：
   特性一：大顶堆中最大的数值小于等于小顶堆中最小的数。
   特性二：保证这两个堆中的元素个数的差不能超过1。
   当数据总数为偶数的时候，当这两个堆建立好以后，中位数显然就是两个堆顶元素的平均值。当数据总数为奇数的时候，根据两个堆的大小，中位数一定在数据多的堆的堆顶。对于本题而言，具体实现思路为：维护两个堆maxHeap与minHeap，这两个堆的大小分别为max_size和min_size。然后开始遍历数字。对于遍历到的数字data：
   1)如果data＜maxHeap的堆顶元素，此时为了满足特性1，只能把data插入到maxHeap中。为了满足特性二，需要分以下几种情况讨论。
   ①如果max_size＜=min_size，说明大顶堆元素个数小于小顶堆元素个数，此时把data直接插入大顶堆中，并把这个堆调整为大顶堆；
   ②如果max_size＞min_size，为了保持两个堆元素个数的差不超过1，此时需要把maxHeap堆顶的元素移动到minHeap中，接着把data插入到maxHeap中。同时通过对堆的调整分别让两个堆保持大顶堆与小顶堆的特性。
   2)如果maxHeap堆顶元素＜=data＜=minHeap堆顶元素，为了满足特性一，此时可以把data插入任意一个堆中，为了满足特性二，需要分以下几种情况讨论：
   ①如果max_size＜min_size，显然需要把data插入到maxHeap中；
   ②如果max_size＞min_size，显然需要把data插入到minHeap中；
   ③如果max_size==min_size，可以把data插入到任意一个堆中。
   3)如果data＞maxHeap的堆顶元素，此时为了满足特性一，只能把data插入到minHeap中。为了满足特性二，需要分以下几种情况讨论。
   ①如果max_size＞=min_size，那么把data插入到minHeap中；
   ②如果max_size＜min_size，那么需要把minHeap堆顶元素移到maxHeap中，然后把data插入到minHeap中。
   通过上述方法可以把5亿个数构建两个堆，两个堆顶元素的平均值就是中位数。
   这种方法由于需要把所有的数据都加载到内存中，当数据量很大的时候，由于无法把数据一次性加载到内存中，因此这种方法比较适用于数据量小的情况。对于本题而言，5亿个数字，每个数字在内存中占4B，5亿个数字需要的内存空间为2GB内存。如果可用的内存不足2G的时候显然不能使用这种方法，因此下面介绍另外一种方法。
   方法二：分治法
   分治法的核心思想为把一个大的问题逐渐转换为规模较小的问题来求解。对于本题而言，顺序读取这5亿个数字；
   1)对于读取到的数字num，如果它对应的二进制中最高位为1则把这个数字写入到f1中，如果最高位是0则写入到f0中。通过这一步就可以把这5亿个数字划分成了两部分，而且f0中的数字都大于f1中的数字(因为最高位是符号位)。
   2)通过上而的划分町以非常容易地知道中位数是在f0中还是在f1中，假设f1中有1亿个数，那么中位数一定在文件f0中从小到大是第1.5亿个数与它后面的一个数求平均值。
   3)对于f0可以用次高位的二进制的值继续把这个文件一分为二，使用同样的思路可以确定中位数是哪个文件中的第几个数。直到划分后的文件可以被加载到内存的时候，把数据加载到内存中以后排序，从而找出中位数。
   需要注意的是，这里有一种特殊情况需要考虑，当数据总数为偶数的时候，如果把文件一分为二后发现两个文件中的数据有相同的个数，那么中位数就是数据总数小的文件中的最大值与数据总数大的文件中的最小值的平均值。对于求一个文件中所有数据的最大值或最小值，可以使用前面介绍的分治法进行求解。

[考点] 如何从5亿个数中找出中位数

对于这种题，如果query的重复度比较大，可以考虑一次性把所有query读入到内存中处理，如果query的重复率不高，可用的内存不足以容纳所有的query，那么就需要使用分治法或者其他的方法来解决。
   方法一：hash_map法
   如果query的重复率比较高，说明不同的query总数比较小，可以考虑把所有的query都加载到内存中的hash_map中(由于hash_map中针对每个不同的query只保存一个键值对，因此这些query占用的空间会远小于10G，有希望把它们一次性都加载到内存中)。接着就可以对hash_map按照query出现的次数进行排序。
   方法二：分治法
   这种方法需要根据数据量的大小以及可用内存的大小来确定问题划分的规模。对于本题而言，可以顺序遍历10个文件中的query，通过hash函数hash(query)%10把这些query划分到10个文件中，通过这样的划分，每个文件的大小为1G左右，当然可以根据实际情况来调整hash函数，如果可用内存很小，可以把这些query划分到更多的小的文件中。
   如果划分后的文件还是比较大，可以使用相同的方法继续划分，直到每个文件都可以被读取到内存中进行处理为止，然后对每个划分后的小文件使用hash_map统计每个query出现的次数，然后根据出现次数排序，并把排序好的query以及出现次数写入到另外一个单独的文件中。这样针对每个文件，都可以得到一个按照query出现次数排序的文件。
   接着对所有的文件按照query的出现次数进行排序，这里可以使用归并排序(由于无法把所有的query都读入到内存中，因此这里需要使用外排序)。

[考点] 如何按照query的频度排序

对于求top k的问题，最常用的方法为堆排序方法。对于本题而言，假设数组降序排列，可以采用如下方法：
   1)首先建立大顶堆，堆的大小为数组的个数，即20，把每个数组最大的值(数组第一个值)存放到堆中。
   2)接着删除堆顶元素，保存到另外一个大小为500的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。
   3)重复第1)、2)个步骤，直到删除个数为最大的K个数，这里为500。
   为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法(比较指针指向的值)。为了便于理解，把题目进行简化：三个数组，每个数组有5个元素且有序，找出排名前5的数。
   public class DataWithSource:IComparable＜DataWithSource＞
   {
   //数据
   public int Value{get; set;}
   //来源的数组
   public int ComeFrom{get; set;}
   //在数组中的index
   public int Index {get; set;}
   

   public DataWithSource(int value, int comeFrom, int index)
   {
   this.Value=value;
   this.ComeFrom=comeFrom;
   this.Index=index;
   }
   

   //
   //由于 PriorityQueue使用小顶堆来实现的。这里通过修改
   //两个整数比较的逻辑来让 PriorityQueue变为一个大顶堆
   //
   public int CompareTo(DataWithSource o)
   {
   if (this.Value＞o.Value)
   return-1;
   else if (this.Value＜o.Value)
   return 1;
   else
   return 0;
   }
   }
   

   //＜summary＞
   //优先队列
   //＜/summary＞
   //＜typeparam name="T"＞＜/typeparam＞
   public class PriorityQueue＜T＞
   {
   IComparer＜T＞ comparer;
   T[] heap;
   

   public int Count {get; private set;}
   

   public PriorityQueue(): this(null) {}
   public PriorityQueue(int capacity):this(capacity, null) { }
   public PriorityQueue(IComparer＜T＞ comparer): this(16, comparer) { }
   

   public PriorityQueue(int capacity, IComparer＜T＞ comparer)
   {
   this.comparer=(comparer==null)?Comparer＜T＞.Default: comparer;
   this.heap=new T[capacity];
   }
   

   public void Push(T v)
   {
   if (Count＞=heap.Length) Array.Resize(ref heap, Count *2);
   heap[Count]=v;
   SiftUp(Count++);
   }
   

   public T Pop()
   {
   var v=Top();
   heap[0]=heap[--Count];
   if(Count＞0)SiftDown(0);
   return v;
   }
   

   public T Top()
   {
   if(Count＞0)return heap[0];
   throw new InvalidOperationException("优先队列为空");
   }
   

   void SiftUp(int n)
   {
   varv=heap[n];
   for(var n2=n/2;n＞0＆＆comparer.Compare(v, heap[n2])＞0;n=n2, n2/=2)heap[n]=heap[n2];
   heap[n]=v;
   }
   

   void SiftDown(int n)
   {
   varv=heap[n];
   for(var n2=n*2;n2＜Count;n=n2, n2*=2)
   {
   if(n2+1＜Count＆＆comparer.Compare(heap[n2+1],heap[n2])＞0)n2++;
   if(comparer.Compare(v, heap[n2])＞=0)break;
   heap[n]=heap[n2];
   }
   heap[n]=v;
   }
   }
   

   class Test
   {
   public static int[] getTop(int[][] data)
   {
   int rowSize=data.Length;
   int columnSize=data[0].Length;
   int[] result3=new int[columnSize];
   //保持一个最小堆, 这个堆存放来自20个数组的最小数
   PriorityQueue＜DataWithSource＞heap=new PriorityQueue＜DataWithSource＞();
   for(inti=0:i＜rowSize; i++)
   {
   //记录下来源那个数组, 以及在数组中的index
   DataWithSource d=new DataWithSource(data[i][0],i, 0);
   heap.Push(d);
   }
   

   int num=0;
   while(num＜columnSize)
   {
   //删除顶点元素
   DataWithSource d=heap.Pop();
   result3[num++]=d.Value;
   

   if(num＞=columnSize)
   {
   break;
   }
   //将value置为该数原数组里的下一个数
   d.Value=data[d.ComeFrom][d.Index+1];
   

   //将其在数组中的index+1
   d.Index=(d.Index+1);
   heap.Push(d);
   }
   return result3;
   }
   

   public static void Main(String[] args)
   {
   int[][] data={new int[]{29,17,14,2,1},new int[]{19,17,16,15,6},new int[]{30,25,20,14,5}};
   Console.WriteLine(string.Join(" ",getTop(data)));
   Console.Read();
   }
   }
   程序的运行结果为
   30 29 25 20 19
   通过把ROWS改成20，COLS改成50，并构造相应的数组，就能实现题目的要求。对于降序排列的数组，实现方式类似，只不过是从数组的最后一个元素开始遍历。

[考点] 如何找出排名前500的数

选择排序是一种简单直观的排序算法，它的基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。以数组{38,65,97,76,13,27,49}为例，具体步骤如下：
   第一趟排序后：13 [65 97 76 38 27 49]
   第二趟排序后：13 27 [97 76 38 65 49]
   第三趟排序后：13 27 38 [76 97 65 49]
   第四趟排序后：13 27 38 49 [97 65 76]
   第五趟排序后：13 27 38 49 65 [97 76]
   第六趟排序后：13 27 38 49 65 76 [97]
   最后排序结果：13 27 38 49 65 76 97
   程序示例如下：
   public class TestSort
   {
   public static void selectSort(int[]a)
   {
   int i;
   int j;
   int temp=0;
   int flag=0;
   int n=a.Length;
   for(i=0;i＜n;i++)
   {
   temp=a[i];
   flag=i;
   for(j=i+1;j＜n;j++)
   {
   if(a[j]＜temp)
   {
   temp=a[j];
   flag=j;
   }
   }
   if (flag!=i)
   {
   a[flag]=a[i];
   a[i]=temp;
   }
   }
   }
   public static void Main(String[] args)
   {
   int i=0;
   int[]a={5,4,9,8,7,6,0,1,3,2};
   selectSort(a);
   for(i=0; i＜a.Length; i++)
   {
   Console.Write(a[i].ToString()+"");
   }
   }
   }
   程序运行结果为：
   0 1 2 3 4 5 6 7 8 9

[考点] 如何进行选择排序

对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。以数组{38,65,97,76,13,27,49}为例，直接插入排序具体步骤如下所示。
   第一步插入38以后：[38] 65 97 76 13 27 49
   第二步插入65以后：[38 65] 97 76 13 27 49
   第三步插入97以后：[38 65 97] 76 13 27 49
   第四步插入76以后：[38 65 76 97] 13 27 49
   第五步插入13以后：[13 38 65 76 97] 27 49
   第六步插入27以后：[13 27 38 65 76 97] 49
   第七步插入49以后：[13 27 38 49 65 76 97]
   程序示例如下：
   public class TestSort
   {
   public static void insertSort(int[]a)
   {
   if(a!=null)
   {
   for (int i=1; i＜a.Length; i++)
   {
   int temp=a[i],j= i;
   if(a[j-1]＞temp)
   {
   while(j＞=1 ＆＆ a[j-1]＞temp)
   {
   a[j]=a[j-1];
   j--;
   }
   }
   a[j]=temp;
   }
   }
   }
   public static void Main(String[] args)
   {
   int[] array={7, 3, 19, 40, 4, 7, 1};
   insertSort(array);
   for(int i=0; i＜array.Length; i++)
   {
   Console.Write(array[i].ToString()+" ");
   }
   }
   }
   程序运行结果为：
   1 3 4 7 7 19 40

[考点] 如何进行插入排序

冒泡排序顾名思义就是整个过程就像气泡一样往上升，单向冒泡排序的基本思想是(假设由小到大排序)：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换其位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前(n-1)个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个时为止。
   以数组{36,25,48,12,25,65,43,57}为例，具体排序过程如下：
   一趟排序的过程如下：
   R[1]36　　25　　25　　25　　25　　25　　25　　25
   R[2]25　　36　　36　　36　　36　　36　　36　　36
   R[3]48　　48　　48　　12　　12　　12　　12　　12
   R[4]12　　12　　12　　48　　25　　25　　25　　25
   R[5]25　　25　　25　　25　　48　　48　　48　　48
   R[6]65　　65　　65　　65　　65　　65　　43　　43
   R[7]43　　43　　43　　43　　43　　43　　65　　57
   R[8]57　　57　　57　　57　　57　　57　　57　　65
   则经过多趟排序后的结果如下所示：
   初始状态：[36 25 48 12 25 65 43 57]
   1趟排序：[25 36 12 25 48 43 57 65]
   2趟排序：[25 12 25 36 43 48] 57 65
   3趟排序：[12 25 25 36 43] 48 57 65
   4趟排序：[12 25 25 36] 43 48 57 65
   5趟排序：[12 25 25] 36 43 48 57 65
   6趟排序：[12 25] 25 36 43 48 57 65
   7趟排序：[12] 25 25 36 43 48 57 65
   程序示例如下：
   public class Test
   {
   public static void BubbleSort(int[] array)
   {
   inti,j;
   int len=array.Length;
   int tmp;
   for(i=0;i＜len-1;++i)
   for(j=len-1;j＞i;--j)
   if(array[j]＜array[j-1])
   {
   tmp=array[j];
   array[j]=array[j-1];
   array[j-1]=tmp;
   }
   }
   public static void Main(String[] args)
   {
   int[]a={5,4,9,8,7,6,0,1,3,2};
   BubbleSort(a);
   for(int i=0;i＜a.Length; i++)
   {
   Console.Write(a[i].ToString()+"");
   }
   }
   }
   程序输出为：
   0 1 2 3 4 5 6 7 8 9

[考点] 如何进行冒泡排序

归并排序是利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。归并排序中，“归”代表的是递归的意思，即递归的将数组折半的分离为单个数组，例如数组：[2，6，1，0]，会先折半，分为[2，6]和[1，0]两个子数组，然后再折半将数组分离，分为[2]，[6]和[1]，[0]。“并”就是将分开的数据按照从小到大或者从大到小的顺序在放到一个数组中。如上面的[2]，[6]合并到一个数组中是[2，6]，[1]，[0]合并到一个数组中是[0，1]，然后再将[2，6]和[0，1]合并到一个数组中即为[0，1，2，6]。
   具体而言，归并排序算法的原理如下：对于给定的一组记录(假设共有n个记录)，首先将每两个相邻的长度为1的子序列进行归并，得到n/2(向上取整)个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。
   所以，归并排序的关键就是两步：第一步，划分子表；第二步，合并半子表。以数组{49，38，65，97，76，13，27}为例，排序过程如下：
   
   程序示例如下所示：
   以数组{5,4,9,8,7,6,0,1,3,2}为例，归并排序
   public class TestSort
   {
   public static void Merge(int[] array, int p, int q, int r)
   {
   inti,j,k,n1,n2;
   n1=q-p+1;
   n2=r-q;
   int[]L=new int[n1];
   int[]R=new int[n2];
   for(i=0,k=p;i＜n1;i++,k+)
   L[i]=array[k];
   for(i=0,k=q+1;i＜n2;i++,k++)
   R[i]=array[k];
   for(k=p,i=0,j=0;i＜n1 ＆＆ j＜n2; k++)
   {
   if(L[i]＞R[j])
   {
   array[k]=L[i];
   i++;
   }
   else
   {
   array[k]=R[j];
   j++;
   }
   }
   if(i＜n1)
   {
   for(j=i;j＜n1; j++, k++)
   array[k]=L[j];
   }
   if(j＜n2)
   {
   for(i=j;i＜n2;i++,k++)
   array[k]=R[i];
   }
   }
   public static void MergeSort(int[] array, int p, int r)
   {
   if(p＜r)
   {
   intq=(p+r)/2;
   MergeSort(array,p,q);
   MergeSort(array,q+1,r);
   Merge(array,p,q,r);
   }
   }
   public static void Main (String[] args)
   {
   int i=0;
   int[]a={5,4,9,8,7,6,0,1,3,2};
   int len=a.Length;
   MergeSort(a,0,len-1);
   for(i=0;i＜len;i++)
   {
   Console.Write(a[i]+"");
   }
   }
   }
   程序输出为：
   9 8 7 6 5 4 3 2 1 0
   二路归并排序的过程需要进行logn趟。每一趟归并排序的操作，就是将两个有序子序列进行归并，而每一对有序子序列归并时，记录的比较次数均小于等于记录的移动次数，记录移动的次数均等于文件中记录的个数n，即每一趟归并的时间复杂度为O(n)。因此，二路归并排序的时间复杂度为O(nlog₂ⁿ)。

[考点] 如何进行归并排序

快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。其原理如下：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
   具体而言，算法步骤如下：
   1)分解：将输入的序列array[m..n]划分成两个非空子序列array[m…k]和array[k+1…n]，使array[m…k]中任一元素的值不大于array[k+1…n]中任一元素的值。
   2)递归求解：通过递归调用快速排序算法分别对array[m…k]和array[k+1…n]进行排序。
   3)合并：由于对分解出的两个子序列的排序是就地进行的，所以在array[m…k]和array[k+1…n]都排好序后不需要执行任何计算array[m…n]就已排好序。
   以数组{38，65，97，76，13，27，49}为例。
   第一趟排序过程如下：
   初始化关键字[49 38 65 97 76 13 27 49]
   第一次交换后：[27 38 65 97 76 13 49 49]
   第二次交换后：[27 38 49 97 76 13 65 49]
   j向左扫描，位置不变，第三次交换后：[27 38 13 97 76 49 65 49]
   i向右扫描，位置不变，第四次交换后：[27 38 13 49 76 97 65 49]
   j向左扫描[27 38 13 49 76 97 65 49]
   整个排序过程如下所示：
   初始化关键字[49 38 65 97 76 13 27 49]
   一趟排序之后：[27 38 13] 49 [76 97 65 49]
   二趟排序之后：[13] 27 [38] 49 [49 65]76 [97]
   三趟排序之后：  13 27 38 49 49 [65]76 97
   最后的排序结果：13 27 38 49 49 65 76 97
   程序示例如下：
   public class Test
   {
   public static void sort(int[] array, int low, int high)
   {
   int i,j;
   int index;
   if(low＞=high)
   return;
   i=low;
   j=high;
   index=array[i];
   while(i＜j)
   {
   while(i＜j＆＆array[j]＞=index)
   j--;
   if(i＜j)
   array[i++]=array[j];
   while(i＜j＆＆array[i]＜index)
   i++;
   if(i＜j)
   array[j--]=array[i];
   }
   array[i]=index;
   sort(array,low,i-1);
   sort(array,i+1,high);
   }
   public static void quickSort(int[] array)
   {
   sort(array,0, array.Length-1);
   }
   public static void Main(String[] args)
   {
   int i=0;
   int[] a={5,4,9,8,7,6,0,1,3,2};
   int len=a.Length;
   quickSort(a);
   for(i=0;i＜len; i++)
   {
   Console.Write(a[i]+"");
   }
   }
   }
   程序输出为：
   0 1 2 3 4 5 6 7 8 9
   当初始的序列整体或局部有序时，快速排序的性能将会下降，此时，快速排序将退化为冒泡排序。
   快速排序的相关特点如下：
   (1)最坏时间复杂度
   最坏情况是指每次区间划分的结果都是基准关键字的左边(或右边)序列为空，而另一边的区间中的记录项仅比排序前少了一项，即选择的基准关键字是待排序的所有记录中最小或者最大的。例如，如果选取第一个记录为基准关键字，当初始序列按递增顺序排列时，每次选择的基准关键字都是所有记录中的最小者，这时记录与基准关键字的比较次数会增多。因此，在这种情况下，需要进行(n-1)次区间划分。对于第k(0＜k＜n)次区间划分，划分前的序列长度为(n-k+1)，需要进行(n-k)次记录的比较。因此，当k从1到(n-1)时，进行的比较次数总共为n(n-1)/2，所以，在最坏情况下快速排序的时间复杂度为O(n)。
   (2)最好时间复杂度
   最好情况是指每次区间划分的结果都是基准关键字左右两边的序列长度相等或者相差为1，即选择的基准关键字为待排序的记录中的中间值。此时，进行的比较次数总共为nlogn，所以，在最好情况下快速排序的时间复杂度为
   (3)平均时间复杂度
   快速排序的平均时间复杂度为。虽然快速排序在最坏情况下的时间复杂度为O(n²)，但是在所有平均时间复杂度为的算法中，快速排序的平均性能是最好的。
   (4)空间复杂度
   快速排序的过程中需要一个栈空间来实现递归。当每次对区间的划分都比较均匀时(即最好情况)，递归树的最大深度为(logn为向上取整)；当每次区间划分都使得有一边的序列长度为0时(即最好情况)，递归树的最大深度为n。在每轮排序结束后比较基准关键字左右的记录个数，对记录多的一边先进行排序，此时，栈的最大深度可降为。因此，快速排序的平均空间复杂度为。
   (5)基准关键字的选取
   基准关键字的选择是决定快速排序算法性能的关键。常用的基准关键字的选择有以下方式：
   1)三者取中。三者取中是指在当前序列中，将其首、尾和中间位置上的记录进行比较，选择三者的中值作为基准关键字，在划分开始前交换序列中的第一个记录与基准关键字的位置。
   2)取随机数。取left(左边)和right(右边)之间的一个随机数m(left≤m≤right)，用n[m]作为基准关键字。这种方法使得n[left]到n[right]之间的记录是随机分布的，采用此方法得到的快速排序一般称为随机的快速排序。
   需要注意一个问题，就是快速排序与归并排序的区别与联系。快速排序与归并排序的原理都是基于分治思想，即首先把待排序的元素分成两组，然后分别对这两组排序，最后把两组结果合并起来。
   而它们的不同点在于，进行的分组策略不同，后面的合并策略也不同。归并排序的分组策略是假设待排序的元素存放在数组中，那么其把数组前面一半元素作为一组，后面一半作为另外一组。而快速排序则是根据元素的值来分组，即大于某个值的元素放在一组，而小于的放在另外一组，该值称为基准。所以，对整个排序过程而言，基准值的挑选非常重要，如果选择不合适，太大或太小，那么所有的元素都分在一组了。总的来说，快速和归并排序，如果分组策略越简单，则后面的合并策略就越复杂，因为快速排序在分组时，已经根据元素大小来分组了，而合并的时候，只需把两个分组合并起来就行了，归并排序则需要对两个有序的数组根据大小合并。

[考点] 如何进行快速排序