查找和排序(13)

习题习题习题习题习题习题习题习题习题

void selectSort(list r,int n)

{//对于包含n个元素的待排序列r进行直接选择排序

for(i=1;i<=________;i++) {k=i;

for(j=i+1;j<=n;j++)if(r[j].key<r[k].key)________;

if(______)swap(r[k],r[i]）; }

}

2．以下对进行一趟快速排序，请补充完整。

int quickpass(list r,int h,int p)

{//对子序列r[h],r[h+1],……r[p]进行一趟快速排序，以第一个记录的键值为枢纽

i=h;j=p;x=r[i];

while(i<j)

{while((r[j].key>=x.key)&&(i<j))________;

if(i<j)

{________;i++;

while((r[i].key<=x.key)&&(i<j))________;

if(i<j){________;j--;}

}

}

r[i]=________;return(i);

}

3．设带头结点的单链表L，结点数据值为整型。试写出对链表L按“插入方法”排序的算法：LINSORT(L).

4．冒泡排序算法是把大的元素向上移（起泡的上浮），也可把小的元素向下移（起泡的下沉），请给出上浮和下沉过程交替的起泡排序算法。

5.一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。

6.已知排序码序列{k1,k2,...,kn}是小顶堆，试写一算法，增加排序码x到堆中{k1,k2,...,kn，x}后，将其调整为小顶堆的算法。（排序码值为ki的记录存于r[i-1]中）

7．请用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第i（0<i<=n）个小元素。