?本节内容说明
内容,选择排序、多关键字排序
要求,掌握简单选择排序的基本思想及算法实现，并了解该排序算法的性能；通过多关键字排序问题进一步提高利用排序算法解决实际问题的能力。
重点,简单选择排序的基本思想及算法实现；
计算机解决多关键字排序中应注意的问题。
难点,多关键字排序的具体实现。
4.7 简单选择排序第一趟排序在所有待排序的 n个记录中选出关键字最小 的记录，将它与数据表中的第一个记录 交换 位置，使关键字最小的记录处于数据表的最前端；第二趟在剩下的 n-1个记录中再选出关键字最小的记录，将其与数据表中的第二个记录交换位置；重复这样的操作，排序共进行 n-1趟,最终可实现数据表的升序排列。
一,基本思想：
选择排序过程示例 ---以升序为例初始状态 38 20 46 38 74 91 12
第 1趟 12 20 46 38 74 91 38
第 2趟 12 20 46 38 74 91 38
第 3趟 12 20 38 46 74 91 38
第 4趟 12 20 38 38 74 91 46
第 5趟 12 20 38 38 46 91 74
第 6趟 12 20 38 38 46 74 91
20本身就是最小的
第 i趟循环，在 list[i]~list[n]范围内选择关键字 最小 的元素，将其与 list[i]进行 交换 。
二．算法描述
k=i; /*k用于记下最小元素的下标 */
for (j=i+1;j<=n;j++)
/*在待排序范围内寻找关键字最小的记录 */
if(list[j].key<list[k].key) k=j;
if(k!=i)
{temp=list[i];
list[i]=list[k];
list[k]=temp;
}
第 i趟执行的操作下面的简单选择排序实现将一个长度为 n的线性表 r
上的所有元素按关键字升序排列。
{ k=i; /*k用于记下最小元素的下标 */
for (j=i+1;j<=n;j++)
/*在待排序范围内寻找关键字最小的记录 */
if(list[j].key<list[k].key) k=j;
if(k!=i)
{ temp=list[i];
list[i]=list[k];
list[k]=temp;
}
}
for(i=1;i<=n-1;i++) /*外循环控制排序的总趟数 */
void selectsort(ElemType list[],int n)
{int i,j,k;
ElemType temp;
} /*selectsort*/
三,算法分析
稳定性,不稳定的
时间复杂度,Ｏ (n2)
与初始状态无关
知识回顾
void sort(ElemType list[],int n)
{int i,j;
ElemType t;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(list[j].key<list[i].key)
{t=list[i];
list[i]=list[j];
list[j]=t;
}
}
下面的排序算法实现将表长为 n
的线性表按关键字值升序排列。
思考?
此排序算法应属于哪种排序方法？
与刚刚介绍的选择排序算法相比，两个算法有何不同之处？哪个算法的效率更高？