交换类排序算法

Question

如题所述

Answer 1

根据排序时数据所占用存储器的不同，可将排序分为两类，一类是整个排序过程完全在内存中进行，成为内部排序。另一类是由于待排序记录数据太大，内存无法容纳全部数据，需要借助外部存储才能完成，称为外部排序。

按照方法可以分为交换类排序和插入类排序。

算法思想：

从待排序记录序列中选取一个记录（通常是第一个）作为枢轴，其关键字设为K1，然后将其余关键字小于K1的记录移动到前面，关键字大于K1的移动到后面，结果将待排序记录分成两个子表，最后将关键字为K1的记录插到分界线的位置处。这个过程称为一趟快速排序。

算法步骤：

假设待划分序列为r,r,....,r,具体实现过程，可以设两个指针i和j，它们的初值分别是left和right。首先将基准记录r移至变量x中，然后反复进行下两步，直到i和j相遇。

1、i从左向右扫描直到r>x时，将r移至空单元r，此时r相当于空单元。

2、j从右向左扫描直到r<x时，将r移至空单元r，此时r相当于空单元。

当i和j相遇的时候，给空单元赋值x，然后对于左右形成的两个子表采用同样的方法进一步划分。