首页 > algorithm > 排序4(快速排序–冒泡的改进)

排序4(快速排序–冒泡的改进)

  今天看了《算法导论》的第七章快速排序。
  首先选择一个记录(通常选择第一个)最为枢轴(pivot)(自己理解为用作比较的关键字)。
  其次,开始进行排序,先进行一趟排序,然后进行递归式的排序。
  在一趟排序的时候,还有两种思维的方法:①(注释的partition)直接把比pivot小的移动在低位,把比pivot大的移动在高位,最后了,把pivot放进去。②设立三个指向东西的i,j,p。p是记录低位,不动。j是遍历,i记录低位段的最高位,最后了,再把pivot查到地位段和高位段的中间。
  继续进化:
  当对一个随机的输入数组应用快速排序时,要想在每一层上都有同样的划分是不太可能的。这样每一次的pivot都是第一个元素的话,就会使某些划分比较对称,另一些很不对称。一个好的解决方法:把pivot随机化,这样我们就在期望平均的情况下,对输入数组进行划分能够比较的对称。
  随机化版本的快速排序是对足够大的输入的理想选择。

#include<stdio.h>
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
return;
}
int partition(int * a,int p ,int r)
{
int x=a[r],i=p-1,j;
for(j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
swap(&a[i],&a[j]);
}
}
swap(&a[i+1],&a[r]);
return i+1;
}
/*int partition(int * a,int low ,int high)
{
int pivot;
a[0]=a[low];
pivot=a[low];
while(low<high)
{
while(low= pivot )
–high;
a[low]=a[high];
while(low ++low;
a[high]=a[low];
}
a[low]=a[0];
return low;
}*/
void quickSort(int *a,int low,int high)
{
int pivot;
if(low<high)
{
pivot=partition(a,low,high);
quickSort(a,low,pivot-1);
quickSort(a,pivot+1,high);
}
return;
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
quickSort(a,1,10);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

  1. Dontarrious 9月 2nd, 2012 @ 00:23 | #1

    I’m imprsesed! You’ve managed the almost impossible.

评论提交中, 请稍候...

留言


可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks