常见排序算法 [整理]

 

名称	复杂度	说明	备注
冒泡排序 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）。

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)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

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）的复杂度。

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

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;
            }
      }
}

 

快速排序

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

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;
}