大家帮我看下这段快速排序的程序有什么问题,为什么数据一多,半天都输不出结果
#include<stdio.h>void main(){ int a[]={25,36,49,100,20,250,30,200,5241,1,36},i; void QuickSort(int a[],int begin,int end); int n=sizeof(a)/sizeof(a[0]); QuickSort(a,0,n-1); for(i=0;i<n;i++) { printf("%d\t",a[i]); }}void QuickSort(int a[],int left,int right){ int key=a[left]; int begin=left; int end=right; while(begin<end) { while(begin<end&&a[end]>key) { end--; } if(begin<end) { a[begin]=a[end]; } while(begin<end&&a[begin]<key) { begin++; } if(begin<end) { a[end]=a[begin]; } a[begin]=key; if(begin-left>1) { QuickSort(a,left,begin-1); } if(right-begin>1) { QuickSort(a,begin+1,right); } }}
void QuickSort(int a[],int left,int right){ int key=a[left]; int begin=left; int end=right; while(begin<end) { while(begin<end&&a[end]>key) { end--; } if(begin<end) { a[begin]=a[end]; ++begin; // 这个地方少了 } while(begin<end&&a[begin]<key) { begin++; } if(begin<end) { a[end]=a[begin]; --end; // 这个地方少了 } a[begin]=key; if(begin-left>1) { QuickSort(a,left,begin-1); } if(right-begin>1) { QuickSort(a,begin+1,right); } }}
[解决办法]
你这个是什么啊?根本就不是快速排序算法。而且根本就是个错误的排序算法。
你直接写:a[begin]=a[end]; 那不是就把a[begin]给扔掉了?这样排下来得扔掉多少成员啊?
[解决办法]
思路错了, 别把递归调用放在while里面, 因为 end 和 begin很可能根本就不能碰到
int Partation(a, left, right) while(begin<end) { while(begin<end&&a[end]>key) { end--; } if(begin<end) { a[begin++]=a[end]; } while(begin<end&&a[begin]<key) { begin++; } if(begin<end) { a[end--]=a[begin]; }}a[begin] = key;return begin;