数据结构 排序算法

下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。

A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序
能不能解释D为什么是错的？

能不能解释D为什么是错的？

因为堆排序的性能不受时间的影响。
像这样的还有：简单选择排序、归并排序。
希望能帮到你~

看看可以不

#include<stdio.h>

#include<stdlib.h>

#define true 1

#define false 0

#define ok 1

#define error

#define overflow -2

#define maxsize 20 //一个用作示例的小顺序表的最大长度

#define lt(a,b) ((a)<(b))

#define lq(a,b) ((a)<=(b))

typedef int keytype;//定义关键字类型为整数类型

typedef int infotype;

typedef struct

{

keytype key;//关键字项

infotype otherinfo;//其他数据项

}redtype;//记录类型

typedef struct

{

redtype r[maxsize+1];//r[0]闲置或用作哨兵单元

int length;//顺序表长度

}sqlist;//顺序表类型

int initlist_sq(sqlist &l)

{//构造一个空的顺序表l。

int i;

printf("请输入待排序的记录的个数：");

scanf("%d",&l.length);

printf("请输入待排序的记录的关键字（整型数）：");

for(i=1;i<=l.length;i++)

scanf("%d",&l.r[i]);

return ok;

}

void print_sq(sqlist &l) //输出

{

int i;

for(i=1;i<=l.length;i++)

{

printf("%4d",l.r[i]);

}

printf("\n");

}

//------------插入排序---

void insertsort(sqlist &l)

{//对顺序表l作直接插入排序。

int i,j;

for(i=2;i<=l.length;++i)

if(lt(l.r[i].key,l.r[i-1].key))//“<”，需将l.r[i]插入有序子表

{

l.r[0]=l.r[i];//复制为哨兵

l.r[i]=l.r[i-1];

for(j=i-2;lt(l.r[0].key,l.r[j].key);--j)

l.r[j+1]=l.r[j];//记录后移

l.r[j+1]=l.r[0];//插入到正确位置

}

}

//--------------冒泡排序---

void bubblesort(sqlist &l)

{//l.r是待排序的文件，采用自下向上扫描，对l.r做冒泡排序

int i,j;

int exchange; // 交换标志

for(i=1;i<l.length;i++)

{// 最多做 n-1 趟排序

exchange=false; // 本趟排序开始前，交换标志应为假

for(j=l.length-1;j>=i;j--) // 对当前无序区 r[i..n] 自下向上扫描

if(lt(l.r[j+1].key,l.r[j].key))

{ // 交换记录

l.r[0]=l.r[j+1]; //l.r[0]不是哨兵，仅做暂存单元

l.r[j+1]=l.r[j];

l.r[j]=l.r[0];

exchange=true; // 发生了交换，故将交换标志置为真

}

if(!exchange) // 本趟排序未发生交换，提前终止算法

return;

}

}

//-----------快速排序---

int partition(sqlist &l,int low,int high)

{//交换顺序表l中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时

//在它之前（后）的记录均不大（小）于它。

keytype 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)

{//对顺序表l中的子序列l.r[low..high]进行快速排序

int pivotloc;

if(low<high)

{//长度大于1

pivotloc=partition(l,low,high);//将l.r[low..high]一分为二

qsort(l,low,pivotloc-1);//对低子表递归排序pivotloc是枢轴位置

qsort(l,pivotloc+1,high);//对高子表递归排序

}

}

void quicksort(sqlist &l)

{//对顺序表l作快速排序。

qsort(l,1,l.length);

}

//----------归并排序---

void merge(redtype sr[],redtype tr[],int i,int m,int n)

{//将有序的sr[i..m]和sr[m+1..n]归并为有序的tr[i..n]

int j,k;

for(j=m+1,k=i;i<=m&&j<=n;++k)

{//将sr中记录由小到大地并入tr

if lq(sr[i].key,sr[j].key) tr[k]=sr[i++];

else tr[k]=sr[j++];

}

if(i<=m)//tr[k..n]=sr[i..m];将剩余的sr[i..m]复制到tr

while(k<=n&&i<=m) tr[k++]=sr[i++];

if(j<=n)//将剩余的sr[j..n]复制到tr

while(k<=n&&j<=n) tr[k++]=sr[j++];

}

void msort(redtype sr[],redtype tr1[],int s,int t)

{//将sr[s..t]归并排序为tr1[s..t]。

int m;

redtype tr2[20];

if(s==t) tr1[t] = sr[s];

else

{

m=(s+t)/2;//将sr[s..t]平分为sr[s..m]和sr[m+1..t]

msort(sr,tr2,s,m);//递归地将sr[s..m]归并为有序的tr2[s..m]

msort(sr,tr2,m+1,t);//将sr[m+1..t]归并为有序的tr2[m+1..t]

merge(tr2,tr1,s,m,t);//将tr2[s..m]和tr2[m+1..t]归并到tr1[s..t]

}

}

void mergesort(sqlist &l)

{// 对顺序表l作归并排序。

msort(l.r, l.r, 1, l.length);

}

//-----------堆排序---

void heapadjust(sqlist &h,int s,int m)

{//已知h.r[s..m]中记录的关键字除h.r[s].key之外均满足堆的定义，

//本函数调整h.r[s]的关键字，使h.r[s..m]成为一个大顶堆

//（对其中记录的关键字而言）

int j;

redtype rc;

rc=h.r[s];

for(j=2*s;j<=m;j*=2)

{//沿key较大的孩子结点向下筛选

if(j<m&&h.r[j].key<h.r[j+1].key) ++j;//j为key较大的记录的下标

if(rc.key>=h.r[j].key) break;//rc应插入在位置s上

h.r[s]=h.r[j];

s=j;

}

h.r[s]=rc;//插入

}

void heapsort(sqlist &h)

{//对顺序表h进行堆排序。

int i;

redtype temp;

for(i=h.length/2;i>0;--i)//把h.r[1..h.length]建成大顶堆

heapadjust(h,i,h.length);

for(i=h.length;i>1;--i)

{

temp=h.r[i];

h.r[i]=h.r[1];

h.r[1]=temp;//将堆顶记录和当前未经排序子序列hr[1..i]中

//最后一个记录相互交换

heapadjust(h,1,i-1);//将h.r[1..i-1]重新调整为大顶堆

}

}

void main()

{

sqlist s;

printf("---------- 五种排序算法 ----------\n");

initlist_sq(s);

printf(" 1.简单插入排序\n");

insertsort(s);

print_sq(s);

printf(" 2.冒泡排序\n");

bubblesort(s);

print_sq(s);

printf(" 3.快速排序\n");

quicksort(s);

print_sq(s);

printf(" 4.归并排序\n");

mergesort(s);

print_sq(s);

printf(" 5.堆排序\n");

heapsort(s);

print_sq(s);

}