排序算法的思考和实践

 分类: 致知

排序是程序开发过程中非常常见的一种操作，是将一组无序的记录序列调整为有序记录。例如，30个学生的考试成绩需要进行从大到小的排列，很多高级语言为我们提供了内置的排序操作，下面是PHP,
JS, 和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);
echo sort($score);//升序排列
echo 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 ; j > 2; 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-1)的阶乘。

大数据排序问题

有一千万条随机排列的数字，如何求出其中最大的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 = line.strip()
	arr.add(num)

number.close()
print arr.get()

以上add的操作(27行)是一千万次，最好情况下，num.txt中前面的10个数是最大的，self.ele.sort()则只需要进行10次，最差的情况下需要进行一千万次，两种情况，其总计算次数为(假设sort为冒泡排序实现的)：
最好情况: 10*(10-1)!
最差情况: 10000000*(10-1)!

从上面的结果可以看出，在不考虑运气的情况下，获取最大的数的个人越多，情况越复杂，那么问题就来了，如果要对这一千万的所有数字进行排序呢，该如何做？

发表回复