快速排序-qsort

有几点记录一下：

1.快速排序的时间复杂度是nlogn，推到《数据结构》上有，看不懂。在记录为有序时，快速排序退化成冒泡排序。

2.注意是low跟high记录交换，而并非跟枢轴记录交换。前者才能保证low，high两部分的基本有序。只不过要注意，low，high记录交换后，low记录本身存在偶然性，即其跟枢轴记录的相对大小不确定。需要比较，然后做出交换动作，才能保证前后两个分支的基本有序，如下面绿色注释部分所指出的。

================2013/5/2更新===========================

Programming Pearls第11章，着重介绍了快速排序，其讲解的深度和算法的优美度都远大于严蔚敏的《数据结构》第十章所介绍的。挑一种比较基本的快速排序实现如下，并做一些笔记

// 解决了原先swap相同变量的问题

#define swap(a, b) \
     if (a!=b)\
     {\
          a = (a)+(b);\
          b = (a)-(b);\
          a = (a)-(b);\
     }

void qsort(int* L, int size)
{

          // 确保递归循环能结束，而非死循环
     if (size <= 1)
          return;

          // i,j可以理解为从两侧开始扫描，

          // while循环的目的是为了将数组转变为如下图

          // i变量为了找比t大的数，j变量为了找比t小的数

     int t = L[0];
     int i = 0, j = size; 
     while (1)
     {
          do
          {
               i ++;
          } while (i<size && L[i]<t);

                    // 此时i有两种可能：

          // 1）i==u, 2）x[i]>=t
          do
          {
               j --;
          } while (L[j]>t);

                    // 此时j只有一种可能：x[j]<=t

                    // 当i,j交叉时，说明整个数组扫描完毕
          if (i>j)
               break;
          swap (L[i], L[j]);
     }
     swap(L[0], L[j]);
     qsort(L, j);
     qsort(&L[j+1], size-1-j);
}

整个算法的关键是在那个while(1)循环，如何保证此循环可以正确的结束。

要保证正确，要保证以下三点：

     1. 循环结束后，j点左侧的都要小于t，j点右侧都要大于t

     2. 循环不变式是i <= j

     3. 保证在交换时，i、j没有交叉

============================================================

#include <stdio.h>
#include <time.h>

// 注意：不加{}，会影响到if分支
#define swap(a, b) \
{\
     a = (a)+(b);\
     b = (a)-(b);\
     a = (a)-(b);\
}
#define dim(a) (sizeof(a)/sizeof(a[0]))

void qsort(int* L, int size);

main()

{
     int i;
     int a[10] = {0};
     srand(time(NULL));
     for (i=0; i<dim(a); i++)
     {
          a[i] = rand() % 100;
     }
     qsort(a, dim(a));

     printf("a: ");
     for (i=0; i<dim(a); i++)
     {
          printf("%d ", a[i]);
     }
     printf("\n");
}

void qsort(int* L, int size)
{
     switch (size)
     {
          case 0:
               printf ("empty array is input.\n");
               return;
          case 1:
               printf ("input array has only 1 member.\n");
               return;
          case 2:
               if (L[0] > L[1])
               {
                    swap(L[0], L[1]);
               }
               return;
          default:
               break;
     }
    
     int low = 1, high = size - 1;
     while(low < high)
     {
          while (low<high && L[low] <= L[0])
          {
               low ++;
          }
          if (low != high)
               swap(L[low], L[high]);
          while (low<high && L[high] >= L[0])
          {
               high --;
          }
          if (low != high)
               swap(L[low], L[high]);
     }

         //////////////////////

     // 注意：这里low的位置存在随机性，《数据结构》中并没有注意到这点
     if (L[0] > L[low])
          swap(L[0], L[low])
     else if (L[0] < L[low])
     {
          low --;
          if (low != 0)
               swap(L[0], L[low])
     }

         //////////////////////

     qsort(L, low);
     if (low < size-1)
          qsort(&L[low+1], size-low-1);
}