小弟在網上找了一個快排代碼，自己改了一下，無論怎么改都不能排全。請各位牛人幫忙，謝謝[\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貢獻1863條經驗 獲得超2個贊
這段代碼應該沒問題。
#include<iostream>
using namespace std;
int a[200000],n;
void sort(int low,int high)
{
if(high-low<=9)//小優化，當序列小于9時，使用插入排序或選擇排序可以減少少量的時間。我使用的是選擇排序，被注釋掉的那一大段代碼是插入排序。
{
/*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貢獻1818條經驗 獲得超8個贊
你的程序，沒工夫看，不過前幾天做了道題，也用到了快排，下面是我的程序，給你學習學習，我的快排是用遞歸寫的。用到了三個函數。。事實上c++庫函數中自帶有qsort函數，可直接調用的，你也可以學習qsort函數的用法
/* 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（）的成員函數，數組就不允許開這么大，就會運行錯誤
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)//這個函數返回的是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);//交換兩個位置的值
}
}
swap(last_small,low);//交換，將pivot放到它應該在的位置
//for(i=low;i<=high;i++)
return last_small;
}
void recursive_quick_sort(int low,int high)
{
int pivot_position; //支點的位置
if(low<high)
{
pivot_position=partition(low,high);//這個函數是用于尋找支點的位置
recursive_quick_sort(low,pivot_position-1);
recursive_quick_sort(pivot_position+1,high);
}
}
void QuickSort(int n)//按照fo字段進行排序
{
recursive_quick_sort(0,n-1);
}
void BinarySearch(char*word,int n,char* result) //n為字典d中message的個數
{
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++;
}
//對字典按照外文的字典順序排序
QuickSort(n);
// cout<<"排序后的結果"<<endl;
//for(int i=0;i<n;i++)
//cout<<d[i].en<<" "<<d[i].fo<<endl;
char word[11];
while(cin>>word)// 輸入要查詢的外文單詞放到數組words中
{
char result[11];
BinarySearch(word,n,result);
cout<<result<<endl;
}
return 0;
}
- 2 回答
- 0 關注
- 153 瀏覽
添加回答
舉報
0/150
提交
取消