排序算法

基于比较的排序

排序的稳定性：关键字相等的节点排序后仍保持在排序前的相对顺序，则称排序是稳定的

稳定排序：插入排序，冒泡排序，归并排序

不稳定排序：选择排序，快速排序，堆排序

插入排序

如其名，把一个数插入到一个已经排好的序列中

template <class Item>
void InsertSort(Item a[], int l, int r){
    int i,j;
    Item intsert;
    for(i = l + 1; i <= r; ++i){
        for(j = i-1, intsert = a[i]; j >= l && intsert < a[i]; j--) a[j+1] = a[j];
        a[j+1] = intsert;
    }
}

时间复杂度最佳，最坏，平均

空间复杂度

是稳定排序

适用于元素较少时的排序

冒泡排序

依次比较相邻元素

template <class Item>
void BubbleSort(Item a[], int l, int r){
    for(int i = l; i < r; ++i){
        for(int j = r-1; j >= i; --j){
            if(a[j] > a[j+1]) swap(a[j], a[j+1]);
        }
    }
}

时间复杂度最佳，最坏，平均

空间复杂度

是稳定排序

选择排序

选出最小的元素和第一个交换，再选次小的和第二个交换，依次完成排序

template <class Item>
void SelectSort(Item a[], int l, int r){
    for(int i = l; i < r; ++i){
        int minIndex = i;
        for(int j = i+1; j <= r; ++j){
            if(a[j] < a[minIndex]) minIndex = j;
        }
        swap(a[i], a[minIndex]);
    }
}

时间复杂度最佳，最坏，平均

空间复杂度

不是稳定排序

优点是交换次数少，适用于交换代价较高的场景，运行时间和记录顺序关系很小

归并排序及优化

基于分治思想

两种次序：自顶向下、自底向上

自顶向下归并排序：先划分再归并

template <class Item>
void MergeSort(Item a[], int l, int r){
    if(l >= r) return;
    int mid = l + (r - l) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid+1, r);
    Merge(a, l, mid, r);
}

template <class Item>
void Merge(Item a[], int l, int mid, int r){
    int i, j;
    Item aux[N];
    
    i = l, j = mid + 1;
    while((i <= mid && j <= r){
        if(a[i] <= a[j]) aux[k++] = a[i++];
        else aux[k++] = a[j++];
    }
    while(i <= mid) aux[k++] = a[i++];
          
    while(j <= r) aux[k++] = a[j++];
          
    for(i = l, j = 0; i <= r; ++i, ++j) a[i] = aux[j];
    
}

自底部向下归并排序：先归并再划分

template <class Item>
void MergeSortBU(Item a[], int l, int r){
    for(int sz = 1; sz <= r - l; sz += sz){
        for(int i = l; i + sz <= r; i += sz + sz){
            Merge(a, i, i + sz - 1, min(i + sz + sz - 1, r));
        }
    }
}

归并排序时间复杂度分析

时间复杂度最佳，最坏，平均

共进行了次归并，每次归并的时间复杂度为，共进行次比较

空间复杂度，需要一个大小为的辅助数组

是稳定排序

在数据只能按序访问的情况下（如链表）比快速排序快

归并排序的优化

对小规模数组使用插入排序
检测数组是否已经有序，若有序则不进行归并操作
去除原数组到辅助数组的复制操作，在递归过程中交替使用原数组和辅助数组

优化一：对小规模数组使用插入排序

在小数组下，使用插入排序比归并排序更快，可以设定一个阈值，当子数组大小小于等于时使用插入排序

enum { k = 16 };

template <class Item> 
void MergeSort(Item a[], int l, int r){
    if(r - l <= k){
        InsertSort(a, l, r);
        return;
    }
    int mid = l + (r - l) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid+1, r);
    Merge(a, l, mid, r);
}

优化二：检测数组是否已经有序

根据归并特点，若，则说明两个子数组已经有序，无需归并

template <class Item>
void MergeSort(Item a[], int l, int r){
    if(l >= r) return;
    int mid = l + (r - l) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid+1, r);
    if(a[mid] > a[mid+1]) // 仅在无序时才归并
        Merge(a, l, mid, r);
}

优化三：去除复制操作

每次 merge 时都需要将原数组复制到辅助数组中，可以通过在递归过程中交替使用原数组和辅助数组来避免这一步

template <class Item>
void MergeSort(Item a[], Item aux[], int l, int r){
    if(l >= r) return;
    int mid = l + (r - l) / 2;
    MergeSort(aux, a, l, mid);       // 注意这里交换了 a 和 aux
    MergeSort(aux, a, mid+1, r);
    if(a[mid] > a[mid+1])
        Merge(a, l, mid, r);
    else
        for(int i = l; i <= r; ++i) aux[i] = a[i]; // 直接复制回去
}

综合三个优化后的归并排序

enum { k = 16 };

template <class Item>
void MergeSort(Item a[], Item aux[], int l, int r){
    if(r - l <= k){
        InsertSort(a, l, r);
        return;
    }
    int mid = l + (r - l) / 2;
    MergeSort(aux, a, l, mid);
    MergeSort(aux, a, mid+1, r);
    if(a[mid] > a[mid+1])
        Merge(a, l, mid, r);
    else
        for(int i = l; i <= r; ++i) aux[i] = a[i];
}

template <class Item>
void MergeSort(Item a[], int n){
    Item* aux = new Item[n];
    for(int i = 0; i < n; ++i) aux[i] = a[i];
    MergeSort(a, aux, 0, n-1);
    delete[] aux;
}

std::stable_sort

这个库函数的实现使用了自底向上的归并排序，并结合了上述优化技术

如果可以申请到辅助空间，它的优化是一+二+三

若申请不到足够的额外空间，则会将序列进行递归分割，若分割后额外空间足以容纳待排序序列，则使用上一段的方法，否则使用原地归并即 inplace_merge ，这使得整个排序算法的时间复杂度增加

若完全申请不到额外空间，则时间复杂度会增加到，对应的空间复杂度降低到（如果考虑递归开销，则空间复杂度是)

这里贴出 sgi-stl 的源码

源码：点击查看代码

template <class _RandomAccessIter>
void sort(_RandomAccessIter __first, _RandomAccessIter __last);
template <class _RandomAccessIter, class _Compare>
void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp);



// stable_sort() and its auxiliary functions.
_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _RandomAccessIter, class _Compare>
void __inplace_stable_sort(_RandomAccessIter __first,
                           _RandomAccessIter __last, _Compare __comp) {
  if (__last - __first < 15) {
    __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
    return;
  }
  _RandomAccessIter __middle = __first + (__last - __first) / 2;
  __inplace_stable_sort(__first, __middle, __comp);
  __inplace_stable_sort(__middle, __last, __comp);
  __merge_without_buffer(__first, __middle, __last,
                         __middle - __first,
                         __last - __middle,
                         __comp);
}

template <class _RandomAccessIter1, class _RandomAccessIter2,
          class _Distance, class _Compare>
void __merge_sort_loop(_RandomAccessIter1 __first,
                       _RandomAccessIter1 __last,
                       _RandomAccessIter2 __result, _Distance __step_size,
                       _Compare __comp) {
  _Distance __two_step = 2 * __step_size;

  while (__last - __first >= __two_step) {
    __result = merge(__first, __first + __step_size,
                     __first + __step_size, __first + __two_step,
                     __result,
                     __comp);
    __first += __two_step;
  }
  __step_size = (min) (_Distance(__last - __first), __step_size);

  merge(__first, __first + __step_size,
        __first + __step_size, __last,
        __result,
        __comp);
}

const int __stl_chunk_size = 7;

template <class _RandomAccessIter, class _Distance, class _Compare>
void __chunk_insertion_sort(_RandomAccessIter __first,
                            _RandomAccessIter __last,
                            _Distance __chunk_size, _Compare __comp) {
  while (__last - __first >= __chunk_size) {
    __insertion_sort(__first, __first + __chunk_size,
                     _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
    __first += __chunk_size;
  }
  __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
}

template <class _RandomAccessIter, class _Pointer, class _Distance,
          class _Compare>
void __merge_sort_with_buffer(_RandomAccessIter __first,
                              _RandomAccessIter __last, _Pointer __buffer,
                              _Distance*, _Compare __comp) {
  _Distance __len = __last - __first;
  _Pointer __buffer_last = __buffer + __len;

  _Distance __step_size = __stl_chunk_size;
  __chunk_insertion_sort(__first, __last, __step_size, __comp);

  while (__step_size < __len) {
    __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
    __step_size *= 2;
    __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
    __step_size *= 2;
  }
}

template <class _BidirectionalIter1, class _BidirectionalIter2,
          class _Distance>
_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
                                      _BidirectionalIter1 __middle,
                                      _BidirectionalIter1 __last,
                                      _Distance __len1, _Distance __len2,
                                      _BidirectionalIter2 __buffer,
                                      _Distance __buffer_size) {
  if (__len1 > __len2 && __len2 <= __buffer_size) {
    _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
    copy_backward(__first, __middle, __last);
    return copy(__buffer, __buffer_end, __first);
  }
  else if (__len1 <= __buffer_size) {
    _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
    copy(__middle, __last, __first);
    return copy_backward(__buffer, __buffer_end, __last);
  }
  else
    return __rotate(__first, __middle, __last);
}

template <class _BidirectionalIter, class _Distance, class _Pointer,
          class _Compare>
void __merge_adaptive(_BidirectionalIter __first,
                      _BidirectionalIter __middle,
                      _BidirectionalIter __last,
                      _Distance __len1, _Distance __len2,
                      _Pointer __buffer, _Distance __buffer_size,
                      _Compare __comp) {
  if (__len1 <= __len2 && __len1 <= __buffer_size) {
    _Pointer __buffer_end = copy(__first, __middle, __buffer);
    merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  }
  else if (__len2 <= __buffer_size) {
    _Pointer __buffer_end = copy(__middle, __last, __buffer);
    __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
                     __comp);
  }
  else {
    _BidirectionalIter __first_cut = __first;
    _BidirectionalIter __second_cut = __middle;
    _Distance __len11 = 0;
    _Distance __len22 = 0;
    if (__len1 > __len2) {
      __len11 = __len1 / 2;
      advance(__first_cut, __len11);
      __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
      __len22 += distance(__middle, __second_cut);
    }
    else {
      __len22 = __len2 / 2;
      advance(__second_cut, __len22);
      __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
      __len11 += distance(__first, __first_cut);
    }
    _BidirectionalIter __new_middle =
      __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
                        __len22, __buffer, __buffer_size);
    __merge_adaptive(__first, __first_cut, __new_middle, __len11,
                     __len22, __buffer, __buffer_size, __comp);
    __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
                     __len2 - __len22, __buffer, __buffer_size, __comp);
  }
}

template <class _RandomAccessIter, class _Pointer, class _Distance,
          class _Compare>
void __stable_sort_adaptive(_RandomAccessIter __first,
                            _RandomAccessIter __last, _Pointer __buffer,
                            _Distance __buffer_size, _Compare __comp) {
  _Distance __len = (__last - __first + 1) / 2;
  _RandomAccessIter __middle = __first + __len;
  if (__len > __buffer_size) {
    __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
                           __comp);
    __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
                           __comp);
  }
  else {
    __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
                               __comp);
    __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
                               __comp);
  }
  __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
                   _Distance(__last - __middle), __buffer, __buffer_size,
                   __comp);
}

template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
void __stable_sort_aux(_RandomAccessIter __first,
                       _RandomAccessIter __last, _Tp*, _Distance*,
                       _Compare __comp) {
  _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  if (buf.begin() == 0)
    __inplace_stable_sort(__first, __last, __comp);
  else
    __stable_sort_adaptive(__first, __last, buf.begin(),
                           _Distance(buf.size()),
                           __comp);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>
void stable_sort(_RandomAccessIter __first,
                 _RandomAccessIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_PRIV __stable_sort_aux(__first, __last,
                               _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                               _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
                               _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
}

template <class _RandomAccessIter, class _Compare>
void stable_sort(_RandomAccessIter __first,
                 _RandomAccessIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_PRIV __stable_sort_aux(__first, __last,
                               _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                               _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
                               __comp);
}

这里出现了一个 implace_merge 函数

inplace_merge 函数用于在不使用额外空间的情况下合并两个已排序的子序列

首先要引入一个辅助函数 rotate，用于旋转数组的一部分

// 反转数组
template <typename Item>
void Reverse(Item a[], int l, int r){
    while(l < r){
        swap(a[l], a[r]);
        ++l; --r;
    }
}

// 对 a[l...r] 内元素循环右移 k 位
template <typename Item>
void Rotate(Item a[], int l, int r, int k){
    Reverse(a, l, r);
    Reverse(a, l, l + k - 1);
    Reverse(a, l + k, r);
}

template <class Item>
void InplaceMerge(Item a[], int l, int mid, int r){
    int left = l;
    int right = mid + 1;
    int k = 0; 
   
    while(left < right && right < r){
        while(left < right && a[left] <= a[right]) 
            ++left;
        k = 0;
    	while(right + k <= r && a[right + k] < a[left]) {
        	++right;
        	++k;
    	}
    	Rotate(a, left, right - 1, k);
    	left += k;
    } 
}

inplace_merge 在最坏情况下，要进行次 rotate()，这导致的最坏时间复杂度为，空间复杂度为

进一步的，在 inplace_merge 中使用分治思想，可以把复杂度降低到

template <class Item>
void InplaceMerge(Item a[], int l, int mid, int r){
    if(l >= r) return;
    if(r - l == 1){
        if(a[l] > a[r]) swap(a[l], a[r]);
        return;
    }
    int leftMid = l + (mid - l) / 2;
    int rightMid = lower_bound(a, mid + 1, r, a[leftMid]);
    int newMid = leftMid + (rightMid - mid - 1);
    Rotate(a, leftMid, rightMid - 1, rightMid - mid - 1);
    InplaceMerge(a, l, leftMid - 1, newMid - 1);
    InplaceMerge(a, newMid + 1, rightMid - 1, r);
}

使用分治思想的 inplace_merge 的归并排序时间复杂度为，空间复杂度为

不需要额外的数组空间，因此堆内存开销为，但是这是一个递归过程，栈空间开销为

因此，使用分治思想的 inplace_merge 的归并排序空间复杂度为

堆排序

堆是一种完全二叉树，可以用数组表示，它要求任意节点的值不小于（或不大于）其子节点的值，称为大根堆（或小根堆）

通过 shiftDown 操作可以将一个数组调整为堆，时间复杂度，建堆时间复杂度

template <class Item>
void Heapify(Item a[], int n){
    for(int i = (n-2)/2; i >= 0; --i){
        ShiftDown(a, n, i);
    }
}
template <class Item>
void ShiftDown(Item a[], int n, int k){
    while(2*k + 1 < n){
        int j = 2*k + 1;
        if(j + 1 < n && a[j+1] > a[j]) j++;
        if(a[k] >= a[j]) break;
        swap(a[k], a[j]);
        k = j;
    }
}

建堆操作：从最后一个非叶节点开始，依次对每个节点执行 shiftDown 操作，直到根节点

进行了 n 次 shiftDown 操作，每次操作的时间复杂度为，但实际上大部分节点的高度较低，因此建堆的时间复杂度为

由于第层节点至多为个，以它为根的子树高度为，则调用次 shiftDown 的比较次数为：

堆排序算法：借助堆的结构排序，首先将数组调整为堆，然后将堆顶元素与最后一个元素交换，再对剩余元素重新调整为堆，重复此过程直到所有元素排序完成

template <class Item>   
void HeapSort(Item a[], int n){
    Heapify(a, n);
    for(int i = n - 1; i > 0; --i){
        swap(a[0], a[i]);
        ShiftDown(a, i, 0);
    }
}

堆排序时间复杂度最佳，最坏，平均

空间复杂度

不是稳定排序

在堆排序过程中，会把堆顶元素与最后一个元素交换位置，这可能会改变相同元素的相对顺序，因此堆排序不是稳定排序算法

插入新节点后需要调整堆，将其上浮到合适位置

template <class Item>
void ShiftUp(Item a[], int k){
        while(k > 0 && a[(k-1)/2] < a[k]){
        swap(a[(k-1)/2], a[k]);
        k = (k-1)/2;
    }
}

这里贴出 sgi-stl 的源码

源码：点击查看代码

// partial_sort, partial_sort_copy, and auxiliary functions.

template <class _RandomAccessIter>
void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
                  _RandomAccessIter __last);

template <class _RandomAccessIter, class _Compare>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
                  _RandomAccessIter __last, _Compare __comp);

template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
                  _RandomAccessIter __result_first, _RandomAccessIter __result_last);

template <class _InputIter, class _RandomAccessIter, class _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
                  _RandomAccessIter __result_first,
                  _RandomAccessIter __result_last, _Compare __comp);

// partial_sort, partial_sort_copy, and auxiliary functions.
_STLP_MOVE_TO_PRIV_NAMESPACE

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)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
                 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
    }
  }
  sort_heap(__first, __middle, __comp);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
                  _RandomAccessIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                            _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
}

template <class _RandomAccessIter, class _Compare>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
                  _RandomAccessIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter, class _RandomAccessIter, class _Compare,
          class _Distance, class _Tp>
_RandomAccessIter __partial_sort_copy(_InputIter __first,
                                      _InputIter __last,
                                      _RandomAccessIter __result_first,
                                      _RandomAccessIter __result_last,
                                      _Compare __comp, _Distance*, _Tp*) {
  if (__result_first == __result_last) return __result_last;
  _RandomAccessIter __result_real_last = __result_first;
  while(__first != __last && __result_real_last != __result_last) {
    *__result_real_last = *__first;
    ++__result_real_last;
    ++__first;
  }
  make_heap(__result_first, __result_real_last, __comp);
  while (__first != __last) {
    if (__comp(*__first, *__result_first)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __adjust_heap(__result_first, _Distance(0),
                    _Distance(__result_real_last - __result_first),
                    _Tp(*__first),
                    __comp);
    }
    ++__first;
  }
  sort_heap(__result_first, __result_real_last, __comp);
  return __result_real_last;
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
                  _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
                                        _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
                                        _STLP_VALUE_TYPE(__first, _InputIter));
}

template <class _InputIter, class _RandomAccessIter, class _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
                  _RandomAccessIter __result_first,
                  _RandomAccessIter __result_last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
                                        __comp,
                                        _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
                                        _STLP_VALUE_TYPE(__first, _InputIter));
}

参数说明：

partial_sort：对区间进行部分排序，使得区间内的元素是排序后的最小元素，且有序

快速排序及优化

基本思想：分治

选择一个基准元素，将数组划分为两部分，一部分小于等于基准元素，另一部分大于等于基准元素，然后递归地对这两部分进行排序

template <class Item>
    
int Partition(Item a[], int l, int r){
    // 选择基准元素,这里选择第一个元素
    Item pivot = a[l];
    int i = l + 1;
    int j = r;
    while(true){
        while(i <= r && a[i] < pivot) ++i;
        while(j >= l + 1 && a[j] > pivot) --j;
        if(i > j) break;
        swap(a[i], a[j]);
        ++i; --j;
    }
    swap(a[l], a[j]);
    return j;
}

template <class Item>
void QuickSort(Item a[], int l, int r){
    if(l >= r) return;
    int p = Partition(a, l, r);
    QuickSort(a, l, p - 1);
    QuickSort(a, p + 1, r);
}

时间复杂度最佳，最坏，平均

空间复杂度最坏，平均，递归栈空间

不是稳定排序

快速排序的优化

栈+短序列优先
三数取中法选择基准元素
与归并一样，对小规模数组使用插入排序
三路划分以减小重复元素的影响

优化一：栈+短序列优先

template <class Item>
void QuickSortBU(Item a[], int l, int r){
    stack<pair<int, int>> stk;
    stk.push({l, r});
    while(!stk.empty()){
        auto [l, r] = stk.top();
        stk.pop();
        if(l >= r) continue;
        int p = Partition(a, l, r);
        // 短序列优先
        if(p - 1 - l < r - (p + 1)){
            stk.push({p + 1, r});
            stk.push({l, p - 1});
        } else {
            stk.push({l, p - 1});
            stk.push({p + 1, r});
        }
    }
}

优化二：三数取中法选择基准元素

template <class Item>
int Median3(Item a[], int l, int r){
    int mid = l + (r - l) / 2;
    if(a[l] > a[mid]) swap(a[l], a[mid]);
    if(a[l] > a[r]) swap(a[l], a[r]);
    if(a[mid] > a[r]) swap(a[mid], a[r]);
    swap(a[l], a[mid]); // 将中位数放到最左边
    return a[l];
}

优化三：对小规模数组使用插入排序

enum { k = 16 };

template <class Item>  
void QuickSort(Item a[], int l, int r){
    if(r - l <= k){
        InsertSort(a, l, r);
        return;
    }
    int p = Partition(a, l, r);
    QuickSort(a, l, p - 1);
    QuickSort(a, p + 1, r);
}

优化四：三路划分以减小重复元素的影响

template <class Item>
void ThreeWayPartition(Item a[], int l, int r, int &lt, int &gt){
    Item pivot = a[l];
    lt = l;      // a[l...lt-1] < pivot
    gt = r + 1;  // a[gt...r] > pivot
    int i = l + 1; // a[lt...i-1] == pivot
    while(i < gt){
        if(a[i] < pivot){
            swap(a[i], a[lt + 1]);
            ++lt; ++i;
        } else if(a[i] > pivot){
            swap(a[i], a[gt - 1]);
            --gt;
        } else {
            ++i;
        }
    }
    swap(a[l], a[lt]);
    --lt;
}

综合了优化二三四的快速排序

enum { k = 16 };

template <class Item>
void QuickSort(Item a[], int l, int r){
    if(r - l <= k){ // 优化三
        InsertSort(a, l, r);
        return;
    }
    Median3(a, l, r); // 优化二
    int lt, gt;
    ThreeWayPartition(a, l, r, lt, gt); // 优化四
    QuickSort(a, l, lt - 1);
    QuickSort(a, gt, r);
}

Introspective Sort

内省排序：结合了快速排序、堆排序的优点

通过引用堆排序，避免了快速排序在最坏情况下的时间复杂度，使得最坏时间复杂度变为

示例代码

enum { k = 16 };

template <class Item>
void IntroSort(Item a[], int l, int r, int depthLimit){
    if(r - l <= k){
        InsertSort(a, l, r);
        return;
    }
    if(depthLimit == 0){
        HeapSort(a + l, r - l + 1);
        return;
    }
    int p = Partition(a, l, r);
    IntroSort(a, l, p - 1, depthLimit - 1);
    IntroSort(a, p + 1, r, depthLimit - 1);
}

template <class Item> 
void IntroSort(Item a[], int n){
    int depthLimit = 2 * log(n);
    IntroSort(a, 0, n - 1, depthLimit);
}

这里贴出 sort() sgi-stl 的源码

源码：点击查看代码

// sort() and its auxiliary functions.
#define __stl_threshold  16

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

template <class _RandomAccessIter, class _Tp, class _Compare>
inline void __linear_insert(_RandomAccessIter __first,
                            _RandomAccessIter __last, _Tp __val, _Compare __comp) {
  //*TY 12/26/1998 - added __val as a paramter
  //  _Tp __val = *__last;        //*TY 12/26/1998 - __val supplied by caller
  if (__comp(__val, *__first)) {
    _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
    copy_backward(__first, __last, __last + 1);
    *__first = __val;
  }
  else
    __unguarded_linear_insert(__last, __val, __comp);
}

template <class _RandomAccessIter, class _Tp, class _Compare>
void __insertion_sort(_RandomAccessIter __first,
                      _RandomAccessIter __last,
                      _Tp *, _Compare __comp) {
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp);  //*TY 12/26/1998 - supply *__i as __val
}

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<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
}

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

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, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
    __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
  }
  else
    __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
}

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

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>
void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  if (__first != __last) {
    _STLP_PRIV __introsort_loop(__first, __last,
                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                                _STLP_PRIV __lg(__last - __first) * 2,
                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
    _STLP_PRIV __final_insertion_sort(__first, __last,
                                      _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  }
}

template <class _RandomAccessIter, class _Compare>
void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  if (__first != __last) {
    _STLP_PRIV __introsort_loop(__first, __last,
                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                                _STLP_PRIV __lg(__last - __first) * 2, __comp);
    _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
  }
}

计数排序

计数排序适用于数据范围较小的整数排序，假设待排序数组为，包含个元素，元素取值范围为，计数排序的基本思想是统计每个元素出现的次数，然后根据这些计数信息将元素放回到正确的位置

template <class Item>
void CountingSort(Item a[], int n){
    Item max = a[0];
    Item min = a[0];
        for(int i = 1; i < n; ++i){
        if(a[i] > max) max = a[i];
        if(a[i] < min) min = a[i];
    }
    int range = max - min + 1;
    vector<int> count(range, 0);
    for(int i = 0; i < n; ++i){
        count[a[i] - min]++;
    }
    for(int i = 1; i < range; ++i){
        count[i] += count[i - 1];
    }
    vector<Item> output(n);
    for(int i = n - 1; i >= 0; --i){
        output[count[a[i] - min] - 1] = a[i];
        count[a[i] - min]--;
    }
    for(int i = 0; i < n; ++i){
        a[i] = output[i];
    }
}

时间复杂度为，其中是元素取值范围的大小

空间复杂度为

是稳定排序

这位基数排序的正确性提供了保证

基数排序

基将整数按位数进行排序，从最低有效位到最高有效位，使用稳定的排序算法（如计数排序）对每一位进行排序

MSD 基数排序从最高有效位开始排序

template <class Item>
void RadixSort(Item a[], int n){
    const int base = 10; // 十进制
    int max = a[0];
    for(int i = 1; i < n; ++i){
        if(a[i] > max) max = a[i];
    }
    for(int exp = 1; max / exp > 0; exp *= base){
        CountingSortByDigit(a, n, exp, base);
    }
}

void CountingSortByDigit(Item a[], int n, int exp, int base){
    vector<int> count(base, 0);
    vector<Item> output(n);
    for(int i = 0; i < n; ++i){
        int digit = (a[i] / exp) % base;
        count[digit]++;
    }
    for(int i = 1; i < base; ++i){
        count[i] += count[i - 1];
    }
    for(int i = n - 1; i >= 0; --i){
        int digit = (a[i] / exp) % base;
        output[count[digit] - 1] = a[i];
        count[digit]--;
    }
    for(int i = 0; i < n; ++i){
        a[i] = output[i];
    }
}

LSD 基数排序从最低有效位开始排序

template <class Item>
void LSDRadixSort(Item a[], int n){
        const int base = 10; // 十进制
    int max = a[0];
    for(int i = 1; i < n; ++i){
        if(a[i] > max) max = a[i];
    }
    vector<int> digits;
    while(max > 0){
        digits.push_back(max % base);
        max /= base;
    }
    for(int i = 0; i < digits.size(); ++i){
        CountingSortByDigit(a, n, pow(base, i), base);
    }
}

template <class Item>
void CountingSortByDigit(Item a[], int n, int exp, int base){
    vector<int> count(base, 0);
    vector<Item> output(n);
    for(int i = 0; i < n; ++i){
        int digit = (a[i] / exp) % base;
        count[digit]++;
    }
    for(int i = 1; i < base; ++i){
        count[i] += count[i - 1];
    }
    for(int i = n - 1; i >= 0; --i){
        int digit = (a[i] / exp) % base;
        output[count[digit] - 1] = a[i];
        count[digit]--;
    }
    for(int i = 0; i < n; ++i){
        a[i] = output[i];
    }
}

LSD 基数排序时间复杂度为，其中是数字的位数，是基数

空间复杂度为

是稳定排序

MSD 与 LSD 的比较

LSD 基数排序从最低有效位开始排序，适用于位数较少且分布均匀的数据

MSD 基数排序从最高有效位开始排序，适用于位数较多且分布不均匀的数据

LSD 必须要比较完所有位，而 MSD 可以在某些情况下提前终止排序

但当需要比较完所有位时，MSD 相比 LSD 会有更高的递归开销

MSD 要对每一个子序列重新计算基数，而 LSD 只需每轮计算一次，这使得 LSD 在处理大规模数据时通常更高效

桶排序

假设数据均匀分布

桶排序将区间划分为个大小相同的子区间，即桶，然后通过一个单调映射函数将个元素插入到个桶中，每个桶中做插入排序，最终把每一个桶中取出来即排好序

template <class Item>
void BucketSort(Item a[], int n, int k){
    vector<vector<Item>> buckets(k);
    for(int i = 0; i < n; ++i){
        int index = a[i] * k; // 映射函数
        if(index >= k) index = k - 1; // 边界处理
        buckets[index].push_back(a[i]);
    }
    for(int i = 0; i < k; ++i){
        InsertSort(buckets[i].data(), buckets[i].size());
    }
    int idx = 0;
    for(int i = 0; i < k; ++i){
        for(int j = 0; j < buckets[i].size(); ++j){
            a[idx++] = buckets[i][j];
        }
    }
}

假设映射函数均匀分配，此时桶排序的时间复杂度为空间复杂度，当时，时间复杂度最优为

这是一个稳定的排序算法

桶排序容易在桶层面做并行化

并行化代码实现

#include <thread>

ThreadPool pool(16); // 假设有一个线程池
template <class Item>
void ParallelBucketSort(Item a[], int n, int k){
    pool.init();
    vector<vector<Item>> buckets(k);
    for(int i = 0; i < n; ++i){
        int index = a[i] * k; // 映射函数
        if(index >= k) index = k - 1; // 边界处理
        buckets[index].push_back(a[i]);
    }
    vector<future<void>> futures;
    for(int i = 0; i < k; ++i){
        futures.push_back(pool.enqueue([&, i]{
            InsertSort(buckets[i].data(), buckets[i].size());
        }));
    }
    for(auto &fut : futures){
        fut.get();
    }
    int idx = 0;
    for(int i = 0; i < k; ++i){
        for(int j = 0; j < buckets[i].size(); ++j){
            a[idx++] = buckets[i][j];
        }
    }
    pool.shutdown();
}

排序的比较

排序方法	最坏时间	稳定性
插入排序		稳定
冒泡排序		稳定
选择排序		不稳定
归并排序		稳定
快速排序	/	不稳定
堆排序		不稳定
计数排序		稳定
基数排序 LSD		稳定
桶排序		稳定

其中为待排序元素个数，为计数排序中元素取值范围的大小，为基数排序中数字的位数，为基数排序中基数的大小

Top-K 问题

Top-K 问题是指在一个数据集中找到前 K 个最大的元素或最小的元素

大致分为两类：

静态 Top-K：数据集在查询过程中保持不变

动态 Top-K：数据集在查询过程中可能会发生变化，需要动态维护 Top-K 元素

静态 Top-K

完全排序

将输入内容进行完全排序，然后取前 K 个元素

使用小根堆

不对输入内容进行排序

维护一个大小为的小根堆，遍历数据集中的每个元素，与堆顶元素进行比较，如果当前元素大于堆顶元素，则将堆顶元素替换为当前元素，并进行堆调整

时间复杂度：

空间复杂度：

template <class Item>
vector<Item> TopK(Item a[], int n, int k){
    priority_queue<Item, vector<Item>, greater<Item>> minHeap;
    for(int i = 0; i < n; ++i){
        if(minHeap.size() < k){
            minHeap.push(a[i]);
        } else if(a[i] > minHeap.top()){
            minHeap.pop();
            minHeap.push(a[i]);
        }
    }
    vector<Item> result;
    while(!minHeap.empty()){
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    reverse(result.begin(), result.end()); // 从大到小排序
    return result;
}

随机选择算法

先找到第 K 大的元素，然后遍历数据集，收集所有大于等于该元素的元素

这借鉴了快速排序的思想，将数组进行划分，区别是快排会递归地对两部分进行排序，而随机选择算法只对包含第 K 大元素的部分进行处理

时间复杂度：平均，最坏

空间复杂度：

int mtrand(int l, int r){
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937 rng = mt19937(seed);
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

template <class Item>
int RandomizedPartition(Item a[], int l, int r){
    int i = l + mtrand(0, r - l);
    
    swap(a[l], a[i]);
    
    return Partition(a, l, r);
}

template <class Item>
Item RandomizedSelect(Item a[], int l, int r, int k){
    if(l == r) return a[l];
    int p = RandomizedPartition(a, l, r);
    int q = p - l + 1; // 排名
    if(k == q) return a[p];
    else if(k < q) return RandomizedSelect(a, l, p - 1, k);
    else return RandomizedSelect(a, p + 1, r, k - q);
}

template <class Item>
vector<Item> TopK(Item a[], int n, int k){
    Item kthLargest = RandomizedSelect(a, 0, n - 1, k);
    vector<Item> result;
    for(int i = 0; i < n; ++i){
        if(a[i] >= kthLargest){
            result.push_back(a[i]);
        }
    }
    return result;
}

选择算法

这是基于随机选择算法的改进

将输入的个元素划分为组，每组包含 5 个元素（最后一组可能少于 5 个）
对每组进行插入排序，确定中位数
对所有中位数递归地调用选择算法，找到中位数的中位数，作为划分的基准元素
以该基准元素对数组进行划分，然后根据划分结果递归地选择第 K 大元素所在的部分

最坏情况下时间复杂度为

空间复杂度为

template <class Item>
int partition(Item a[], int l, int r, Item x){
    for(int i = l; i <= r; ++i){
        if(a[i] == x){
            swap(a[i], a[l]);
            break;
        }
    }
    int i = l-1, j = r,;
    Item t = a[r];
    while(1){
        while(a[++i] < t);
        while(a[--j] > t);
        if(i >= j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

template <class Item>
Item findMedian(Item a[], int l, int r){
    int n = r - l + 1;
    sort(a + l, a + r + 1); // 插入排序也可以
    return a[l + n / 2];
}

template <class Item>
Item Select(Item a[], int l, int r, int k){
    if(l == r) return a[l];
    int n = r - l + 1;
    int numMedians = (n + 4) / 5;
    vector<Item> medians(numMedians);
    for(int i = 0; i < numMedians; ++i){
        int subL = l + i * 5;
        int subR = min(subL + 4, r);
        medians[i] = findMedian(a, subL, subR);
    }
    Item pivot = Select(medians.data(), 0, numMedians - 1, numMedians / 2);
    int p = partition(a, l, r, pivot);
    int q = p - l + 1;
    if(k == q) return a[p];
    else if(k < q) return Select(a, l, p - 1, k);
    else return Select(a, p + 1, r, k - q);
}

动态 Top-K

使用对顶堆

对顶堆是一种特殊的堆结构，其中包含两个堆：一个大根堆和一个小根堆

小根堆用于存储当前的 Top-K 元素，而大根堆用于存储剩余的元素

template <class Item>
class DynamicTopK{
    private:
    priority_queue<Item, vector<Item>, greater<Item>> minHeap; // 小根堆
    priority_queue<Item> maxHeap; // 大根堆
    int k;
    
    public:
    DynamicTopK(int k): k(k) {}

    void add(Item value){
        if(minHeap.size() < k){
            minHeap.push(value);
        } else if(value > minHeap.top()){
            maxHeap.push(minHeap.top());
            minHeap.pop();
            minHeap.push(value);
        } else {
            maxHeap.push(value);
        }
    }

    vector<Item> getTopK(){
        vector<Item> result;
        while(!minHeap.empty()){
            result.push_back(minHeap.top());
            minHeap.pop();
        }
        // 重新构建小根堆
        for(const auto &val : result){
            minHeap.push(val);
        }
        return result;
    }
};

时间复杂度：添加元素，获取 Top-K 元素

空间复杂度：，其中是数据集中元素的总数

还有使用动态平衡树（如 AVL 树或红黑树）、线段树来维护 Top-K 元素的方案，等到树章节再补充

逆序对

逆序对是指在一个数组中，存在一对元素，使得且

同理存在正序对，使得且

它们的求法可以使用归并排序的思想，在归并的过程中统计逆序对的数量

template <class Item>
int mergeSortAndCount(Item a[], int l, int r){
    if(l >= r) return 0;
    int mid = l + (r - l) / 2;
    int count = 0;
    count += mergeSortAndCount(a, l, mid);
    count += mergeSortAndCount(a, mid + 1, r);
    count += mergeAndCount(a, l, mid, r);
    return count;
}

template <class Item>
int mergeAndCount(Item a[], int l, int mid, int r){
    int i = l, j = mid + 1;
    int k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]){
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            count += (mid - i + 1); // 统计逆序对
            // count += (j - (mid + 1)); // 统计正序对
        }
    }
    while(i <= mid){
        temp[k++] = a[i++];
    }
    while(j <= r){
        temp[k++] = a[j++];
    }
    for(int p = 0; p < k; ++p){
        a[l + p] = temp[p];
    }
    return count;
}

时间复杂度：

空间复杂度：

其实均与归并排序相同

TimSort

TimSort 是一种混合排序算法，结合了归并排序和插入排序的优点，最初实现于 Python 的排序函数中，后来被广泛应用于 Java 和其他编程语言的标准库中

(´-ω-｀)

基于比较的排序

插入排序

冒泡排序

选择排序

归并排序及优化

归并排序的优化

堆排序

快速排序及优化

快速排序的优化

计数排序

基数排序

桶排序

排序的比较

Top-K 问题

静态 Top-K

完全排序

使用小根堆

随机选择算法

选择算法

动态 Top-K

逆序对

TimSort