排序算法的思考和实践

排序是程序开发过程中非常常见的一种操作，是将一组无序的记录序列调整为有序记录。例如，30个学生的考试成绩需要进行从大到小的排列。很多高级语言都为我们提供了内置的排序操作，下面是 PHP、JavaScript 和 Python 为我们提供的对学生成绩进行排序的方法：

<?php

$score = array(68,79,85,92,99,75,66,88,71,71,63,89,91,96,83,85,86,66,63,66,59,60,65,66,69,67,79,80,90,60);

sort($score);  //升序排列
rsort($score); //降序排列

score = new Array(68,79,85,92,99,75,66,88,71,71,63,89,91,96,83,85,86,66,63,66,59,60,65,66,69,67,79,80,90,60);

score.sort(); //升序排列（字符编码顺序）
score.sort(function(a,b){ return a-b; }); //升序排列
score.sort(function(a,b){ return b-a; }); //降序排列

score = [68,79,85,92,99,75,66,88,71,71,63,89,91,96,83,85,86,66,63,66,59,60,65,66,69,67,79,80,90,60]

print sorted(score)  #升序排列
print sorted(score,cmp=lambda x,y:cmp(y,x)) #降序排列

那么，在其它没有提供排序操作的语言里，我们如何去做呢？或者说，如何实现一个排序算法呢？

排序算法中，最常见的算法之一就是冒泡排序，其基本实现方法如下：

比较相邻的元素。如果第一个比第二个大，就交换它们两个。
对每一对相邻元素进行同样的操作，从开始的第一对一直到最后一对。完成之后，最后的元素应该是最大的数。
针对所有元素重复以上步骤，除了最后一个。
持续对越来越少的元素进行比较，直到没有任何一对数字需要交换。

用 C 语言实现如下：

#include <stdio.h>

void sort(int num[], int len){
    int i, j, tmp;

    j = len;

    for (; j > 1; j--){
        for(i = 0; i < j - 1; i++){
            if(num[i] > num[i+1]){
                tmp = num[i+1];
                num[i+1] = num[i];
                num[i] = tmp;
            }
        }
    }
}

int main(){
    int num[] = {121,120,10,100,342};

    sort(num,5);

    int i;

    for(i = 0; i < 5; i++){
        printf("%d\n",num[i]);
    }

    return 0;
}

冒泡排序就是对元素进行两两比较，把大的往后移动，小的往前移动，最终形成一个有序序列。

假设有 n 个元素需要排列，冒泡排序最多需要进行：

n(n-1)/2

次比较，因此它的时间复杂度为 O(n²)。

大数据排序问题

假设有一千万条随机排列的数字，如何求出其中最大的10个数？

显然，这里不能采用完全的冒泡排序。一种简单的办法是，先创建一个保存10个数字的数组，然后逐个读取数据，只保留其中最大的10个数，并进行排序。

如下：

#!/usr/bin/env python

class Container:
    def __init__(self,length):
        self.length = length
        self.ele = range(length)

    def add(self,number):
        if number > self.ele[0]:
            self.ele.remove(self.ele[0])
            self.ele.insert(0,number)
            self.ele.sort() # 内置函数进行排序
        elif number < self.ele[0]:
            return

    def get(self):
        return self.ele


arr = Container(10)

number = open("num.txt","r") # 假设num.txt中存放了一千万个数据

while True:
    line = number.readline()

    if not line:
        break

    num = int(line.strip())
    arr.add(num)

number.close()

print arr.get()

上面的 add() 操作会执行一千万次。最好情况下，num.txt 中前面的10个数就是最大的数，后面的数据基本都不需要重新排序；最差情况下，大量数据都需要进入排序过程。

由于容器中始终只有10个数据，因此每次排序的数据规模都非常小。

从上面的结果可以看出，在不考虑数据分布的情况下，获取最大的10个数仍然需要遍历全部一千万条数据，但不需要对全部数据进行完整排序，这样可以明显减少计算量。

那么问题又来了：如果要对这一千万个数字进行完整排序呢？该如何做？

这时候就不能只关注排序代码本身，而需要根据数据规模选择更加合适的排序算法。