如何编写有重复项串数组的快速排序，不用qsort

#include   "stdafx.h"  
  #include   "stdio.h"  
  #include   "stdlib.h"  
   
  #define   one   17  
   
  char   s1[one][100];  
   
  void   quick_string(char   items[][100],int   count);  
  void   qs_string(char   items[][100],int   left,int   right);  
   
  int   APIENTRY   WinMain(HINSTANCE   hInstance,  
                                            HINSTANCE   hPrevInstance,  
                                            LPSTR           lpCmdLine,  
                                            int               nCmdShow)  
  {  
    //   TODO:   Place   code   here.  
   
  FILE   *f1;  
  FILE   *f2;  
  f1=fopen("1.txt","r");  
  f2=fopen("2.txt","w");  
   
  for(int   read1=0;read1<one;read1++){  
  fscanf(f1,"%s\n",s1[read1]);  
  }  
   
  quick_string(s1,one);  
   
   
  for(int   i=0;i<one;i++){  
   
  fprintf(f2,"%s\n",s1[i]);  
   
  }  
   
   
  return   0;/**/  
  }  
   
  void   quick_string(char   items[][100],int   count){  
  qs_string(items,0,count-1);  
  }  
   
  void   qs_string(char   items[][100],int   left,int   right){  
  register   int   i,j;  
  char   *x;  
  char   temp[100];  
   
  i=left;j=right;  
  x=items[(left+right)/2];  
   
  do{  
  while((strcmp(items[i],x)<0)&&(i<right))   i++;  
  while((strcmp(items[j],x)>0)&&(j>left))   j--;  
  if(i<=j){  
  strcpy(temp,items[i]);  
  strcpy(items[i],items[j]);  
  strcpy(items[j],temp);  
  i++;j--;  
  }  
  }while(i<=j);  
   
  if(left<j)   qs_string(items,left,j);  
  if(i<right)   qs_string(items,i,right);  
  }  
   
  1.txt  
  a  
  h  
  c  
  h  
  e  
  f  
  h  
  h  
  i  
  j  
  k  
  l  
  m  
  n  
  h  
  h  
  h  
  输出结果为  
  a  
  c  
  e  
  f  
  h  
  h  
  h  
  h  
  h  
  h  
  h  
  i  
  l  
  m  
  j  
  k  
  n  
  是我写的代码不对，还是对重复项有另外的算法。 问题点数：100、回复次数：5Top

1 楼nasi00（莫傲·逍遥）回复于 2005-06-01 05:17:00 得分 10

快排要区分重复项吧  
   
  你可以这样：如果有相等两个串的话，地址小的排在前面，这样就区分了重复项阿（理论上可行，没试过）Top

2 楼foochow（无聊,灌水......）回复于 2005-06-01 07:29:53 得分 40

#include<iostream>  
  #include<string>  
  #include<vector>  
  #include<algorithm>  
  using   namespace   std;  
  int   main()  
  {  
  string   temp="ahchefhhijklmnhhh";  
  vector<int>tent;  
  for(int   i=0;i<temp.length();++i)  
  {  
  tent.push_back((int)temp[i]);  
  }  
  sort(tent.begin(),tent.end());  
  for(int   j=0;j<tent.size();++j)  
  {  
  cout.put(tent[j]);  
  }  
  cout<<endl;  
  system("PAUSE");  
  return   0;  
  }Top

3 楼jixingzhong（瞌睡虫·星辰）回复于 2005-06-01 08:56:08 得分 30

快排是要区分重复项的，否则会出现无限的递归函数调用！！  
   
   
  对于这种情况，可以用计数排序啊。（考研复习是看到的一种算法，感觉还好：计算组中的比自己小的元素的个数，如有N个，则自己排在N-1）  
   
  如果一定要用到快速排序，可以先对组处理一下，去掉重复项，只保留一个，（记录重复的次数），对没有重复项的组用快排，输出是结合次数，重复项重复输出相应次数。Top

4 楼jixingzhong（瞌睡虫·星辰）回复于 2005-06-01 08:59:41 得分 10

计数排序中要处理重复项，必须设置3个数组，  
   
  相对来说是比较麻烦！！  
  Top

5 楼mostideal（三甲）回复于 2005-06-03 00:02:05 得分 10

dingTop

相关问题

• hinstance
• fopen
• include
• txt
• char items
• read

• 帖主：66766
• nasi00
• foochow
• jixingzhong
• jixingzhong
• mostideal

• C/C++ Blog
• C/C++类图书
• C/C++类源码下载