Quicksort（快速排序）

时间：2010-08-26 来源：chen202052428

   Quicksort算法采用了分而制之（divide-and-conquer）的概念，这中思想的策略是将问题划分为子问题，每个问题是独立的，可以单独进行求解，然后使用递归的思想再将问题划分为孙问题，直到问题的答案显而易见（即被征服了）。
    在快速排序算法中，选取某个称为基准（pivot）的元素，然后对数组进行排序，将小于基准的元素排在基准的前面，将大于基准的元素排在基准的后面；这样一来，也就确定了基准的位置，然后将小数的子序列按同样的方法进行排序，直到子序列中只有一个元素。
    快速算法的C语言实现如下所示，程序的目的是将数组由小到大排序(可以通过改变 if(array[l] >= array[i])中的符号来改变顺序，将其改为<则按由大到小排)
    void quicksort(int *array, int l, int u)
{
int i, m;
if(l>=u) return ;
swap(array+l, array + randint(l+1,u));

m = l;
for(i=l+1; i<=u; i++)
{
  if(array[l] >= array[i])
   swap(array + (++m), array+i);
} swap(array+l, array+m); quicksort(array, l, m-1);
quicksort(array, m+1, u); }
    在上述代码中，l是带排序数组的下标，u是待排序数组的上标。程序中，将待排序的第一个元素作为基准，之所以先将第一个元素与中间随机的一个元素相交换，目的在于避免最坏的情况，即加入数组时反序的，那么在第一次排序后，元素基本上集中在基准的一边，会出现另一边为空的现象，采用上述方法可以很好的避免这种现象的产生。取基准的方法并不唯一，也有从第一个，中间一个，最后一个这3个数中取值中间的那个。
    由于以第一个元素作为基准，所以交换从第二个元素开始，将小于基准的元素往前排。m其实指向的是大于基准的元素（因为大于的时候不会交换，也就是说m指向第一个大于基准大数的前一个数，m不可能比基准大，因为每次交换都是将大数和++m交换，也就是每次m指向的都是小数），当扫描完整个数组后，m指向的是最后一个小数（假如中间还有小数的话，那么还会进行交换），将m与基准值交换，就订好基准的位置，使得在左的都是小于基准的，在右的都是大于基准的。 void swap(int *a, int *b)
{
if(a == b)
  return;
*a = *a ^ *b ;
*b = *b ^ *a ;
*a = *a ^ *b ;
}
    上述代码中，很关键的一点是判断a和b是否是指向同一个数（不是值相同），假如是指向同一个数时，还用代码中的交换方法，则结果会变为0（异或相同则为0）。 int randint(int min, int max)
{
if(max>min)
    return (min + (rand()%(max-min)));
return 0;
}
    排序算法有许多种，因此各种排序算法都有其使用范围，Quicksort的使用范围是对于那些>=20的长表，性能表现优