|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
|
|
|
|
|
|
直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
|
|
|
|
|
|
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即 r[1].key>r[2].key），则交换两个记录，接着比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序，使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时，所有记录都已有序排列。
|
|
|
|
|
|
简单选择排序的基本思想是：在进行每趟排序时，从无序的记录中选择出关键字最小（或最大）的记录，将其插入到有序序列（初始时为空）的尾部。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，且任意x∈R[1...i-1]，y∈R[i...n]满足x.key≤y.key，则选择排序的主要思路如下。
|
|
|
|
（1）反复从R[i...n]中选出关键字最小的结点R[k]。
|
|
|
|
（2）若i≠k，则将R[i]与R[k]交换，使得R[1...i]有序且保持原来的性质。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
可见，选择排序不管原先序列是否有序，其排序需要比较的次数均为n(n-1)/2；同时，由于相等的两个元素，位置相对在前的可能被交换到后面，故该选择排序是不稳定的。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个记录进行简单选择排序的基本方法是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录进行交换，当i等于n时所有记录有序排列。
|
|
|
|
|
|
|
简单选择排序法在最好情况下（待排序列已按关键码有序）不需要移动元素，因此n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n-1趟排序，总移动次数为3（n-1）。无论在哪种情况下，元素的总比较次数为 。
|
|
|
|
由此，简单选择排序是一种不稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O（1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
设S为具有n个不同元素的n元集，从S中选取r个元素且考虑其顺序称为S的一个r排列，不同排列的总数记为 ，有时也用P(n，r)表示。如果r=n，则称这个排列为S的全排列。从排列的定义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序也必须完全相同。
|
|
|
|
|
|
例子1：用0～9这十个数字，可以组成多少个没有重复数字的三位数？
|
|
|
解法1：由于百位数上的数字不能为0，因此可先考虑排百位上的数字，再排十位和个位上的数字。百位数上的数字只能从除0以外的1～9数字中任选一个，有 种；十位和个位上的数字，可以从余下的9个数字中任选两个，有 种。根据乘法原理，所求的三位数的个数是 。
|
|
|
解法2：可先考虑从0～9这十个数字中任取三个数字的排列数（ ），再减去其中以0开头的排列数（ ）。因此，所求的三位数的个数是 。
|
|
|
解法3：符合条件的三位数可以分为三类：每一位数字都不是0的三位数有 个；个位数是0的三位数有 个；十位数是0的三位数有 个。根据加法原理，符合条件的三位数个数是 。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
|
|
|
|
|
|
|
