作者geo760217 (我想变成coding达人)
看板Programming
标题[问题] 可以帮我看看 quick sort 哪里错了吗?
时间Mon Sep 10 21:14:39 2007
code:
#include<iostream>
#define cutoff 3
using namespace std;
void swap(int *,int *);
void quick(int[],int,int);
int Median3(int[],int Left,int Right);
void insertion_sort(int a[],int);
int s;
int num = 1;
int a[2000];
int b[2000];
int c[2000][2000];
int main()
{
int x;
int i=0;
while(cin >> x)
{
if(x!=-1)
{
a[i] = x;
b[i] = x;
i++;
}
else
{
if(i==0)
break;
quick(a,0,i-1);
s = i;
for(int x=0;x<s;x++)
cout << a[x] << endl;
cout << endl;
i = 0;
}
}
return 0;
}
void swap(int *ptr1,int *ptr2)
{
int hold=*ptr1;
*ptr1=*ptr2;
*ptr2=hold;
}
int Median3(int A[],int Left,int Right)
{
int Center;
Center=(Left+Right)/2;
if(A[Left]>A[Center])
swap(&A[Left],&A[Center]);
if(A[Left]>A[Right])
swap(&A[Left],&A[Right]);
if(A[Center]>A[Right])
swap(&A[Center],&A[Right]);
swap(&A[Center],&A[Right]);
return A[Right];
}
void quick(int A[],int Left,int Right)
{
int i,j;
int Pivot;
if(Left+cutoff<=Right)
{
Pivot=Median3(A,Left,Right);
i=Left;
j=Right;
for(;;)
{
while(A[++i]<Pivot){}
while(A[--j]>Pivot){}
if(i<j)
swap(&A[i],&A[j]);
else
break;
}
swap(&A[i],&A[Right]);
quick(A,Left,i-1);
quick(A,i+1,Right);
}
else
{
insertion_sort(A,Right-Left);
}
}
void insertion_sort(int a[],int n)
{
int t;
int i,j;
for(i=1;i<=n;i++)
{
t = a[i];
for(j=i;j>0&&a[j-1]>t;j--)
a[j] = a[j-1];
a[j] = t;
}
}
测资:
389
207
155
300
299
170
158
65
-1
23
34
21
-1
-1
遇到-1代表结束
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.137.4