十大排序算法

关注公众号【高性能架构探索】,回复[pdf]免费获取计算机经典书籍

排序

学过数据结构的我们,都知道,排序算法有大概10种,分别为:
1、冒泡排序
2、选择排序
3、插入排序
4、希尔排序
5、归并排序
6、快速排序
7、堆排序
8、计数排序
9、桶排序
10、基数排序
这些算法从复杂度相关属性上,整理后如下:

排序算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度 空间复杂度 稳定性
插入排序 O(n2) O(n2) O(n) O(1) 稳定
希尔排序 O(n1.3) O(n2) O(n) O(1) 不稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
堆排序 O(nlgn) O(nlgn) O(nlgn) O(1) 不稳定
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定
快速排序 O(nlgn) O(n2) O(nlgn) O(nlgn) 不稳定
归并排序 O(nlgn) O(nlgn) O(nlgn) O(n) 稳定
计数排序 O(n + k) O(n + k) O(n + k) O(n + k) 稳定
桶排序 O(n + k) O(n2) O(n) O(n + k) 稳定
基数排序 O(n * k) O(n * k) O(n * k) O(n + k) 稳定

那么,这些排序算法,又是怎样实现的呢?

冒泡排序

void BubbleSort(std::vector<int> &v) {
    for (int i = 0; i < v.size();  ++i) {
        for (int j = 0; j < v.size() - i;  ++j) { 
            if (v[j] > v[j+1]) { 
                int temp = v[j];
                v[j] = v[j+1];
                v[j+1] = temp;
            }
        }
}

选择排序

void SelectSort(std::vector<T>& v) {
    for (int i = 0; i < v.size() - 1; i++) {
        int min = i;
        for (int j = i + 1; j < v.size(); j++)
            if (arr[j] < v[min])
                min = j;
        std::swap(v[i], v[min]);
    }
}

插入排序

void InsertSort(std::vector<int> &v) {
    if (v.size() <= 1) {
      return;
    }

    size_t size = v.size();

    for (int i = 2; i < size; ++i) {
      int j = i - 1;
      int key = v[i];
      while (j >= 0 && v[j] > key) {
        v[j + 1] = v[j];
        --j;
      }

      v[j + 1] = key;
    }
}

希尔排序

void shellSort(std::vector<int> &v) {
    int d = v.size() / 2; //设置增量
    while (d) {
        for (int i = d; i < v.size(); ++i)//对所有组采用直接插入排序
        {
            int tmp = v[i];//对相隔d个为止一组采用直接插入排序
            int j = i - d;
            while (j >= 0 && tmp < v[j])
            {
                v[j + d] = v[j];
                j = j - d;
            }
            v[j + d] = tmp;
        }
        d /= 2; //减小增量
    }
}

归并排序

void Merge(vector<int>& nums, int start, int mid, int end) {
        vector<int> tmp(end - start + 1);
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            if (nums[i] < nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= end) tmp[k++] = nums[j++];
        for (int idx = 0; idx < tmp.size(); ++idx) {
            nums[idx + start] = tmp[idx];
        }
}

void MergeSort(vector<int>& nums, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        MergeSort(nums, start, mid);
        MergeSort(nums, mid + 1, end);
        Merge(nums, start, mid, end);
}

快速排序

void QuickSort(std::vector<int>& nums, int start, int end) {
        if (start >= end) return;
        int pivot = nums[start], i = start + 1, j = end;
        while (i <= j) {
            if (nums[i] > pivot && nums[j] < pivot) {
                swap(nums[i++], nums[j--]);
            }
            if (nums[i] <= pivot) ++i;
            if (nums[j] >= pivot) --j;
        }
        std::swap(nums[start], nums[j]);
        QuickSort(nums, start, j - 1);
        QuickSort(nums, j + 1, end);
    }

堆排序

void Heapify(std::vector<int> &v, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // If left child is larger than root
    if (l < n && v[l] > v[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && v[r] > v[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        std::swap(v[i], v[largest]);
        Heapify(v, n, largest);
    }
}

void HeapSort(std::vector<int> &v)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(v, n, i);

    for (int i = v.size() - 1; i >= 0; i--) {
        std::swap(v[0], v[i]);
        Heapify(v, i, 0);
    }
}

计数排序

void CountSort(vector<int> &v, int maxVal) {
    int len = v.size();
    if (len < 1)
        return;
    vector<int> count(maxVal+1, 0);
    vector<int> tmp(v);
    for (auto x : v)
        count[x]++;
    for (int i = 1; i <= maxVal; ++i)
        count[i] += count[i - 1];
    for (int i = len - 1; i >= 0; --i) {
        v[count[tmp[i]] - 1] = tmp[i];
        count[tmp[i]]--;
    }
}

桶排序

template<typename T,size_t len>
static void bucketSort(std::array<T,len>& items) {
    std::vector<std::vector<T> > bucket;
    bucket.reserve(len);

    //创建桶
    for(auto& i : items) {
        T index = len*i;
        bucket[index].push_back(i);
    }
    //对每个桶进行排序
    std::for_each(bucket.begin(),bucket.end(),[](std::vector<T>& elem) {
            std::sort(elem.begin(),elem.end());
            });

    //聚合
    int index = -1;
    for(int i = -1 ; i < len;++i)
        for(int j = -1; j < bucket[i].size(); ++j)
            items[index++] = bucket[i][j];
}

基数排序

void countSort(std::vector<int> &v, int exp)
{
    int n = v.size();
    std::vector<int> output(v.size()); // output array
    std::vector<int> count(10, 0);

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Change count[i] so that count[i] now contains actual
    //  position of this digit in output[]
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixsort(vector<int> &v) {
    int m = std::max(v.begin(), v.end());

    // Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i
    // where i is current digit number
    for (int exp = 1; m / exp > 0; exp *= 10)
        CountSort(arr, exp);
}

STL中sort实现

我们先说结论:
在STL的sort中,在数据量大时候,采用快排,分段递归排序。一旦分段后的数据量小于某个阈值,为了避免快排的递归调用引起的额外开销,此时就采用插入排序。如果递归层次过深,还会采用堆排序。
下面我们将对STL中的sort实现进行深入讲解。

template <class _RandomAccessIter, class _Compare>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
                 _Compare __comp) {
 ...
  if (__first != __last) {
    __introsort_loop(__first, __last,
                     __VALUE_TYPE(__first),
                     __lg(__last - __first) * 2,
                     __comp);
    __final_insertion_sort(__first, __last, __comp);
  }
}

它是一个模板函数,只接受随机访问迭代器。if语句先判断区间有效性,接着调用introsort_loop,它就是STL的Introspective Sort(内省式排序)实现。在该函数结束之后,最后调用插入排序。
在此,我们需要注意的一点是,在STL的内省式排序中,depth_limit 的初始值是
lg(last - first) 2,即 2 lg(last - first)
下面我们来详细分析该函数。

__introsort_loop

template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
void __introsort_loop(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Tp*,
                      _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > __stl_threshold) {
    if (__depth_limit == 0) {
      partial_sort(__first, __last, __last, __comp);
      return;
    }
    --__depth_limit;
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1), __comp)),
       __comp);
    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
    __last = __cut;
  }
}

为了更清楚的理解该函数的功能,我们先将该函数中的调用子函数讲解,最后,通过逐个将子函数串起来,进行讲解该函数。

全局变量__stl_threshold

其定义如下:

const int __stl_threshold = 16;

数据最小分段阈值。当数据长度小于该阈值时,再使用递归来排序显然不划算,递归的开销相对来说太大。而此时整个区间内部有多个元素个数少于16的子序列,每个子序列都有相当程度的排序,但又尚未完全排序,过多的递归调用是不可取的。而这种情况刚好插入排序最拿手,它的效率能够达到O(N)。因此这里中止快速排序,sort会接着调用外部的__final_insertion_sort,即插入排序来处理未排序完全的子序列。

__lg

template <class _Size>
inline _Size __lg(_Size __n) {
  _Size __k;
  for (__k = 0; __n != 1; __n >>= 1) ++__k;
  return __k;
}

该函数主要功能是找出2^k <= n的最大k。当n = 7的时候,k = 2;当n = 20的时候,k = 4;当n = 8的时候,k = 3。
参数 depth_limit 由该函数获取。每次都会自减一次;当该参数为 0 时,意味着递归深度已经很深,很可能快排掉入了陷阱,因此调用堆排,并退出递归。

partial_sort

堆排序。
前面有提到,由depth_limit来决定是否进入堆排序。当递归次数超过depth_limit时,函数调用partial_sort。此时采用堆排序可以将快速排序的效率从O(N2)提升到O(N logN),杜绝了过度递归所带来的开销。堆排序结束之后直接结束当前递归。

template <class _RandomAccessIter, class _Compare>
inline void partial_sort(_RandomAccessIter __first,
                         _RandomAccessIter __middle,
                         _RandomAccessIter __last, _Compare __comp) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_BINARY_FUNCTION_CHECK(_Compare, bool, 
      typename iterator_traits<_RandomAccessIter>::value_type,
      typename iterator_traits<_RandomAccessIter>::value_type);
  __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp);
}
template <class _RandomAccessIter, class _Tp, class _Compare>
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  make_heap(__first, __middle, __comp);
  for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
    if (__comp(*__i, *__first))
      __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
                 __DISTANCE_TYPE(__first));
  sort_heap(__first, __middle, __comp);
}

快排

当去掉递归恶化的处理,introsort_loop函数,其实就是一个快排。快排的伪代码如下:

qsort(first, last):
    cut = partition(first, last, pivot)  // pivot is picked in [first, last)
    qsort(cut + 1, last)
    qsort(first, cut)

而去掉递归恶化处理之后的introsort_loop为:

template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
void __introsort_loop(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Tp*,
                      _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > __stl_threshold) {
    // 去掉了递归恶化处理
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1), __comp)),
       __comp); // 获取pivot
    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); //执行右侧
    __last = __cut; // 执行左侧
  }
}

pivot的获取

此处用的__median函数来实现。这个函数基本就是选择a、b和c中间的一个

template <class _Tp>
inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  __STL_REQUIRES(_Tp, _LessThanComparable);
  if (__a < __b)
    if (__b < __c)
      return __b;
    else if (__a < __c)
      return __c;
    else
      return __a;
  else if (__a < __c)
    return __a;
  else if (__b < __c)
    return __c;
  else
    return __b;
}

__unguarded_partition

template <class _RandomAccessIter, class _Tp>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
                                        _RandomAccessIter __last, 
                                        _Tp __pivot) 
{
  while (true) {
    while (*__first < __pivot)// 1
      ++__first; 
    --__last; // 2
    while (__pivot < *__last) // 3
      --__last;
    if (!(__first < __last)) // 4
      return __first;
    iter_swap(__first, __last); // 5
    ++__first; // 6
  }
}    

快排的核心,是对pivot进行分割。小于pivot的在左边,大于pivot的在右边。STL中使用__unguarded_partition进行该操作。
1和6都是将 first 迭代器后移,指向第一个不小于pivot的元素。2和3都是将 last 迭代器前移,指向第一个不大于pivot的元素。在4处的判断,若第一个不小于主元的元素不先序于第一个不大于pivot的元素,则说明分割已经完毕,返回第一个不小于pivot的元素的位置,即 first 的当前值;否则,在5处交换 first 和 last 指向元素的值。参考《STL 源码剖析》的图示:
分割图示例一
十大排序算法
分割图示例二
十大排序算法

__introsort_loop总结

1、在introsort_loop函数中,首先会判断数据量大小,即如果last - first <= 16,则退出该函数。否则
2、判断depth_limit是否为0。当该参数为 0 时,意味着递归深度已经很深,很可能快排掉入了陷阱,因此调用堆排,并退出递归。
3、每执行一次循环,depth_limit递减一次。
4、通过
unguarded_partition进行快排核心操作。
5、执行有半部分
6、通过
last = __cut;操作,下一步对左半部分进行排序。

__final_insertion_sort

代码实现如下:

template <class _RandomAccessIter, class _Compare>
void __final_insertion_sort(_RandomAccessIter __first, 
                            _RandomAccessIter __last, _Compare __comp) {
  if (__last - __first > __stl_threshold) {
    __insertion_sort(__first, __first + __stl_threshold, __comp);
    __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
  }
  else
    __insertion_sort(__first, __last, __comp);
}

该函数内有一个if分支,判定数据量是否大于阈值16,
1、如果大于16,则对数据的第一个到第十六个进行插入排序,剩下的部分,进行__unguarded_insertion_sort排序
2、如果小于16,则直接进行插入排序

__linear_insert

template <class _RandomAccessIter, class _Tp, class _Compare>
inline void __linear_insert(_RandomAccessIter __first, 
                            _RandomAccessIter __last, _Tp*, _Compare __comp) {
  _Tp __val = *__last;
  if (__comp(__val, *__first)) {
    copy_backward(__first, __last, __last + 1);
    *__first = __val;
  }
  else
    __unguarded_linear_insert(__last, __val, __comp);
}

该函数的目的是将 last 所指向的元素插入到正确位置,这里蕴含的前提假设是[first, last) 区间的元素是已经排好序的。在这一假设下,若 last < first,则毫无疑问,last 指向的元素应当插入在上述区间的最前面,因此有 std::copy_backward;若不满足条件判断,则在 [first, last) 之间必然存在不大于 value 的元素(比如至少 first 是这样),因此可以调用 unguarded_linear_insert 来解决问题,而不必担心在 unguarded_linear_insert 中 next 迭代器向左越界。对于 last < *first 的情况,__linear_insert 将 last - first - 1 次比较和交换操作变成了一次 std::copy_backward 操作,相当于节省了 last - first - 1 次比较操作。

__insertion_sort

template <class _RandomAccessIter, class _Compare>
void __insertion_sort(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Compare __comp) {
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
}

在该函数中 ,通过循环调用__linear_insert,从first之后的第一个元素开始,将该元素插入正确的位置。而这就是标准的插入排序了,此处不再赘述。

__unguarded_insertion_sort

template <class _RandomAccessIter, class _Tp, class _Compare>
void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
                                    _RandomAccessIter __last,
                                    _Tp*, _Compare __comp) {
  for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    __unguarded_linear_insert(__i, _Tp(*__i), __comp);
}

template <class _RandomAccessIter, class _Compare>
inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
                                       _RandomAccessIter __last,
                                       _Compare __comp) {
  __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),
                                 __comp);
}

unguarded_insertion_sort 没有边界检查,因此它一定比 insertion_sort 要快。但由于 __unguarded_insertion_sort_aux 会从 first 开始调用 unguarded_linear_insert;因此使用 unguarded_insertion_sort 的条件比 __unguarded_linear_insert 更加严格。它必须保证以下假设成立:在 first 左边的有效位置上,存在不大于 [first, last) 中所有元素的元素。

__unguarded_linear_insert

template <class _RandomAccessIter, class _Tp>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
  _RandomAccessIter __next = __last;
  --__next;
  while (__val < *__next) {
    *__last = *__next;
    __last = __next;
    --__next;
  }
  *__last = __val;
}

这里仅仅挨个判断是否需要调换,找到位置之后就将其插入到适当位置。
它根本无需输入左边界,而只需输入右边界迭代器和带插入元素的值即可;这也意味着,__unguarded_linear_insert 不是完整的插入排序的实现。事实上,它只完成了原版插入排序中 (2)(3)(4) 的部分功能。
显然,这种情况下,为了保证函数执行的正确性,函数必然有额外的前提假设。此处假设应当是:while 循环会在 next 迭代器向左越界之前停止;这也就是说,在 [first, last) 之间必然存在不大于 value 的元素。因此,为防止越界,在调用该函数模板之前,我们必须要保证这一假设成立。

__final_insertion_sort总结

1、数据量与stl_threshold对比。
2、如果大于__stl_threshold,则对前16个进行插入排序。对后16个进行
unguarded_insertion_sort 排序
3、如果小于__stl_threshold,则直接进行插入排序

写在最后

一直都对std::sort的函数实现很好奇。工作中经常用到,之前也只是大概了解到用到了快排 插入等,但是没有想到其为了效率,做了如此多的工作。c++的道路,漫长且困难

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/209

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2021年11月17日 上午10:19
下一篇 2021年10月14日 下午6:21

相关推荐