锐客网

  1. 首页 > 生活百科 > it技术 > >

C/C++快速排序

IT知识快速排序排序

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述C/C++快速排序相关的知识，希望能为你提供帮助。


//左边区间比key小，中间区间未处理，右边区间比key大
int oneSort(int a[],int left,int right)

//i,j为两个指针，一个从左向右移动，一个从右向左移动
int i=left;
int j=right;
int key=a[left]; //把第一个数当轴值
while(i< j)//每次循环处理左右两个子区间，并完成左右区间第一个不满足值的位置交换

while(key< a[j]& & i< j) //如果右边的值比轴值大，指针向左移动
j--;
if(i< j)

a[i]=a[j]; //右边第一个比key小的值放在左边指针停留的位置
i++; //左边指针向右移动一位，下次指针移动从下一个位置开始

while(a[i]< key& & i< j) //如果左边的值比轴值小，指针向右移动
i++;
if(i< j)

a[j]=a[i]; //左边第一个比key大的值放在右边指针停留的位置
j--; //右边指针向左移动一位，下次指针移动从下一个位置开始


//至此，[left,i]左边区间值都比key小，[j,right]右边区间值都比key大，完成时i==j
a[i]=key; //设置key的位置，i指针停留的位置就是key的位置，实际上就是交换key，i，j的值
//key=a[j]; 右边第一个比key小的值放在key位置
//a[j]=a[i]; 左边第一个比key大的值放在右边第一个比key小的位置
//a[i]=key; key放在左边第一个比key大的位置

return i; //返回key的位置

void qSort(int a[],int left,int right)

if(left< right)

int key_pos=oneSort(a,left,right); //完成一次划分，并返回key的坐标
qSort(a,left,key_pos-1); //继续划分左边
qSort(a,key_pos+1,right); //继续划分右边



int _tmain(int argc, _TCHAR* argv[])

int a[10] = 7,3,8,9,4,1,10,5,2,6;
cout< < "before sort:";
for (int i=0; i< 10; i++)

cout< < a[i]< < " ";

cout< < endl;
qSort(a,0,9);
cout< < "after sort:";
for (int i=0; i< 10; i++)

cout< < a[i]< < " ";

cout< < endl;
getchar();
return 0;



【C/C++快速排序】


    推荐阅读


    上一篇：道德经

    下一篇：Clojure使用Java方法