C语言五种基本排序算法

程序员可以使用的基本排序算法有5种：

1. 插入排序(insertionsort．)
2. 交换排序(exchangesOrt)
3. 选择排序(selectionsort)
4. 归并排序(mergesort)
5. 分布排序(distributionsort)

为了形象地解释每种排序算法是怎样工作的，让我们来看一看怎样用这些方法对桌上一付乱序的牌进行排序。牌既要按花色排序(依次为梅花、方块、红桃和黑心)，还要按点数排序(从2到A)。

插入排序的过程为：从一堆牌的上面开始拿牌，每次拿一张牌，按排序原则把牌放到手中正确的位置。桌上的牌拿完后，手中的牌也就排好序了。

交换排序的过程为：

    (1)先拿两张牌放到手中。如果左边的牌要排在右边的牌的后面，就交换这两张牌的位置。

    (2)然后拿下一张牌，并比较最右边两张牌，如果有必要就交换这两张牌的位置。

    (3)重复第(2)步，直到把所有的牌都拿到手中。

    (4)如果不再需要交换手中任何两张牌的位置，就说明牌已经排好序了；否则，把手中的牌放到桌上，重复(1)至(4)步，直到手中的牌排好序。

选择排序的过程为：在桌上的牌中找出最小的一张牌，拿在手中；重复这种操作，直到把所有牌都拿在手中。

归并排序的过程为：把桌上的牌分为52堆，每堆为一张牌。因为每堆牌都是有序的(记住，此时每堆中只有一张牌)，所以如果把相邻的两堆牌合并为一堆，并对每堆牌进行排序，就可以得到26堆已排好序的牌，此时每一堆中有两张牌。重复这种合并操作，就可以依次得到13堆牌(每一堆中有4张牌)，7堆牌(有6堆是8张牌，还有一堆是4张牌)，最后将得到52张的一堆牌。

分布排序(也被称作radix sort，即基数排序)的过程为：先将牌按点数分成13堆，然后将这13堆牌按点数顺序叠在一起；再将牌按花色分成4堆，然后将这4堆牌按花色顺序叠在一起，牌就排好序了。

在选用排序算法时，你还需要了解以下几个术语：

1、自然的(natural)

如果某种排序算法对有序的数据排序速度较快(工作量变小)，对无序的数据排序速度却较慢(工作变量大)，我们就称这种排序算法是自然的。如果数据已接近有序，就需要考虑选用自然的排序算法。

2、稳定的(stable)

如果某种排序算法能保持它认为相等的数据的前后顺序，我们就称这种排序算法是稳定的。

    例如，现有以下名单：
    Mary Jones
    Mary Smith
    Tom Jones
    Susie Queue

如果用稳定的排序算法按姓对上述名单进行排序，那么在排好序后"Mary Jones”和"Tom Jones”将保持原来的Jr顺序，因为它们的姓是相同的。

稳定的排序算法可按主、次关键字对数据进行排序，例如按姓和名排序(换句话说，主要按姓排序，但对姓相同的数据还要按名排序)。在具体实现时，就是先按次关键字排序，再按主关键字排序。

3、内部排序(internal sort)和外部排序(external sort)

待排数据全部在内存中的排序方法被称为内部排序，待排数据在磁盘、磁带和其它外存中的排序方法被称为外部排序。