排序算法的思考和实践

 分类: 致知

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

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

发表回复