小弟在網(wǎng)上找了一個(gè)快排代碼，自己改了一下，無論怎么改都不能排全。請(qǐng)各位牛人幫忙，謝謝[\code]#include<iostream>using namespace std;int n;void kp(int a[],int b,int c){int i=b,j=c,x=a[(b+c)/2];do{while (a[i]<x&&i<j)i++;while (a[j]>x&&j>i)j--;if (i<=j){swap(a[i],a[j]);i++;j--;}}while(i<=j);if (b<j)kp(a,b,j);if (c>i)kp(a,i,c);}int main(){int i,s=1;cin>>n;int a[n+1];a[0]=0xfffffff;for (i=1;i<=n;i++)cin>>a[i];cout<<endl;kp(a,1,n);for (i=1;i<=n;i++){if (a[i]==a[i-1]){s++;continue;}if (i!=1){cout<<a[i-1]<<' '<<s<<endl;s=1;}elsecout<<a[i]<<' '<<s<<endl;}return 0;}[code]
2 回答
小唯快跑啊
TA貢獻(xiàn)1863條經(jīng)驗(yàn) 獲得超2個(gè)贊
這段代碼應(yīng)該沒問題。
#include<iostream>
using namespace std;
int a[200000],n;
void sort(int low,int high)
{
if(high-low<=9)//小優(yōu)化，當(dāng)序列小于9時(shí)，使用插入排序或選擇排序可以減少少量的時(shí)間。我使用的是選擇排序，被注釋掉的那一大段代碼是插入排序。
{
/*int i,j=low,k,tmp;
for(i=low+1;i<=high;i++)
{
j=low;
while(a[i]>a[j]&&j<i) j++;
if(j!=i)
{
tmp=a[i];
for(k=i;k>j;k--)
a[k]=a[k-1];
a[k]=tmp;
}
}*/
int i,j;
for(i=low;i<high;i++)
for(j=i+1;j<=high;j++)
if(a[j]>a[i])
swap(a[i],a[j]);
return ;
}
int v=a[low],i=low,j=high+1;
do
{
do i++;
while(a[i]<v);
do j--;
while(a[j]>v);
if (i<j)
swap(a[i],a[j]);
}while(i<j);
a[low]=a[j];
a[j]=v;
sort(low,j-1);
sort(j+1,high);
return ;
}
int main()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(0,n-1);
int tmp=a[0],s=1;
for(i=1;i<n;i++)
if(a[i]!=tmp)
{
printf("%d %d\n",tmp,s);
s=1;
tmp=a[i];
}
else
s++;
printf("%d %d\n",tmp,s);
return 0;
}
弒天下
TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超8個(gè)贊
你的程序，沒工夫看，不過前幾天做了道題，也用到了快排，下面是我的程序，給你學(xué)習(xí)學(xué)習(xí)，我的快排是用遞歸寫的。用到了三個(gè)函數(shù)。。事實(shí)上c++庫(kù)函數(shù)中自帶有qsort函數(shù)，可直接調(diào)用的，你也可以學(xué)習(xí)qsort函數(shù)的用法
/* Babelfish
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 15011 Accepted: 6605
Description
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.
Input
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words.
Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word
appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line.
Each word in the input is a sequence of at most 10 lowercase letters.
Output
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".
Sample Input
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
Sample Output
cat
eh
loops
Hint
Huge input and output,scanf and printf are recommended.
Source
Waterloo local 2001.09.22
*/
#include <iostream>
using namespace std;
struct dic_entry
{
char en[11];//表示english;
char fo[11];//表示foreignlanguage
} d[100001];//d表示dictionary; //真奇怪，如果將d聲明為main（）的成員函數(shù)，數(shù)組就不允許開這么大，就會(huì)運(yùn)行錯(cuò)誤
void swap(int pos1,int pos2)
{
char temp1[11]="";
strcpy(temp1,d[pos1].en);
strcpy(d[pos1].en,d[pos2].en);
strcpy(d[pos2].en,temp1);
char temp2[11]="";
strcpy(temp2,d[pos1].fo);
strcpy(d[pos1].fo,d[pos2].fo);
strcpy(d[pos2].fo,temp2);
}
int partition(int low,int high)//這個(gè)函數(shù)返回的是pivot的位置
{
char pivot[11];
int i,last_small;
strcpy(pivot,d[low].fo);//
last_small=low;
for(i=low+1;i<=high;i++)
{
if(strcmp(d[i].fo,pivot)<0)
{
last_small=last_small+1;
swap(i,last_small);//交換兩個(gè)位置的值
}
}
swap(last_small,low);//交換，將pivot放到它應(yīng)該在的位置
//for(i=low;i<=high;i++)
return last_small;
}
void recursive_quick_sort(int low,int high)
{
int pivot_position; //支點(diǎn)的位置
if(low<high)
{
pivot_position=partition(low,high);//這個(gè)函數(shù)是用于尋找支點(diǎn)的位置
recursive_quick_sort(low,pivot_position-1);
recursive_quick_sort(pivot_position+1,high);
}
}
void QuickSort(int n)//按照fo字段進(jìn)行排序
{
recursive_quick_sort(0,n-1);
}
void BinarySearch(char*word,int n,char* result) //n為字典d中message的個(gè)數(shù)
{
strcpy(result,"eh");//如果沒有查到就放回eh，這是題目的要求
int low=0;
int high=n-1;
int mid=0;
while(low<=high)
{
mid=(low+high)/2;
int flag=strcmp(d[mid].fo,word);
if(flag==0)
{
strcpy(result,d[mid].en);
return ;
}
if(flag>0)
{
high=mid-1;
}
else low =mid+1;
}
}
int main()
{
int n=0;
char s[40];
while(gets(s))
{
int len=strlen(s);
if(len==0)
break;
int i=0;
for(i=0; s[i]!=' ';i++ )
d[n].en[i]=s[i];
d[n].en[i]='\0';
int k=0;
for(int j=i+1; j<len ; j++)
{
d[n].fo[k]=s[j];
k++;
}
d[n].fo[k]='\0';
n++;
}
//對(duì)字典按照外文的字典順序排序
QuickSort(n);
// cout<<"排序后的結(jié)果"<<endl;
//for(int i=0;i<n;i++)
//cout<<d[i].en<<" "<<d[i].fo<<endl;
char word[11];
while(cin>>word)// 輸入要查詢的外文單詞放到數(shù)組words中
{
char result[11];
BinarySearch(word,n,result);
cout<<result<<endl;
}
return 0;
}
- 2 回答
- 0 關(guān)注
- 132 瀏覽
添加回答
舉報(bào)
0/150
提交
取消