常见排序算法

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

常见排序算法

长征4号 2017-10-16 14:16:00 浏览774
展开阅读全文

 

名称 复杂度 说明 备注
冒泡排序 BubbleSort O(N*N)

将待排序的元素看作是竖着排列的  气泡  ,较小的元素比较轻,从而要往上浮


插入排序 InsertionSort O(N*N) 逐一取出元素,在已经排序的元素序列中从后向前扫描,放到适当的位置 起初,已经排序的元素序列为空
选择排序 SelcetionSort O(N*N) 首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此递归。
快速排序 QuickSort O(n*log2 (n)) 先选择中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(递归)。
堆排序 HeapSort O(n*log2 (n))

利用堆( heaps )这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或者大于)它的父节点。

近似完全二叉树
希尔排序 ShellSort

O(n1+   0< <1

选择一个步长 (Step) , 然后按间隔为步长的单元进行排序 . 递归 , 步长逐渐变小 , 直至为 1.


箱排序 BinSort O(n)

设置若干个箱子,把关键字等于   k   的记录全都装入到第   k   个箱子里   (   分配   )   ,然后按序号依次将各非空的箱子首尾连接起来   (   收集   )   

分配排序的一种:通过   "   分配   "      "   收集   "   过程来实现排序。

桶排序 BucketSort O(n)

桶排序的思想是把   [0      1)   划分为   n   个大小相同的子区间,每一子区间是一个桶。

分配排序的一种:通过   "   分配   "      "   收集   "   过程来实现排序。


冒泡排序

冒泡排序算法的思想:很简单,每次遍历完序列都把最大(小)的元素放在最前面,然后再对剩下的序列重复前面的一个过程,每次遍历完之后待排序序列就少一个元素,当待排序序列减小为只有一个元素的时候排序就结束了。因此,复杂度在最坏的情况下是O(N ^ 2)。
Java代码  收藏代码
  1. public static void BubbleSort(int[] array){  
  2.         
  3.       if(array==null || array.length==0){  
  4.             return;  
  5.       }  
  6.         
  7.       int size = array.length;  
  8.       for(int i=0; i<size-1; i++){  
  9.             boolean hasSwap = false;  
  10.             for(int j=i+1; j<size; j++){  
  11.                   if(array[j]<array[i]){  
  12.                         // swap  
  13.                         int temp = array[i];  
  14.                         array[i] = array[j];  
  15.                         array[j] = temp;  
  16.                         hasSwap = true;  
  17.                   }  
  18.                   if(!hasSwap){  
  19.                         break;  
  20.                   }  
  21.             }  
  22.       }  
  23. }  
 
 
选择排序
选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
Java代码  收藏代码
  1. public static void SelectionSort(int[] array){  
  2.         
  3.       if(array==null || array.length==0){  
  4.             return;  
  5.       }  
  6.         
  7.       int size = array.length;  
  8.       for(int i=0; i<size-1; i++){  
  9.             int minIndex = i;  
  10.             for(int j=i+1; j<size; j++){  
  11.                   if(array[j]<array[minIndex]){  
  12.                         minIndex = j;  
  13.                   }  
  14.             }  
  15.             // 将最小值置于最前端  
  16.             if(minIndex!=i){  
  17.                   int temp = array[minIndex];  
  18.                   array[minIndex] = array[i];  
  19.                   array[i] = temp;  
  20.             }  
  21.       }  
  22.         
  23. }  
 
*与冒泡排序的区别,交换次数。每次遍历找到最小值,只交换一次。冒泡是每次比较都进行交换。

插入排序
插入排序是最简单最直观的排序算法了,它的依据是:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止。
算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是1 + 2 + 3 + …… + N = O(N ^ 2)的复杂度。
Java代码  收藏代码
  1. public static void InsertionSort(int[] array){  
  2.         
  3.       if(array==null || array.length==0){  
  4.             return;  
  5.       }  
  6.         
  7.       int size = array.length;  
  8.       // 默认认为第一位是有序的  
  9.       for(int i=1; i<size; i++){  
  10.             int key = array[i];  
  11.             // 对有序列从后向前扫描  
  12.             int j=0;  
  13.             for(j=i-1; j>=0; j--){  
  14.                   if(key<array[j]){  
  15.                         array[j+1] = array[j];  
  16.                   }else{  
  17.                         break;  
  18.                   }  
  19.             }  
  20.             array[j+1] = key;  
  21.       }  
  22.         
  23. }  
 
 
希尔排序
shell排序是对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量 扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了。
Java代码  收藏代码
  1. public static void ShellSort(int array[])  
  2. {  
  3.       if(array==null || array.length==0){  
  4.             return;  
  5.       }  
  6.         
  7.       int temp;  
  8.       int size = array.length;  
  9.       // 增量从数组长度的一半开始,每次减小一倍  
  10.       for (int increment = size / 2; increment > 0; increment /= 2)  
  11.       {  
  12.             for (int i = increment; i < size; ++i)  
  13.             {  
  14.                   temp = array[i];  
  15.                   // 对一组增量为increment的元素进行插入排序  
  16.                   int j = 0;  
  17.                   for (j = i; j >= increment; j -= increment)  
  18.                   {  
  19.                         // 把i之前大于array[i]的数据向后移动  
  20.                         if (temp < array[j - increment])  
  21.                         {  
  22.                               array[j] = array[j - increment];  
  23.                         } else  
  24.                         {  
  25.                               break;  
  26.                         }  
  27.                   }  
  28.                   // 在合适位置安放当前元素  
  29.                   array[j] = temp;  
  30.             }  
  31.       }  
  32. }  
 
 
快速排序
快速排序的算法思想: 选定一个枢轴元素,对待排序序列进行分割,分割之后的序列一个部分小于枢轴元素,一个部分大于枢轴元素,再对这两个分割好的子序列进行上述的过程。
Java代码  收藏代码
  1. public static void QuickSort(int[] array, int low, int hight){  
  2.         
  3.       if(array==null || array.length==0){  
  4.             return;  
  5.       }  
  6.         
  7.       if(low<hight){  
  8.             int n = Partition(array, low, hight);  
  9.             QuickSort(array, 0, n);  
  10.             QuickSort(array, n+1, hight);  
  11.       }  
  12.         
  13. }  
  14. // 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,  
  15. // 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素  
  16. private static int Partition(int[] array, int low, int hight){  
  17.         
  18.       // 采用子序列的第一个元素为枢纽元素  
  19.       int pivot = array[low];  
  20.         
  21.       int temp = 0;  
  22.       while(low<hight){  
  23.               
  24.             // 从后往前在后半部分中寻找第一个小于枢纽元素的元素  
  25.             while(low<hight && array[hight]>=pivot){  
  26.                   hight--;  
  27.             }  
  28.             // 将这个比枢纽元素小的元素交换到前半部分  
  29.             temp = array[low];  
  30.             array[low] = array[hight];  
  31.             array[hight] = pivot;  
  32.               
  33.             // 从前往后在前半部分中寻找第一个大于枢纽元素的元素  
  34.             while(low<hight && array[low]<=pivot){  
  35.                   low++;  
  36.             }  
  37.             // 将这个比枢纽元素大的元素交换到后半部分  
  38.             temp = array[low];  
  39.             array[low] = array[hight];  
  40.             array[hight] = temp;  
  41.               
  42.       }  
  43.       // 返回枢纽元素所在的位置  
  44.       return low;  
  45. }  

来源:http://univasity.iteye.com/blog/1164713




本文转自夏雪冬日博客园博客,原文链接:http://www.cnblogs.com/heyonggang/archive/2013/05/08/3066927.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
长征4号
+ 关注