数据结构和算法11 之基础排序

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构和算法11 之基础排序

shy丶gril 2016-05-26 11:01:02 浏览1169
展开阅读全文

前10节我们学习了一些经典的数据结构,从这节开始,我们将学习一些排序算法。这一节我们先学习几个基础排序算法:冒泡排序,选择排序和插入排序。

1. 冒泡排序

        冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。冒泡排序算法的基本流程是:每一轮从头开始两两比较,将较大的项放在较小项的右边,这样每轮下来保证该轮最大的数在最右边。

算法程序如下:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public void bubbleSort(int[] source) {  
  2.     for(int i = source.length - 1; i > 0; i--) {  
  3.         for(int j = 0; j < i; j++) {  
  4.             if(a[j] > a[j+1])  
  5.                 swap(source, j, j+1); //交换,具体实现略  
  6.         }  
  7.     }  
  8. }  

        冒泡排序算法还有个可以改进的地方,就是在算法中加入一个布尔变量标识该轮有没有进行数据的交换,若在某一次排序中未发现气泡位置的交换,则说明待排序的无序区中所有的项均已满足排序后的结果。

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public void bubbleSort(int[] source) {  
  2.     boolean exchange;  
  3.     for(int i = source.length - 1; i > 0; i--) {  
  4.         exchange = false;  
  5.         for(int j = 0; j < i; j++) {  
  6.             if(a[j] > a[j+1])  
  7.                 swap(source, j, j+1);  
  8.             exchange = true;  
  9.         }  
  10.         if(!exchange) return;  
  11.     }  
  12. }  

        算法分析:冒泡排序最好的情况是初始状态是正序的,一次扫描即可完成排序,所以最好的时间复杂度为O(N);最坏的情况是反序的,此时最坏的时间复杂度为O(N2)。平均情况,每轮N/2次循环,N轮时间复杂度为O(N2)。

        算法是稳定的,因为当a=b时,由于只有大于才做交换,故a和b的位置没有机会交换,所以算法稳定。

        空间复杂度为O(1),不需要额外空间。

2. 选择排序

选择排序改进了冒泡排序,将必要的交换次数从O(n2)减少到O(n),但是比较次数仍保持为O(n2)。冒泡排序每比较一次就可能交换一次,但是选择排序是将一轮比较完后,把最小的放到最前的位置(或者把最大的放到最后)。选择排序为大记录量的排序提出了一个非常重要的改进,因为这些大量的记录需要在内存中移动,这就使交换的时间和比较的时间相比起来,交换的时间更为重要。(一般在Java中不是这种情况,因为java中只是改变了引用位置,而实际对象的位置并没有发生改变。)

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public void selectSort(int[] source) {    
  2.     int min;    
  3.     for(int i = 0; i < source.length; i++) {    
  4.         min = i;    
  5.         for(int j = i + 1; j < source.length; j++) {    
  6.             if(a[j] < a[min])    
  7.                 min = j;      
  8.         }    
  9.         swap(i, min);    
  10.     }    
  11. }    

        算法分析:选择排序最好和最坏的情况一样运行了O(N2)时间,但是选择排序无疑更快,因为它进行的交换少得多,当N值较小时,特别是如果交换时间比比较时间大得多时,选择排序实际上是相当快的。平均复杂度也是O(N2)。

        算法是不稳定的,假设a=b,且a在b前面,而某轮循环中最小值在b后面,而次最小值需要跟a交换,这时候b就在a前面了,所以选择排序是不稳定的。

        空间复杂度为O(1),不需要额外的空间。

3. 插入排序

        插入排序的实现步骤为:从第一个元素开始,该元素可以认为已经被排序 -> 取出下一个元素,在已经排序的元素序列中从后向前扫描 -> 如果该元素小于前一个元素,则将两者调换,再与前一个元素比较–> 重复第三步,直到找到已排序的元素小于或者等于新元素的位置 -> 将新元素插入到该位置中 -> 重复第二步

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public void insertSort(int[] source) {  
  2.     for(int i = 1; i < source.length; i++) {  
  3.         for(int j = i; (j > 0) && (source[j] < source[j-1]); j--) {  
  4.             swap(j, j-1);  
  5.         }  
  6.     }  
  7. }  

        算法分析:插入排序最好的情况是序列已经是升序排列了,在这种情况下,需要进行N-1次比较即可,时间复杂度为O(N),最坏的情况是序列降序排列,这时候时间复杂度为O(N2)。因此插入排序不适合对于数据量比较大的排序应用。但是如果需要排序的数据量很小(如小于千),那么插入排序还是一个不错的选择。插入排序平均时间复杂度为O(N2),但是它要比冒泡排序快一倍,比选择排序还要快一点,经常被用在较复杂的排序算法的最后阶段,例如快速排序。

        算法是稳定的,假设a=b,且a在b的前面,其排序位置必然比b先确定,而后面再插入b时,必然在a的后面,所以是稳定的。

        空间复杂度为O(1),不需要额外的空间。

        以上三种排序是排序算法中比较基础的,也相对容易理解,就介绍到这里。如有错误,欢迎留言指正~+

转载:http://blog.csdn.net/eson_15/article/details/51154989

网友评论

登录后评论
0/500
评论
shy丶gril
+ 关注