算法篇——快速排序

Quicksort是对冒泡排序法的一种改进。由C. A. R. Hoare在1962年提出的。他的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

前两天看微软源码的时候无意间看到这个，打算深入了解一下。

快速排序法的基本原理就是，从数组中拿出一个数，以这个数为基数，将比它小的放在左边，比他大的放在右边，直到”基线”左边的数全部都比它小，基线右面的书全都比它大，以基线为分界，彻底将数组分离成两部分。然后这两部分以此类推重复上述操作。

为了不产生”阻断”现象，比如以下数组，设a0为基数，向后推移，a1比她小，那么把a1拿出来放在a[0]的位置，a[2]比它大，那么a[2]不动。问题出来了基线无法向下进行了，a[3]比它小，可是a[2]位置没动。故采取的左右进行的方式。

从右到左采取小的放左面，从左向右采取大的放右面，直到除基线以外的每个元素都与基线比较过，既左右进行的角标重合，这样就能合理分区了。演变过程如下图所示。

现在已经按照基线全部分开了，同时在基线两边分别分化出来两组数组，这两组数组也按照上述规则进行排序。这里可以用到一个递归。code如下。

public static void QuickSort(int[] nums, int left, int right)
{
   int num = nums[left];
   int x = left;
   int y = right;

   while (x < y)
   {
       //从右向左数，遇到比基线小的则将该较小的数填入左侧，并'遗留'右侧位置
       while (x < y)
       {
           if (nums[y] < num)
           {
               nums[x] = nums[y];
               x++;
               break;
           }
           y--;
       }
       //从左向右数，遇到比基线大的则将该较大的数值填入右侧，并'遗留'左侧位置
       //Ps:这时产生右侧位置则是上一个while循环遗留的位置
       while (x < y)
       {
　　　　　　　if (nums[x] > num)
           {
               nums[y] = nums[x];
               y--;
               break;
           }
           x++;
       }
   }
   //x=y既基线位置，将基数装入基线位置
   nums[x] = num;
   //左右数组分别递归
   //判断条件防止堆栈溢出 --比如该数组只有一个相同的数字
   if (x > 1)
       QuickSort(nums, 0, x - 1);
   if (x < right)
       QuickSort(nums, x + 1, right);
}