排序之快排qsort

2019-11-06 07:16:00

字体：大中小

来源：转载

供稿：网友

#include<stdio.h>#include<stdlib.h>#include<time.h>/*rand产生的随机数从0~rand_max（32767）产生从x~y的随机数k=rand()%(y-x+1)+x *///k=rand()%(right-left+1)+left; void swap(int& a,int& b) { if(a!=b) { a^=b; b^=a; a^=b; } }void RANDOMIZED_QUICKSORT(int a[],int left,int right){ srand((int) time(0));//以时间为随机种子 swap(a[rand()%(right-left+1)+left],a[right]);//随机化 int pivot = a[right],l = left,r = right; while(l<r) { swap(a[l],a[r]);//把分界值放在最左边 while(r>l&&a[r]>pivot)//交换后a[r]>pivot r会自减到a[r]<=pivot 保证最后的l=r 而且a[r]<pivot且pivot =a[left] r--; while(l<r&&a[l]<=pivot) l++; } swap(a[left],a[r]); if(left<l-1)RANDOMIZED_QUICKSORT(a,left,l-1); if(r+1<right)RANDOMIZED_QUICKSORT(a,r+1,right);}int main(){ int a[10] = {2,9,71,20,0,212,364,78,-1,55}; RANDOMIZED_QUICKSORT(a,0,9); for(int i=0;i<10;i++) { PRintf("%d ",a[i]); }}

上一篇：Markdown

下一篇：排序之归并排序