＞第 11 章 排序与查找＞线性查找

/*对于这个问题我的想法是：把字母按照ascii码比较，先用快速排序进行，然后用快速查找进行查找。为了保存初始字符位置定义一个结构体下面为本算法实现。*/

#include<stdio.h>

char a[]="hello world";

struct array{
  char c;
  int index;
} T;

int partition(int start,int end,struct array a[])
{
  int j=start,i;
  char temp;
  for(i=start+1;i<=end;i++)
    if(a[i].c<=a[j].c)
      {
	temp=a[i].c;
	a[i].c=a[j+1].c;
	a[j+1].c=temp;

	temp=a[j+1].c;
	a[j+1].c=a[j].c;
	a[j].c=temp;
	j++;
      }
  return j;
}
void quicksort(int start ,int end,struct array a[])
{
  int mid;
  if(start<end)
    {
      mid=partition(start,end,a);
      quicksort(start,mid-1,a);
      quicksort(mid+1,end,a);
    }
}

int quickfind(int high1,struct array a[],char x)
{
  int low=0,high=high1;
  int mid;
  while(low<high)
    {
      mid=(low+high)/2;
      if(x<a[mid].c)
	high=mid-1;
      else if(x>a[mid].c)
	low=mid+1;
      else
	return a[mid].index;
    }
  return -1;
}
int indexof(char letter)
{
}

int main()
{                                         int i=strlen(a),j;
  struct array tmp[strlen(a)];
  for(j=0;j<=i;j++)
    {
      tmp[j].index=j;
      tmp[j].c=a[j];
    }
  quicksort(0,10,tmp);
  printf(" %d ",quickfind(10,tmp,'h'));

}

就这个算法我有个问题：就是我所实现的如果其中含有重复的字符如“hello world”这个字符串，如果查找'o'返回的是8,这个问题怎么解决呢？请大家指教，谢谢。

上面的方法是不行的，其中用到的快速排序其复杂度是Θ(nlgn)而不是Θ(lgn)，这已经比正常的顺序查找Θ(n)要更慢了。事实上在随机序列的情况下，没有比Θ(n)更快的查找方法，因为每个字母都必须比较，而且一次只能比较一个字母，因此复杂度就是Θ(n)，没有更小的了。
除非是有序序列，但排序将导致更大的时间消耗，正如上面的方法所示，排序的时间就已经比Θ(n)更大了。

如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！