扫码获取更多资源

●选择排序

排序(Selection Sort)是一类借助“选择”进行排序的方法，其基本思想是：每趟排序在 当前待排序序列中选出关键字最小的记录，添加到有序序列中。该方法比较独特的地方是 记录移动的次数较少。选择排序的方法主要包括简单选择排序和堆排序。

简单选择排序

简单选择排序(Simple Selection Sort)是选择排序中最简单的一种排序方法，需要解决 两个关键问题：一是如何在待排序序列中选出关键字最小的记录；二是如何确定待排序序 列中关键字最小的记录在有序序列中的位置

将选出的关键字最小的记录，与无序区中的第一个记录交换，使得有序区扩展了一个记 录，而无序区减少了一个记录。在第i趟排序中，关键字最小的记录和第i个记录交换作为 有序序列的第i个记录。不断重复该过程，直到无序区只剩下一个记录为止，此时所有的记 录已经按关键字从小到大的顺序排列就位。

算法描述

假设待排序记录个数为n。当初始文件记录为正序时，记录移动次数为0；当初始文件 记录为反序时，每趟排序均需要执行交换操作，总的记录移动次数取最大值3(n-l)0因此 简单选择排序中记录的移动次数较少。但无论文件初始状态如何，关键字的比较次数相同， 在第i趟排序中选出最小关键字的记录，需要做n — i次比较，总的比较次数为n(n—1)/2。 因此算法9-5的时间复杂度为0(1?)。

简单选择排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元，因此算 法9-5的空间复杂度为0(1)。

联系我们：