| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 490 人关注过本帖
标题:快速排序的求高手帮忙改成数组的,或者可以其他的排序是O(n㏒2n),
只看楼主 加入收藏
h2363752280
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2012-12-19
结帖率:33.33%
收藏
已结贴  问题点数:20 回复次数:2 
快速排序的求高手帮忙改成数组的,或者可以其他的排序是O(n㏒2n),
顺序表的排序,要求该算法的时间复杂度为O(n㏒2n),然后调用函数输出处理之后的顺序表.
/* QuickSort related function */快速排序的求高手帮忙改成数组的,或者可以其他的排序是O(n㏒2n),急急急
int Partition(SqList *L,int low,int high)
{
  int pivotkey;
  L->r[0]=L->r[low];
  pivotkey=L->r[low].key;
  while(low<high){
    while(low<high&&L->r[high].key>=pivotkey) --high;
    L->r[low]=L->r[high];
    while(low<high&&L->r[low].key<=pivotkey) ++low;
    L->r[high]=L->r[low];
  }
  L->r[low]=L->r[0];
  return low;
}
void QSort(SqList *L,int low,int high)
{
  int pivotloc;
  if(low<high){
    pivotloc=Partition(L,low,high);
    QSort(L,low,pivotloc-1);
    QSort(L,pivotloc+1,high);
  }
}
void QuickSort(SqList *L)
{
  QSort(L,1,L->length);
}        
搜索更多相关主题的帖子: related function 
2012-12-24 11:50
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:20 
坛子里有

www.qunxingw.wang
2012-12-24 12:31
h2363752280
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2012-12-19
收藏
得分:0 
#include <stdio.h>
#define MAX 99900
#include <time.h>

void creat1(int *p,int n)  //随机生成
{ int temp,i;   //定义两个整型变量
  srand((unsigned)time(NULL));
   for(i=0;i<n;i++)          //用随机函数生成一个顺序表
     {    temp=(int)rand()%MAX+100;  p[i]=temp;}
     
}
void creat2(int *p,int n)//输出
{    int i;
    for(i=0;i<n;i++)
   printf("%d\t",p[i]);

}
int partion(int low, int high)
{int a[MAX];
    a[0] = a[low];
    while( low < high )
    {
        while( low<high && a[0]<=a[high] )
            --high;
        a[low] = a[high];
        while( low<high && a[0]>=a[low] )
            ++low;
        a[high] = a[low];
    }
    a[low] = a[0];
    return low;
}
void sort(int a[],int low, int high)
{
    int i;
    if( low < high )
    {
        i = partion(low, high);
        sort(a,low, i-1);
        sort(a,i+1, high);
    }
}

void show(int n)
{int i,a[MAX];
    for(i=1; i<=n ; ++i )
        printf(" %d", a[i]);
}

int main()                  //主函数
{
int a[MAX],n;
int i,j=0;

while(1)
{
printf("\n 1随机生成顺序表       \n");
printf(" 2输出生成元素           \n");
printf(" 3paixu          \n");

scanf("%d",&i);

while(j==0&&i<0&&i>3)           //确认数组建立与否
{
printf("数组还没有建立!请重新选择功能号:");
scanf("%d",&i);}
switch(i)                    //功能选择
{

case 1:
    printf("键盘输入元素个数n\n");
    scanf("%d",&n);
    creat1(a,n);
    printf("随机生成数组元素成功!!\n\n");  
    break;
      
case 2: creat2(a,n);break;
        
case 3: sort(a,1,n);
    show(n);
      break;  
   

}}}快速排序的不知道哪里有错了求指导,急急急急
2012-12-24 13:24
快速回复:快速排序的求高手帮忙改成数组的,或者可以其他的排序是O(n㏒2n),
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032047 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved