排序算法总结（一）

时间：2014-03-14 18:57:59 收藏：0 阅读：449

查找和排序是计算机应用中较为基础同时也很重要的两个组成成分。特别是当今网络如此盛行，Internet上充斥着各种各样的数据，图片，文本，音视频等，用户如何搜寻自己想要的数据，服务者如何及时有效的将用户的需求返回，都需要这些基础算法的帮助。在本人复习数据结构的时候，特意结合网上各位大牛的神贴，以及自己的一些理解，整理了一下一些常用的查找和排序算法，如有雷同之处，请各位大牛多多包涵。

基于比较的算法：

1. 选择排序

在众多的排序算法中，选择排序应该是最容易理解的一个算法了。其平均时间复杂度为O(n^2)，空间复杂度则是O(1), 并且选择排序是不稳定的排序(值相同的两个元素在排序之后相互位置可能发生变化)。

选择排序是一个递归的查找比较算法：

（1）遍历一次尚未排序的数组元素，找到其中最大的元素，

（2）将其与尚未排序的数组最后一个元素互换

（3）将找到的最大元素从未排序的数组元素中取出

（4）其余未排序数组元素，重复操作（1），直到未排序数组中没有剩余元素。

 1 void insertion_sort(int a[],int length)
 2 {
 3      for(int i=length -1; i>0;i--)
 4      {
 5          int maxData = a[i];
 6          int index =0;
            // 寻找最大元素
 7          for(int j=0;j<i;j++)
 8          {
 9              if(maxData < a[j])
10              {
11                  maxData = a[j];
12                  index =j;
13              }
14          }
            // 是否需要交换位置
15          if(maxData != a[i])
16          {
17            swap(a[i],a[index]);
18          }
19      }
20 }

selection_sort

2. 冒泡排序

冒泡排序也是一个比较基础的排序算法，基于比较。其平均时间复杂度为O(n^2), 空间复杂度O(1), 稳定的排序。

冒泡排序算法的运作如下：（此处参考百度百科，冒泡排序的介绍：http://baike.baidu.com/link?url=JVltAqLpNLpQuk7LR1CnJGykNKTr1jYFWoDSj1vBuZPVXzQ8gC5JUOYnoFOSixWF）

(1) 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

(2) 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

(3) 针对所有的元素重复以上的步骤，除了最后一个。

(4) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 1 void bubble_sort(int a[],int length)
 2 {
 3      for(int i=0;i<length -1; i++)  // 外层循环为需要递归的次数 
 4      {
 5          for(int j = 0; j<length -i -1; j++) // 内层循环用于调整相邻节点的位置 
 6          {
 7                  if(a[j]>a[j+1])
 8                     swap(a[j],a[j+1]);
 9          }
10      }
11 }

bubble_sort

需要指出的是，在冒泡排序中，往往不需要进行n-1次调整，数组就可能已经是有序的了，这时候继续比较就显得比较浪费，而且效率也低。通常的做法是在内循环中加入一个哨兵标志，如果当前循环中没有相互交换的元素，则认为数组已经有序，可以结束排序，其运作如下：

(1) 比较相邻的元素。如果第一个比第二个大，就交换他们两个,进入步骤(2)

(2) 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

(3) 针对所有的元素重复以上的步骤，除了最后一个。如果上面的比较中没有出现交换操作，算法退出。否则，进入步骤(4).

(4) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

其实现如下：

 1 void supper_bubble_sort(int a[],int length)
 2 {
 3      for(int i=0;i<length -1; i++)  // 外层循环为需要递归的次数 
 4      {
 5          bool sorted =false; 
 6          for(int j = 0; j<length -i -1; j++) // 内层循环用于调整相邻节点的位置 
 7          {
 8                  if(a[j]>a[j+1])
 9                  {
10                     swap(a[j],a[j+1]);
11                     sorted = true;  // 本次循环过程中，出现了交换 
12                  }
13          }
14          if(sorted == false)  // 本次过程中没有出现数据交换，算法提前结束 
15              break;
16      }
17 }

supper_bubble_sort

3. 插入排序

相对比较基础的一个排序算法。莫非大牛们都比较喜欢“斗地主”，为嘛都拿打扑克来做例子！！（不过确实很形象~）

这个算法呢，理解起来比较容易，不过写程序的时候，因为移位操作比较多，在边界条件的选择上往往容易出问题。

要注意从数组起始位置开始查找，还是数组最后记录的位置。

算法的时间复杂度也是0(n^2),空间复杂度O(1),稳定的排序。

 1 /**************************************
 2  * Insertion_sort
 3  * 每次从已插入的数组最后一个元素开始比较，
 4  * 如果新的元素比最后一个元素大，则直接放入
 5  * 已排序队列的最后位。否则，将新元素与当前
 6  * 元素互换位置递归查找，直到找到第一个比新
 7  * 元素小的元素，并将新的元素插入到该位置 
 8 **************************************/
 9 void Insertion_sort(int a[],int length)
10 {
11      for(int i =1;i<length; i++)
12      {
13           int key = a[i];
14           int j=i -1;
15           while(j>=0 && a[j]>a[j+1])
16           {
17              swap(a[j],a[j+1]); // 循环移位操作 
18              j--;
19           }
20           if(a[j]>key) //插入新元素 
21             a[j] = key;
22      }
23 }

insertion_sort

排序算法总结（一）,布布扣,bubuko.com

原文：http://www.cnblogs.com/double-win/p/3598573.html