排序算法的思考和实践

 分类: 致知

排序是程序开发过程中非常常见的一种操作,是将一组无序的记录序列调整为有序记录。例如,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)!

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

发表评论