算法分析之快速排序

一.快速排序基本特性


平均时间复杂度：O(n*lgn)
最坏时间复杂度：O(n^2)
空间复杂度：O(n*lgn)
不稳定



二.快速排序描诉

快速排序是基于分治思想的一种排序算法。
对于一个典型的数组A[n]的排序思路是：

1.分解
把数组分为A[0~k-1]和A[k+1~n]使得前一半数据小于A[K],后一半数据大于A[K]

2.递归
递归调用快速排序对两半数组进行快速排序。

3.合并

如果只说分治思想不好理解，我们还可以说是一种挖坑+分治的思想。在排序过程中不断挖坑
，然后填补！

例子：
原始数据：{2,8,7,1,3,5,6,4}

第一步以数组第一个元素为分割点，在此处为：2
i游标从前往后走找比标准值大的，j游标从后往前走找比标准值小的

找比2小的数据，用j游标从后往前找，直到j指向1时，找到符合条件的数据。

OK！我们挖坑，把2挖掉，用1填坑，自然1所在的位置被挖坑。

现在数据变成了{ 1,8,7, ,3,5,6,4}
i=0;j=3

第二步
改用i游标从前往后找比2大的数，知道i指向8  OK！
把8填到刚挖的坑上。
现在数据变成了{1, ,7,8,3,5,6,4}
i=1;j=3

由于i<j继续
继续用J游标从后往前找比2小的数，直到j=i时。
完成了一趟快速排序。

把2填回。
数据变为：{1,2,7,8,3,5,6,4}

OK我们完成了一趟快速排序。

这是网上找的一个这个版本的快速排序：
思想是一样的
/**************************************************/
/*  函数功能：快速排序算法                        */
/*  函数参数：结构类型table的指针变量tab          */
/*            整型变量left和right左右边界的下标   */
/*  函数返回值：空                                */
/*  文件名：quicsort.c  函数名：quicksort ()      */
/**************************************************/
void quicksort(table *tab,int left,int right)
{
  int i,j;
  if(left<right)
  {
    i=left;j=right;
    tab->r[0]=tab->r[i]; //准备以本次最左边的元素值为标准进行划分，先保存其值
    do
    {
      while(tab->r[j].key>tab->r[0].key&&i<j)
        j--;        //从右向左找第1个小于标准值的位置j
      if(i<j)                               //找到了，位置为j
      {
        tab->r[i].key=tab->r[j].key;i++;
      }           //将第j个元素置于左端并重置i
      while(tab->r[i].key<tab->r[0].key&&i<j)
        i++;      //从左向右找第1个大于标准值的位置i
      if(i<j)                       //找到了，位置为i
      {
        tab->r[j].key=tab->r[i].key;j--;
      }           //将第i个元素置于右端并重置j
    }while(i!=j);

    tab->r[i]=tab->r[0];         //将标准值放入它的最终位置,本次划分结束
    quicksort(tab,left,i-1);     //对标准值左半部递归调用本函数
    quicksort(tab,i+1,right);    //对标准值右半部递归调用本函数
  }
}