当顺序表的长度固定以后,快速排序在什么情况下所需要的比较次数多?

当顺序表的长度固定以后,快速排序在什么情况下所需要的比较次数多?

如果选择某一确定点的元素作为标志（中点、第一个等等）
当表已经排好序时，这时有可能比较非常多：试想以最小的那个为标志，比较了n次之后，只是把规模降到了n-1而已，然后还得再比较n-1次……等等，这样就是O（n^2）的复杂度了
你可以自己打个顺序的数据试试，时间成倍增长
所以可以使用随机位置作为标志

///是不是要这样，
#include
#define MAXSIZE 10 // 待排顺序表最大长度
typedef int KeyType; // 关键字类型为整数类型
typedef struct sqlist
{
KeyType r[MAXSIZE+1]; // r[0]闲置
int length; // 顺序表长度
}SqList;
//建立顺序表//
SqList InputSList()
{int x;
SqList L;
L.length=0;
printf("\n请输入数据，结束输入-1！\n");
scanf("%d",&x);
while(x!=-1)
{ L.r[++L.length]=x;
if(L.length==MAXSIZE)
{ printf("\n顺序表已满!\n");
break;
}
scanf("%d",&x);
}
return L;
}
//直接插入排序//
void InsertionSort (SqList *L )
{
// 对顺序表 L 作直接插入排序。
int i,j;
SqList *p=L;
for ( i=2; i<=p->length; ++i )
if (p->r[i] < p->r[i-1])
{
p->r[0] = p->r[i];
p->r[i]=p->r[i-1];
for ( j=i-2; p->r[0] < p->r[j]; -- j )
p->r[j+1] = p->r[j]; // 记录后移
p->r[j+1] = p->r[0]; // 插入到正确位置
}
}
//冒泡排序//
void BubbleSort(SqList *L)
{
int i,j,t;
SqList *p=L;
for (i=p->length;i>1;--i){
for (j=1;j if (p->r[j+1]r[j]){
t=p->r[j+1];
p->r[j+1]=p->r[j];
p->r[j]=t;

}
}
}

//简单选择排序//
void SelectSort (SqList *L )
{ SqList *p=L;
int i, j, k; KeyType temp;
for (i=1; ilength; ++i) { k=i;
for (j=i+1; j<=p->length; j++)
if (p->r[j]r [k]) k=j;
if (k!=i)

}
}
void display(SqList *L)
{
SqList *p;
p=L;
if (p->length!=0)
{
while(p->length)
{ printf("%d ",p->r[p->length]);
p->length--;
}
}
printf("\n");
}
void main()
{
SqList L;
L=InputSList();
InsertionSort (&L);
// SelectSort (&L) ;
// BubbleSort(&L);
display(&L);
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息