排序

LC912 排序数组
LC148 排序链表
LC147 对链表进行插入排序
LC88 合并两个有序数组[反向merge]
⚠️LC75 颜色分类[计数排序 或 特制partition]

洗牌算法

冒泡排序

如果不交换相邻的相等元素，则是稳定的排序算法。平方复杂度。
优化：

- 如果内层循环没有发生交换，那么直接退出。

code

template<typename It>
void bubbleSort(It first, It last)
{
    while(true)
    {
        auto swapped = false;
        for(auto i = first, j = first + 1; 
            i != last && j != last;
            ++i,++j)
            {
                if(*j < *i)
                {
                    iter_swap(i,j);
                    swapped = true;
                }
            }
        if(!swapped) break;
    }
}

选择排序

用链表实现是稳定的。如果在数组上用交换的方式实现则不稳定。平方复杂度。改进版为堆排序。堆的存在将min_element(first, last)的时间复杂度变为对数级。

code

template<typename It>
void selectionSort(It first, It last)
{
    while(first < last)
    {
         auto ptr = min_element(first, last);
         iter_swap(first, ptr);
         ++first;
    }
}

插入排序

不稳定。平方复杂度。

插入排序作为STL中较小区间的默认排序算法，实现比较具有技巧性：

• 维护循环不变式：[first, i)区间是有序的。
• 用一个外层循环，不断的调用内层函数linear_insert
• linear_insert首先将i处的值复制下来。之后检查first处的值是不是比i的值大，如果是，就直接调用copy_backward将整个区间向后挪动一格，再把i放到腾出的first处。
• 如果不是，就开始从next = i - 1处开始检查逆序对。这里并没有采用不断交换逆序对的手段。而是仍然类似之前，先记录下来i的值value，遇到*next比value小的情况，就把*next往后窜，直到*next不小于value，这时再将value放置到此时next的后一位置last处。

code

template<typename It>
void insertionSort(It first, It last)
{
    for(auto i = first + 1; i < last; ++i)
    {
        linear_insert(first, i);
    }
}

template<typename It>
void linear_insert(It first, It last)
{
    // copy the value for the last element
    auto value = *last;
    // if the value is smaller than all the elements
    // then we do not need to perform swap, just shift
    // the range right by one slot
    if(value < *first)
    {
        copy_backward(first, last, last + 1);
        *first = value;
    }
    else
    {
        linear_insert(last, value);
    }
}

template<typename It, typename T>
void linear_insert(It last, T value)
{
    auto next = last;
    --next;
    // we do not need to worry about whether 
    // next will move out of range
    // because in the function above, 
    // the situation value < *first 
    // is already treated with care.
    while(value < *next)
    {
        //shift the value of next right by one slot
        *last = *next;
        last = next;
        --next;
    }

    // the slot where the value should be put in
    *last = value;

}

---

对链表进行插入排序

LC147 对链表进行插入排序

希尔排序

不稳定。低于平方复杂度。实现简单，效率高。在LC912 排序数组这个题目的测试上，可以得到60ms左右的成绩。而采用STL库的内省式排序，则为30ms左右。

根据插入排序的以下两个性质进行改进：

- 插入排序对几乎已经排好的数据进行排序时，可以达到近乎线性的效率
- 插入排序每次只能将元素向前移动一个位置，较为低效

因此希尔排序通过设置步长，将整个区间分为几块，分别排序，再不断缩小步长。这样在开始时，元素可以朝目标移动一大段距离。最后步长会变成1，进行一次普通的插入排序。但是此时数据已经几乎是有序的了，插入排序就能非常迅速的完成任务。

几种常见的希尔排序增量：

- Hibbard增量：1, 3, 7, 15 ... 2^k - 1 保证相邻增量之间没有公因数，复杂度可证：$\Theta(N^{\frac{3}{2})$
- Knuth增量：1, 4, 13, 40, ..., (3^k - 1) /2 递推式为 $a_{n+1} = 3 * a_{n} + 1$, $a_1 = 1$，复杂度可证：$\Theta(N^{\frac{3}{2})$
- Sedgewick增量

采用Knuth增量的ShellSort实现

template<typename It>
void shellSort(It first, It last)
{
    auto len = last - first;
    size_t step = 1;
    while(step < len / 3)
    {
        step = step * 3 + 1;
    }
    shellSort(first, last, step);
}

template<typename It>
void shellSort(It first, It last, size_t step)
{
    while(step)
    {
        for (auto i = first + step; i < last; ++i)
        {
            for (auto j = i;
            	// this is a very smart way to avoid j move out of range
                j >= first + step && *j < *(j - step); 
                j-= step)
                iter_swap(j, j - step);
        }
        step /= 3;
    }

}

堆排序

堆排序的关键子算法为下沉。即GNU STL中的__adjust_heapstl_heap.h Reference中的实现为了减少比较次数，没有在每次循环中判断下沉节点和较大子节点之间的关系，而是采用一沉到底再上浮的方法。

另一个需要注意的点是STL中的堆序号是从0开始的，因此：

• 节点i的左孩子为2 i + 1，右孩子为2 i
• 设区间长度为len，则index为 (len - 2) / 2开始的节点为叶子节点。

下沉的实现（即__adjust_heap）

template<typename It, typename Comp = less<typename iterator_traits<It>::value_type> >
void adjust_heap(It first, 
                typename iterator_traits<It>::difference_type hole_idx, 
                It last, 
                const Comp& comp = less<typename iterator_traits<It>::value_type>{})
{
    // get the value of the hole
    auto hole = first + hole_idx;
    auto val = *hole;
    // get the secondChild It
    auto secondChild = hole + (hole - first) + 2;

    while(secondChild < last)
    {
        // compare second child with first child
        if(comp(*secondChild, *(secondChild - 1))) --secondChild;
        // check if val is greater than both children
        if(comp(*secondChild, val)) break;
        *hole = *secondChild;
        hole = secondChild;
        secondChild = hole + (hole - first) + 2;
    }

    // if it escape the loop because it does not 
    // have a secondChild, we have to check if it
    // still needs to sink
    if(secondChild == last && comp(val, *(--secondChild)))
    {
        *hole = *secondChild;
        hole =secondChild;
    }

    *hole = val;
}

在堆排序之前需要先进行建堆，即从最后一个叶子节点开始，从后往前对堆中元素进行下沉操作

template<typename It, typename Comp = less<typename iterator_traits<It>::value_type> >
void make_heap(It first, It last, const Comp& comp = less<typename iterator_traits<It>::value_type>{})
{
    for(auto hole_idx = (last - first - 2) / 2 + 1; hole_idx--;)
    {
        adjust_heap(first, hole_idx, last, comp);
    }
}

在堆排序中最经常被调用的算法为pop_heap，即将堆首元素弹出堆，置于堆尾。在一个已经建好的堆上不断调用pop_heap直到区间长度为1，就可以实现堆排序了。

pop_heap的实现

template<typename It, typename Comp = less<typename iterator_traits<It>::value_type> >
void pop_heap(It first, It last, const Comp& comp = less<typename iterator_traits<It>::value_type>{})
{
    iter_swap(first, last - 1);
    adjust_heap(first, 0, last - 1);
}

最后是将以上组件组合在一起的的heap_sort实现：

heap_sort的实现

template<typename It, typename Comp = less<typename iterator_traits<It>::value_type> >
void heap_sort(It first, It last, const Comp& comp = less<typename iterator_traits<It>::value_type>{})
{
    make_heap_williams(first, last, comp);
    while(last - first > 1)
    {
        pop_heap(first, last--, comp);
    }

}

归并排序

需要使用额外空间的稳定排序算法。复杂度为$\Theta(N\mathrm{log}(N))$

在数组上进行merge，往往都需要额外的空间来储存结果。然而在链表上可以实现常数空间复杂度的归并排序。

STL中的merge

STL中<algorithm>提供的函数merge，可以用于两个数组的归并。介绍中是这样描述的：

• 归并二个已排序范围 [first1, last1) 和 [first2, last2) 到始于 d_first 的一个已排序范围中。
• 稳定性对于元范围中的等价元素，来自第一范围的元素（保持其原顺序）先于来自第二范围的元素（保持其原顺序）。
• 需要额外空间若目标范围与输入范围之一重叠，则行为未定义（输入范围可相互重叠）。

STL中的merge实现并未有太特别之处。需要注意的地方有三：

• 一是为了保证稳定性的小细节：即保证当序列1和序列2中的元素等价时，序列1中的元素在前。所以在判断的时候，先判断*first2 < *first1，并把相等的部分放入了else分支中。
• 二是最后调用copy来实现剩余区间的拷贝。
• 三是区间一，区间二和输出区间各用一种迭代器，可以归并不同类型的迭代器的内容。

code

template<typename It1, typename It2, typename It3>
It3 merge_(It1 first1, It1 last1, It2 first2, It2 last2, It3 result)
{
    while(first1 < last1 && first2 < last2)
    {
        if(*first2 < *first1)
        {
            *result = *first2;
            ++first2;
        }
        // be very careful about the order of comparing first2 and first1
        // we must make sure when first1 and first2 are equivalent,
        // first1 will be added into the result first.
        else
        {
            *result = *first1;
            ++first1;
        }

        ++result;
    }        

    return copy(first1, last1, copy(first2, last2, result));
}

STL中的归并排序stable_sort

STL中的归并排序stable_sort底层采用适应性分配缓冲区的__stable_sort_adaptive和__merge_adaptive，实现比较复杂。这里我们实现一个简单的归并排序。

如果想要用归并，就必须得有缓冲区，GNU STL中使用的缓冲区位于<ext/memory>中GNU STL API，构造函数定义如下。介绍为

Requests storage large enough to hold a copy of [first,last).

__gnu_cxx::temporary_buffer<It, T>::temporary_buffer(It first, It last)

像一般容器一样，他也有size(),begin(),end()等方法，还有一个requested_size()。

我们在实现时，可以申请一个[first, last)一样长的缓冲区，然后将[first, mid)的内容拷贝进缓冲区，然后再把缓冲区和[mid, last)调用merge，归并回[first, last)。

简易stable_sort实现

#include<ext/memory>
template<typename It>
void mergesort(It first, It last)
{
    auto n = (last - first);
    // base case
    if(n == 0 || n == 1) return;
    
    // merge sort routine
    auto mid = first + n / 2;
    mergesort(first, mid);
    mergesort(mid, last);
    // apply for a buffer
    auto buf = __gnu_cxx::temporary_buffer<It, typename iterator_traits<It>::value_type>(first, last);
    auto buf_end = copy(first, mid, buf.begin());
    merge(buf.begin(), buf_end, mid, last, first);
}

合并两个有序数组

LC88 合并两个有序数组

这个题目给出两个数组，并保证其中较长的数组有足够的空间容纳结果。我们可以实现不使用额外空间的merge：

• 初始化三个指针。p1指向长数组使用部分的末尾。p2指向短数组的末尾（短数组没有剩余空间）。p指向长数组的末尾。
• 从后向前来做归并。比较p1和p2的值：
  • p1 < p2, 将p2放到p的位置，—p, —p2
  • !(p1 < p2)， 将p1放到p的位置，—p, —p1
• 如果p1的指针先挪出范围了，那就把p2到头的部分都赋值进p1
• 如果p2的指针先挪出范围了，那就不用动了。

我们可以利用这样的思路直接调用STL库函数里的merge。即传入反向迭代器，使用greater<int>实现从尾到头merge。

code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        // how many slots are not in used in nums1?
        auto freeSlotNum = nums1.size() - m;
        // initialize all three ptrs
        auto it1 = nums1.rbegin() + freeSlotNum;
        auto it2 = nums2.rbegin();
        auto it  = nums1.rbegin();
        // merge from the end to begin.
        std::merge(it1, nums1.rend(), it2, nums2.rend(), it, greater<int>{});
    }
};

甚至可以写成一行

一行code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        std::merge(nums1.rbegin() + nums1.size() - m, nums1.rend(), nums2.rbegin(), nums2.rend(), nums1.rbegin(), greater<int>{});
    }
};

或者由我们来自己实现merge

自己实现merge

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        merge_(nums1.rbegin() + nums1.size() - m, nums1.rend(), nums2.rbegin(), nums2.rend(), nums1.rbegin(), greater<int>{});
    }

    template<typename It, typename Comp>
    It merge_(It first1, It last1, It first2, It last2, It result, Comp cmp)
    {
        while(first1 < last1 && first2 < last2)
        {
            if(cmp(*first2, *first1))
            {
                *result = *first2;
                ++first2;
            }else
            {
                *result = *first1;
                ++first1;
            }
            ++result;
        }

        return copy(first1, last1, copy(first2, last2, result));
    }
};

归并链表

LC148 排序链表

多路归并

就地归并

快速排序

SGI STL中的quicksort实现不同于一般我们上课或在教材当中学到的quicksort形式。他使用一个循环保证[first, last)区间非空。然后在循环当中对枢纽右侧区间递归调用，将枢纽赋给last后重新循环。形式更加简洁。

code

template<typename It>
void quicksort(It first, It last)
{
    while(first + 1 < last)
    {
        auto cut = unguarded_partition(first, last, 
        __gnu_cxx::__median(*first, *(first + (last - first)/2), *(last - 1)));
        quicksort(cut, last);
        last = cut;
    }
}

用于快速排序的unguarded_parition

代码同std::__unguarded_partition。这个unguarded_partition不像partition一样有很多流程控制保证first和last不会交错，因此效率更高。尚不知道partition那样做的原因。

code

template<typename It, typename T>
It unguarded_partition(It first, It last, T pivot)
{
    while(true)
    {
        while(*first < pivot) ++first;
        --last;
        while(pivot < *last) --last;
        if(!(first < last)) return first;
        iter_swap(first, last);
        ++first;
    }
}

用于划分的partition

code

template<typename It, typename Pred>
It partition(It first, It last, Pred pred)
{
    while(true)
    {
        
        while(true)
        {
            
            if(first == last) return first;
            else if(pred(*first)) ++first;
            else break;
           
        }
        --last;
        while(true)
        {
            if(first == last) return first;
            else if(!pred(*last)) --last;
            else break;
        }
        iter_swap(first, last);
        ++first;
    }
}

median-of-three

这个算三个数的中位数的程序可以在SGI STL的头文件ext/algorithm里找到，名字叫__gnu_cxx::__median。

防止栈溢出

内省排序

基数排序

计数排序

LC75 颜色分类

思路一：记录每一种颜色的个数，然后再按顺序填回去即可。

code

class Solution {
private:
public:
    void sortColors(vector<int>& nums) {
        auto cnt = array<int, 3>{};
        for(auto x : nums)
        {
            ++cnt[x];
        }
        auto it = nums.begin();
        int color = 0;
        for(auto x : cnt)
        {
            while(x)
            {
                *it = color;
                ++it;
                --x;
            }
            ++color;
        }
    }
};

思路二：因为只有三种元素，所以可以采用partition的思路一次遍历。注意不能简单的带入hoare partition等算法。因为那是针对将区间划分成两个区域采用的。我们要将区间划分成三个区域。

使用三个指针first, cur, last

• 初始化first = begin, cur = begin, last = —end
• 如果*cur == 0那么我们就把cur和first交换，然后++cur,++first（还是不理解为什么要++cur）
• 如果*cur == 1，++cur
• 如果*cur == 2，交换cur和last，然后—last，但不++cur(因为从右边换过来的数不一定是什么？)

code

class Solution {
private:
public:
    void sortColors(vector<int>& nums) {
        auto cur = nums.begin();
        auto first = nums.begin();
        auto last = --nums.end();

        // invariance 
        // [begin, first) == 0
        // [last, end) == 2
        // cur < last

        while(cur <= last)
        {
            // swap it into [begin, first) range
            if(*cur == 0)
            {
                iter_swap(cur, first); 
                ++first;
                ++cur;
            }

            else if(*cur == 2)
            {
                iter_swap(cur, last);
                --last;
            }

            else // *cur == 1
            {
                ++cur;
            }
        }

    }
};

桶排序