一步一步写算法(之非递归排序).doc

软件英才网 软件行业驰名招聘网站 一步一步写算法（之非递归排序） 在上面一篇博客当中，我们发现普通查找和排序查找的性能差别很大。作为一个100万的数据，如果使用普通的查找方法，那么每一个数据查找平均下来就要几十万次，那么二分法的查找呢，20多次就可以搞定。这中间的差别是非常明显的。既然排序有这么好的效果，那么这篇博客中，我们就对排序算做一个总结。 按照我个人的理解，排序可以分为两种：一种是非递归排序，它主要按照非递归的方法对数据进行排序，也就是说主要数据的移位和循环来完成；另外一种就是递归方法，我们在排列当前数据的时候首先把子数据排列有序，然后才会排列当前的数据。这种不断递归调用的方法就是递归排序。 非递归排序的方法很多，这里主要介绍冒泡排序、插入排序、希尔排序；递归的方法也不少，这里介绍的方法是快速排序、归并排序和堆排序。排序的内容很多，本篇博客主要介绍非递归排序，递归排序的内容主要在下一节内容解决。 （1）冒泡排序 冒泡排序的内容并不复杂。假设有n个数据需要排序，那么我们需要确定n个从大到小的数据，每一次都挑选第n大的数据是多少，并且放大相应的位置。直到所有的数据都排列整齐了，那么我们的排序就结束了。cpp view plaincopy1 void bubble_sort(int array, int length) 2 3 int inner = 0, outer = 0; 4 int median = 0; 5 6 if(NULL = array | 0 = length) 7 return; 8 9 for(outer = length-1; outer = 1; outer -) 10 for(inner = 0; inner arrayinner + 1) 12 median = arrayinner; 13 arrayinner = arrayinner + 1; 14 arrayinner + 1 = median; 15 16 17 18 那么这个程序有没有什么改进的地方呢？当然存在，如果发现在一次遍历循环之中，如果没有发生移位的现象，那么是不是可以判断这个排序可以结束了呢？朋友们可以好好思考一下这个问题？cpp view plaincopy19 void bubble_sort(int array, int length) 20 21 int inner = 0, outer = 0; 22 int median = 0; 23 int flag = 1; 24 25 if(NULL = array | 0 = length) 26 return; 27 28 for(outer = length-1; outer = 1 & flag; outer -) 29 flag = 0; 30 31 for(inner = 0; inner arrayinner + 1) 33 median = arrayinner; 34 arrayinner = arrayinner + 1; 35 arrayinner + 1 = median; 36 37 if(flag = 0) 38 flag = 1; 39 40 41 42 （2） 插入排序 插入排序的意思就是说，我们把数据分成两个部分，一部分是已经排好序的数据，一部分是当前还没有完成排序的数据。那么这么说来的话，排序的过程是不是就是把没有排序的数据逐个插入到已经排好序的队列中的过程呢。大家可以自己先试一下，然后再看看我的代码对不对？cpp view plaincopy43 void insert_sort(int array, int length) 44 45 int inner = 0; 46 int outer = 0; 47 int median = 0; 48 if(NULL = array | 0 = length) 49 return; 50 51 for(outer = 1; outer = 1; inner -) 53 if(arrayinner = 1; step -=2) 73 for(int index = 0; index step; index +) 74 if(length -1) (index + step) 75 continue; 76 else 77 outer = index + step; 78 while( (outer + step) = (index + step); outer -= step) 83 for(inner = index; inner = arrayinner + step) 85 median = arrayinner; 86 arrayinner = arrayinner + step; 87 arrayinner + step = median; 88 89 90 91 9