常见排序算法-阿里云开发者社区

名称	复杂度	说明	备注
冒泡排序 BubbleSort	O(N*N)	将待排序的元素看作是竖着排列的 “ 气泡 ” ，较小的元素比较轻，从而要往上浮
插入排序 InsertionSort	O(N*N)	逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置	起初，已经排序的元素序列为空
选择排序 SelcetionSort	O(N*N)	首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。
快速排序 QuickSort	O(n*log₂ (n))	先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。
堆排序 HeapSort	O(n*log₂ (n))	利用堆（ heaps ）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。	近似完全二叉树
希尔排序 ShellSort	O(n¹⁺ ^￡) 0<￡ <1	选择一个步长 (Step) , 然后按间隔为步长的单元进行排序 . 递归 , 步长逐渐变小 , 直至为 1.
箱排序 BinSort	O(n)	设置若干个箱子，把关键字等于 k 的记录全都装入到第 k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。	分配排序的一种：通过 " 分配 " 和 " 收集 " 过程来实现排序。
桶排序 BucketSort	O(n)	桶排序的思想是把 [0 ， 1) 划分为 n 个大小相同的子区间，每一子区间是一个桶。	分配排序的一种：通过 " 分配 " 和 " 收集 " 过程来实现排序。

冒泡排序

冒泡排序算法的思想：很简单，每次遍历完序列都把最大（小）的元素放在最前面，然后再对剩下的序列重复前面的一个过程，每次遍历完之后待排序序列就少一个元素，当待排序序列减小为只有一个元素的时候排序就结束了。因此，复杂度在最坏的情况下是O（N ^ 2）。

    Java代码  
     
   
public static void BubbleSort(int[] array){  
        
      if(array==null || array.length==0){  
            return;  
      }  
        
      int size = array.length;  
      for(int i=0; i<size-1; i++){  
            boolean hasSwap = false;  
            for(int j=i+1; j<size; j++){  
                  if(array[j]<array[i]){  
                        // swap  
                        int temp = array[i];  
                        array[i] = array[j];  
                        array[j] = temp;  
                        hasSwap = true;  
                  }  
                  if(!hasSwap){  
                        break;  
                  }  
            }  
      }  
}  

选择排序

选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

    Java代码  
     
   
public static void SelectionSort(int[] array){  
        
      if(array==null || array.length==0){  
            return;  
      }  
        
      int size = array.length;  
      for(int i=0; i<size-1; i++){  
            int minIndex = i;  
            for(int j=i+1; j<size; j++){  
                  if(array[j]<array[minIndex]){  
                        minIndex = j;  
                  }  
            }  
            // 将最小值置于最前端  
            if(minIndex!=i){  
                  int temp = array[minIndex];  
                  array[minIndex] = array[i];  
                  array[i] = temp;  
            }  
      }  
        
}  

*与冒泡排序的区别，交换次数。每次遍历找到最小值，只交换一次。冒泡是每次比较都进行交换。

插入排序

插入排序是最简单最直观的排序算法了，它的依据是：遍历到第N个元素的时候前面的N-1个元素已经是排序好的了，那么就查找前面的N-1个元素把这第N个元素放在合适的位置，如此下去直到遍历完序列的元素为止。
算法的复杂度也是简单的，排序第一个需要1的复杂度，排序第二个需要2的复杂度，因此整个的复杂度就是1 + 2 + 3 + …… + N = O（N ^ 2）的复杂度。

    Java代码  
     
   
public static void InsertionSort(int[] array){  
        
      if(array==null || array.length==0){  
            return;  
      }  
        
      int size = array.length;  
      // 默认认为第一位是有序的  
      for(int i=1; i<size; i++){  
            int key = array[i];  
            // 对有序列从后向前扫描  
            int j=0;  
            for(j=i-1; j>=0; j--){  
                  if(key<array[j]){  
                        array[j+1] = array[j];  
                  }else{  
                        break;  
                  }  
            }  
            array[j+1] = key;  
      }  
        
}  

希尔排序

shell排序是对插入排序的一个改装，它每次排序把序列的元素按照某个增量分成几个子序列，对这几个子序列进行插入排序，然后不断的缩小增量扩大每个子序列的元素数量，直到增量为一的时候子序列就和原先的待排列序列一样了，此时只需要做少量的比较和移动就可以完成对序列的排序了。

    Java代码  
     
   
public static void ShellSort(int array[])  
{  
      if(array==null || array.length==0){  
            return;  
      }  
        
      int temp;  
      int size = array.length;  
      // 增量从数组长度的一半开始,每次减小一倍  
      for (int increment = size / 2; increment > 0; increment /= 2)  
      {  
            for (int i = increment; i < size; ++i)  
            {  
                  temp = array[i];  
                  // 对一组增量为increment的元素进行插入排序  
                  int j = 0;  
                  for (j = i; j >= increment; j -= increment)  
                  {  
                        // 把i之前大于array[i]的数据向后移动  
                        if (temp < array[j - increment])  
                        {  
                              array[j] = array[j - increment];  
                        } else  
                        {  
                              break;  
                        }  
                  }  
                  // 在合适位置安放当前元素  
                  array[j] = temp;  
            }  
      }  
}  

快速排序

快速排序的算法思想：选定一个枢轴元素，对待排序序列进行分割，分割之后的序列一个部分小于枢轴元素，一个部分大于枢轴元素，再对这两个分割好的子序列进行上述的过程。

    Java代码  
     
   
public static void QuickSort(int[] array, int low, int hight){  
        
      if(array==null || array.length==0){  
            return;  
      }  
        
      if(low<hight){  
            int n = Partition(array, low, hight);  
            QuickSort(array, 0, n);  
            QuickSort(array, n+1, hight);  
      }  
        
}  
// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,  
// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素  
private static int Partition(int[] array, int low, int hight){  
        
      // 采用子序列的第一个元素为枢纽元素  
      int pivot = array[low];  
        
      int temp = 0;  
      while(low<hight){  
              
            // 从后往前在后半部分中寻找第一个小于枢纽元素的元素  
            while(low<hight && array[hight]>=pivot){  
                  hight--;  
            }  
            // 将这个比枢纽元素小的元素交换到前半部分  
            temp = array[low];  
            array[low] = array[hight];  
            array[hight] = pivot;  
              
            // 从前往后在前半部分中寻找第一个大于枢纽元素的元素  
            while(low<hight && array[low]<=pivot){  
                  low++;  
            }  
            // 将这个比枢纽元素大的元素交换到后半部分  
            temp = array[low];  
            array[low] = array[hight];  
            array[hight] = temp;  
              
      }  
      // 返回枢纽元素所在的位置  
      return low;  
}  

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

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

常见排序算法

热门文章

最新文章

相关电子书