快速排序C/C++代码实现

2021年8月18日09:02:13

#include<stdio.h>
//2021年8月17日21:43:13
int median3(int n[],int a,int b,int c)
{if((n[a]>=n[b] && n[a]<=n[c] )|| (n[a]<=n[b] && n[a]>=n[c])) return a;if((n[b]>=n[a] && n[b]<=n[c] )|| (n[b]<=n[a] && n[b]>=n[c])) return b;if((n[c]>=n[b] && n[c]<=n[a])|| (n[c]<=n[b] && n[c]>=n[a])) return c;//if(n[c]>n[b] && n[c]<n[a]|| n[c]<n[b] && n[c]>n[a]) return c;return 0;
}
void swap (int *a,int *b)
{int t=*a;*a=*b;*b=t;
}
void quicksort(int a[],int left,int right)
{if(right-left<1) return; int pivot=median3(a,left,right,(left+right)/2);swap(&a[pivot],&a[right]);int i=0,j=right-1;for(;;){while(a[i]<a[right]) i++;while(a[j]>a[right]) j--;if(i<j) swap(&a[i],&a[j]);else{swap(&a[i],&a[right]);quicksort(a,left,i-1);quicksort(a,i+1,right);break;}}
}
void quick_sort(int a[],int n)
{quicksort(a,0,n-1);
}
int main()
{int a[10]={1,4,7,9,2,8,6,3,0,5};quick_sort(a,10);for(int i=0;i<10;i++){printf("%d ",a[i]);}
}

有错误但结果正确的代码

（错误：右指针j指向right  right-left<=1）

#include<stdio.h>
void swap(int *a,int *b)
{int t=*a;*a=*b;*b=t;
}
int median3(int m[],int a,int b,int c)
{if((m[a]>m[b]&& m[a]<m[c]) || (m[a]<m[b] &&m[a]>m[c])) return a;if((m[b]>m[a]&& m[b]<m[c]) || (m[b]<m[a] &&m[b]>m[c])) return b;if((m[c]>m[b]&& m[c]<m[a]) || (m[c]<m[b] &&m[c]>m[a])) return c;else return 0;
}
void quicksort(int a[],int left,int right)
{if(right-left<=1) return ;int pivot=median3(a,left,(left+right)/2,right);swap(&a[right],&a[pivot]);int i=left,j=right;for(;;){while(a[i]<a[right])i++;while(a[j]>a[right]) j--;if(i<j) swap(&a[i],&a[j]); else {swap(&a[i],&a[right]);break;}}quicksort(a,left,i-1);quicksort(a,i+1,right);}
void quick_sort(int a[],int n)
{quicksort(a,0,n-1);
}
int main()
{int a[10]={0,2,533,1,312,4,7,19,8,6};quick_sort(a,10);for(int i=0;i<10;i++) printf("%d ",a[i]);
}