基本排序算法

2018-09-15 分类编程基础, 数据结构与算法作者云海鹰影 ~8.25K 字

1. 算法复杂度
2. 1. 冒泡排序(Bubble Sort):
3. 2. 选择排序(Selection Sort):
4. 3. 插入排序(Insert Sort):
5. 4. 希尔排序 (Shell Sort):
6. 5. 快速排序（Quick Sort):
7. 6. 归并排序(Merge Sort):
8. 7. 梳排序(Comb sort):

以前存于百度文章上的东西，刚学编程那会儿总结的基础知识。

基本的排序方法，主要包括冒泡、选择、插入、希尔、快速、归并和梳排序。

算法复杂度

冒泡、选择、插入排序时间复杂度均为O(N^2)，
快速、归并排序时间复杂度为O(N logN)，
希尔排序的时间复杂度为O(N^(1.5))
键索引排序的时间复杂度为O(N) （依然可以用上面的算法，只是排序的不是容器中的元素，而是其索引，即Indirect Sort）

/****************************公共部分, 简单宏定义，冒泡，选择排序用到*******************************
typedef int Item;
#define less(A, B) ((A) < (B))
#define exch(A, B) {Item t = A; A = B; B = t;}
#define compexch(A, B) if(less(B, A)) exch(A, B)    //若A大于B，则交换A、B
***************************************************************************************************/

1. 冒泡排序(Bubble Sort):

一趟循环从后向前依次比较相邻元素，如果反序则交换位置，就像冒泡一样。(当然也可以向后冒泡)。通过一趟排序确定开头(或结尾)的元素，然后循环处理依次确定每个元素。
优点：简单

void bubble(Item* a, int l, int r)
{
    int i, j;
    for(i = l; i < r; i++)
        for(j = r; j > i; j--)        //从右向左
            compexch( a[j-1], a[j] );
}

2. 选择排序(Selection Sort):

选择排序是通过一趟排序确定最小(或最大)元素的当前位置然后和开头交换，然后循环处理依次确定每个元素
优点：一趟排序只交换一次元素位置即确定一个元素，比冒泡快，对于大型对象速度较快消耗资源较小

void selection(Item* a, int l, int r)
{
    int i, j;
    for(i = l; i < r; i++)
    {
        int min = i;
        for(j = i + 1; j <= r; j++)
            if(less(a[j], a[min]))    min = j;
        exch(a[i], a[min]);
    }
}

3. 插入排序(Insert Sort):

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
(1)从第一个元素开始，该元素可以认为已经被排序
(2)取出下一个元素，在已经排序的元素序列中从后向前扫描
(3)如果该元素（已排序）大于新元素，将该元素移到下一位置
(4)重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
(5)将新元素插入到该位置中
(6)重复步骤2~5

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

//c++语言版本的插入排序。为了支持list使用了std::advance()。
#include <iterator>
 
template<typename biIter>
void insertion_sort(biIter begin, biIter end)
  {
    typedef typename std::iterator_traits<biIter>::value_type value_type;
    biIter bond = begin; std::advance(bond, 1);
 
    for(; bond!=end; std::advance(bond, 1)) {
  value_type key = *bond; //记录原始位置的值(留出空位)
  biIter ins = bond; //标记插入位置
  biIter pre = ins; std::advance(pre, -1);
  while(ins!=begin && *pre>key) {
   *ins = *pre;
   std::advance(ins, -1);
   std::advance(pre, -1);
  }
  *ins = key;
    }
  }

4. 希尔排序 (Shell Sort):

希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。
通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
步长可以有各种取法，但需注意：应使步长序列中的值没有除1以外的公因子，并且最后一个步长必须等于1。

//c++语言版本的希尔排序。

template<typename RandomIter, typename Compare>
void shell_sort(RandomIter begin, RandomIter end, Compare cmp)
  {
    typedef typename std::iterator_traits<RandomIter>::value_type value_type;
    typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;
 
    diff_t size = std::distance(begin, end);
    diff_t step = size / 2;
    while(step >= 1) {
      for(diff_t i=step; i<size; ++i) {
        value_type key = *(begin+i);
        diff_t ins = i;
        while(ins>=step && cmp(key, *(begin+ins-step)) ) {
          *(begin+ins) = *(begin+ins-step);
          ins -= step;
        }
        *(begin+ins) = key;
      }
      if(step == 2)
        step = 1;
      else
        step = static_cast<diff_t>(step / 2.2);
    }
  }
 
template<typename RandomIter>
void shell_sort(RandomIter begin, RandomIter end) {
    typedef typename std::iterator_traits<RandomIter>::value_type value_type;
    shell_sort(begin, end, std::less<value_type>() );
}

5. 快速排序（Quick Sort):

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
(1) 从数列中挑出一个元素，称为 “基准”（pivot），
(2) 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边)。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
(3) 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束。因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

快速排序的时间复杂度为O(N logN)
在最坏情况下，快速排序使用约(N^2)/2次比较
快速排序需要栈空间来实现递归，经过改进栈的最大深度可降为O(log n)

//这是一个使用标准模版库（STL）的泛型式快速排序版本。
#include <functional>
#include <algorithm>
#include <iterator>
 
template< typename biIter, typename Compare >
void quick_sort( biIter first, biIter last, Compare cmp ) {
  if( first != last ) {
    biIter left  = first;
    biIter right = last;
    biIter pivot = left++;
 
    while( left != right ) {
      if( cmp( *left, *pivot ) ) {
         ++left;
      }
   else {
         while( (left != right) && cmp( *pivot, *right ) )
           right--;
         std::iter_swap( left, right );
      }
    }
 
    if (cmp( *pivot, *left ))
         --left;
    std::iter_swap( first, left );
 
    quick_sort( first, left, cmp );
    quick_sort( right, last, cmp );
  }
}
 
template< typename biIter >
inline void quick_sort( biIter first, biIter last ) {
 typedef typename std::iterator_traits< biIter >::value_type value_type;
 quick_sort( first, last, std::less_equal< value_type >() );
}

6. 归并排序(Merge Sort):

归并排序（以从大到小为例）：
假设一个容器内，前半部分与后半部分分别有序（即两部分分别排序完成），将前面一半复制到一个新的容器里（原容器空出一半），然后将原容器里的后半部分元素跟新容器里的元素依次比较，较小的放到原容器前面去，最后有剩余的一个容器剩下的元素全部是最大且有序的，直接全部copy到原容器里。这样整个容器就变得有序了。
而前半部分与后半部分我们依然可以假设他们各可以分成前后有序的两段，递归进行归并，最后则可以得到一个只有2元素的容器，可以直接比较交换了。

//这是一个使用标准模版库（STL）的泛型式快速排序版本。使用了std::advance(), std::distance(), std::iter_swap
#include <functional>
#include <algorithm>
#include <iterator>

template< typename biIter, typename Compare >
void merge_sort(biIter First, biIter Last, Compare cmp) 
{
 // merge_sort [First,Last)
 typedef typename std::iterator_traits<biIter>::difference_type diff_t;
 typedef typename std::iterator_traits<biIter>::value_type value_type;
 diff_t count=std::distance(First, Last);
 
 if(count>=2)
 {
  biIter Mid(First); std::advance(Mid, count/2);
  if(count==2)
  {
   // order two one-element partitions
   if(cmp(*First, *Mid))
    std::iter_swap(First, Mid);
  }
  else
  {
   _Temp_iterator<value_type> tempbuf(count/2);
   _STDEXT unchecked_copy(First, Mid, tempbuf._Init());
   
   biIter First1(tempbuf._First), First2(Mid), Dest(First);
   while (First1 != tempbuf._Last && First2 != Last)
   {
    if (cmp(*First2, *First1))
    {
     *Dest = *First2;
     std::advance(First2);
    }
    else
    {
     *Dest = *First1;
     std::advance(First1);
    }
    std::advance(Dest);
   }
   STDEXT unchecked_copy(First1, tempbuf._Last, Dest); // copy any tail
   
   merge_sort(First, Mid, cmp);
   merge_sort(Mid, Last, cmp);
  }
 }
}

template<typename biIter>
void merge_sort(biIter begin, biIter end) {
    typedef typename std::iterator_traits<biIter>::value_type value_type;
    merge_sort(begin, end, std::less<value_type>() );
}

7. 梳排序(Comb sort):

梳排序是改良自泡沫排序和快速排序，其要旨在于消除乌龟，亦即在阵列尾部的小数值，这些数值是造成泡沫排序缓慢的主因。相对地，兔子，亦即在阵列前端的大数值，不影响泡沫排序的效能。
在泡沫排序中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为 1.3。在一次循环中，梳排序如同泡沫排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入阵列大致排序好，并以泡沫排序作最后检查及修正。

//c++语言版本的插入排序。使用了std::advance(), std::distance(), std::iter_swap
template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
    static const double shrink_factor = 1.247330950103979;
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type gap = std::distance(first, last);
    bool swaps = true;
 
    while ( (gap > 1) || (swaps == true) ){
        if (gap > 1)
            gap = static_cast<difference_type>(gap/shrink_factor);
 
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
 
        for ( ; itRight!=last; ++itLeft, ++itRight ){
            if ( (*itRight) < (*itLeft) ){
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}

云海鹰影