数据结构-练习 13 快排

快速排序的思想是平常最常用的排序算法之一，因其平均复杂度为NlgN而著称，并且可以不借助其他空间。下面我们就来学习一下快排。

        看看原理吧。

        快速的排序采用了分而治之的思想。选取一个基元，分别与之比较，进行一次partition，再循环进行。

       原理图解如下：假设以6为基元，

                                  i,j俩个相当于指针，分别指示小于基元和大于基元的数。

      第一步：i指向3的前一个位置，j指向3，观察j指向的数与基元6的大小，小于则i++，然后i，j指向的数互换，j再++；相反，大于6，则i不变，j++。此处，i，j都指向3，互换      不变；

      第二步：如第2行，j指向的数是4，小于6，按上面的规则，此时，i++, i,j指向4，互换仍然不变，j++;

     第三步：如第三行，j指向的是9，大于6，j++;

     第四步：如第四行，j指向的是1，此时i指向4，i先++,i指向9,1和9互换，j++,如第6行；

     第五步：第六行，第七行，j指向的数均大于6，i不变，直至，基元的前一个位置。

     最后一步：i++,i指向的数和基元互换。如第九行。进行这一步的原因是：经过这五部的调整，基元调整到中间就可以把大于基元和小于基元的数分开。

    上面整个过程完成了一次PARTITION。

     然后再类似地对分组后的元素进行PARTITION。从而完成整个快速排序的过程。余下部分的排序过程如图所示，最后我们得到了从小到大的排序结果。

                   

 

 

 

 

   

                                            

 

 整个过程采用了：分治法，递归的思想。目前采用到分治和递归思想的排序有：归并，八皇后，树的遍历，图的遍历。

  接下来自然是 上代码了：

   //n是新的分组的大小，startLoc是新分组的起始位置。

void fastSort(int * inputData,int n,int startLoc)
{
  if(n<2) return ;//递归停止的条件
  int i=startLoc-1;//指向最后一个小于基元的数据
  int j=startLoc;//移动j，挨个遍历元素
  int baseDa=inputData[startLoc+n-1];//获取基元
  int tmp;
  int k=0;
  while(j<=startLoc+n-1)
  {
   if(inputData[j]<inputData[startLoc+n-1]||j==startLoc+n-1)
     {
      i++;
	  k++;
	  //交换
	  tmp=inputData[j];
	  inputData[j]=inputData[i];
	  inputData[i]=tmp;
	  
     }
    j++;
    }
  startLoc=i-k+1;//左边分组的位置，右边分组的位置为：i+1
  fastSort(inputData,i-startLoc,startLoc);
  fastSort(inputData,n-(i-startLoc)-1,i+1);
 
  
}

 测试:

int main()
{
//递归调用
  int a[11]={3,4,9,1,8,7,6,2,5,1,3};
 
 
  fastSort( a,11,0);
  for(int i=0;i<11;i++)
	  std::cout<<a[i]<<",";
 
 
	return 0;
}

结论：采用递归的思想，很容易混淆。注意三点：

1 ，递归的思想，一定是函数包含函数本身；

2，在函数里一定有其他代码，其作用当然是实现功能；

3，特别注意参数的调整，即下次传入递归函数的参数。