关于数据结构排序算法的问题

插入排序、选择排序、冒泡排序、基数排序、堆排序的算法中其比较次数与初始数据集顺序无关的是？请说明理由。

选择排序

插入排序：每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

选择排序：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数
据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情
况下将快于冒泡排序。

冒泡排序：在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。
堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。

看看可以不

#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);

}

选择排序。 选择排序的算法原理是：第一趟从n个待排关键字中找出最小的关键字放到第一个位置，如果要找到最小关键字则必须所有元素都进行比较，所以第一趟要比较n-1次；第二趟从剩下的n-1的元素中再通过n-2次的比较找出最小的元素…………以此类推，不管初始有没有序，它都一共要进行n-1趟排序共n(n-1)/2次比较，时间复杂度始终是O（n平方） 至于其他的，拿插入排序举例：插入排序的基本思想是每次将一个待排的记录按其关键字大小插入到前面已经排好序的子序列中。试想，如果已经排好序的子序列是123，待排记录为45，插入4时，只要和3比较一次就知道排在3后面，对5排序时只要与4比较一次就知道该排在4后面，共比较2次。如果已经排好序的子序列是234，待排记录为15，插入1时，它要从后往前依次比较3次才能找到自己的位置，同样对5排序时只要与4比较一次，共比较4次。由上例可知，插入排序会随着初始数据集的顺序不同而比较次数不同。 BTW，基数排序不是基于关键字比较的排序算法。 纯手打，望采纳，不清楚还可共同探讨。