对某个区间操作(sort,stable_sort,parital_sort,parital_sort_copy,nth_element,is_sorted)

2024-03-30 23:13:48

对某个区间操作(sort,stable_sort,parital_sort,parital_sort_copy,nth_element,is_sorted)

sort

　　参数为随机迭代器，只有vector和deque使用sort算法；在介绍SGI的快排之前先介绍以下几种排序。

insertion sort

　　直接插入排序。

template<class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first,RandomAccessIterator last)//外循环遍历整个序列，每次迭代决定一个子区间
{
    if(first==last) return;
    for(RandomAccessIterator i=first+1;i!=last;++i)
        __linear_insert(first,i,value_type(first));
        //以上[first,i)形成一个子区间
}

template <class RandomAccessIterator,class T>
inline void__linear_insert(RandomAccessIterator first,Random AccessIterator last,T*)//内层循环遍历子区间，将子区间内的逆转对倒转过来
{
    T value=*last;//记录尾元素，用于判断一次要插入的元素和头元素的大小
    if(value<*first){
        copy_backward(first,last,last+1);//将整个区间右移一个位置
        *first=value;
    }
    else//尾不小于头
        __unguarded_linear_insert(last,value);
}

template<class RandomAccessIterator,class T>
void __unguarded_linear_insert(RandomAccessIterator first,Random AccessIterator last,T value)
{//因为在直接插入排序中会有两次判断:判断其是否为逆转对&判断循环是否过边界——省下一个判断操作
    RandomAccessIterator next=last;
    --next;
    //insertion sort的内循环
    //注意，一旦不再出现逆转对，循环就可以结束了
    while(value<*next){//逆转对存在
        *last==*next;
        last=nex;
        --next;
    }
    *last=value;
}

Quick Sort

如果S的元素个数为0或1，结束
取S中的任意一个元素，当做枢轴pivot（v）
将S分割为L，R两段，使L内每一个元素都小于或等于V，R内的每一个元素都大于等于v
对L，R执行递归QuickSort

　　快排的灵魂是在于将大区间分割为小区间，分段排序，每个小区间排序完成后，串起来的大区间也就完成了排序。但是在选取中值进行划分时可能会产生空区间。

　　median-of-three（三点之中值）：为了避免“元素当初输入时不够随机”所带来的恶化效应，最理想的最稳当的方法就是取整个序列的头、尾、*三个位置的元素，以其中值作为枢轴，这种做法成为median-of-three partitioning，或成为median-of-QuickSort，为了能够快速取出*位置的元素，显然迭代器必须能够随机读取亦即是个RandomAccessIterators。

partition（分割）

　　令first向尾移动，last向头移动。当*first大于或等于pivot时停下来，当*last小于或等于pivot时也停下来，然后检验两个迭代器是否交错。未交错则元素互相，然后各自调整一个位置，再继续相同行为。若交错，则以此时first为轴将序列分为左右两半，左边值都小于或等于pivot，右边都大于等于pivot。

template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,RandomAccessIterator last,T pivot)
{
    while(true)
    {
        while (*first < pivot) 
            ++first;// first 找到 >= pivot的元素就停
        --last;
        while (pivot < *last)
            --last;// last 找到 <=pivot

        if (!(first < last)) 
            return first;// 交错，结束循环   
        
        iter_swap(first,last);// 大小值交换
        ++first;// 调整
    }
}

IntroSort

　　不当的枢轴选择，导致不当的分割，导致Quick Sort恶化为O(N^2)。Introspective Sorting。其行为在大部分情况下几乎与 median-of-3 Quick Sort完全相同。但是当分割行为(partitioning)有恶化为二次行为倾向时，能自我侦测，转而改用Heap Sort，使效率维持在O(NlogN)。SGI中sort使用的就是IntroSort。

　　先判断数据量是否大于阈值，若不大于直接调用直接插入排序；若大于再检查分割层次，若超过分割层次就调用partion_sort（堆排序实现），否则就以三点中值法确定中枢位置，利用__unguarded_partition找出分割点，对左右区间进行IntroSort——SGI sort内部过程。

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first,RandomAccessIterator last)
{
    if (first != last)
    {
        __introsort_loop(first, last, value_type(first), __lg(last-first)*2);
        __final_insertion_sort(first,last);//__introsort_loop会产生许多长度小于16的未排序的区间，用此函数进行排序；这些子序列之间是递增的
    }
}
// __lg()用来控制分割恶化的情况
// 找出2^k <= n 的最大值,例：n=7得k=2; n=20得k=4
template<class Size>
inline Size __lg(Size n)
{
    Size k;
    for (k = 0; n > 1; n >>= 1)
        ++k;
    return k;
}
// 当元素个数为40时,__introsort_loop的最后一个参数
// 即__lg(last-first)*2是5*2,意思是最多允许分割10层。
const int  __stl_threshold = 16;
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,RandomAccessIterator last, T*, Size depth_limit)
{
    while (last - first > __stl_threshold){        // > 16
    if (depth_limit == 0){                    // 至此，分割恶化
        partial_sort(first, last, last);    // 改用 heapsort
        return;
    }
    --depth_limit;
    // 以下是 median-of-3 partition，选择一个够好的枢轴并决定分割点
    // 分割点将落在迭代器cut身上
    RandomAccessIterator cut = __unguarded_partition
    (first, last, T(__median(*first,*(first + (last - first)/2),*(last - 1))));

    // 对右半段递归进行sort
    __introsort_loop(cut,last,value_type(first), depth_limit);

    last = cut;
    // 现在回到while循环中，准备对左半段递归进行sort
    // 这种写法可读性较差，效率也并没有比较好
    }
}

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last)
{
    if (last - first > __stl_threshold)
    {
        // > 16
        // 一、[first,first+16)进行插入排序
        // 二、调用__unguarded_insertion_sort，实质是直接进入插入排序内循环
        __insertion_sort(first,first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    }
    else
        __insertion_sort(first, last);
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,RandomAccessIterator last)
{
    __unguarded_insertion_sort_aux(first, last, value_type(first));
}

template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first,RandomAccessIterator last,T*)
{
    for (RandomAccessIterator i = first; i != last; ++i)
        __unguarded_linear_insert(i, T(*i));
}

stable_sort

//版本一 
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first,RandomAccessIterator last);
//版本二 
template <class RandomAccessIterator,class StrictWeakOrdering)
void stable_sort(RandomAccessIterator first,RandomAccessIterator last,StrictWeakOrdering cmp);

stable_sort会保证排序后元素的相对位置不变（把某序列按姓排序，如果姓相同而名不同，则视为等价，此时相对位置不改变，用stable_sort函数），使用merge sort算法
sort不会保证排序后的相对位置相同，因此sort比stable_sort快，使用intersort算法
每个函数都有两个版本，第一个版本重载operator < ，第二个版本调用自己定义的function object

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class F
{
    public:
        bool operator()(int i,int j)
        {
            return (i%10)>=(j%10);    
        }    
};
int main()
{
    vector<int> v{2,1,-1,5,6,3};
    sort(v.begin(),v.end(),F());
    for_each(v.begin(),v.end(),[](int i)
    {
        cout<<i<<" ";
    });
    cout<<endl;
    return 0;    
}

parital_sort

使[first,middle)中个最小元素以递增方式排序（此区间为大根堆），[middle,last)中无序，但[middle,last)中的每个元素都大于[first,middle)中的元素
用partial_sort而不用sort的理由是partial_sort挑选出来n个元素来排序比对整个区间来排序要快
middle==first，无意义，先将0个元素放入[first,first)中，然后将剩余元素也即是所有元素放入[first,last)中，唯一保证是[first,last)中的元素以未知顺序排序过
middle==last，是对整个区间排序

//版本一，使用operator <来比较，都是先取元素后排序
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last); 

//版本二 ，用自定义的function object来比较
template <class RandomAccessIterator,class StrictWeakOdering>
void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last,StrictWeakOdering cmp);

partial_copy_sort

//版本一
template <class RandomAccessIterator>
void partial_sort_copy(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result_first,RandomAccessIterator result_last); 

//版本二 
template <class RandomAccessIterator,class StrictWeakOdering>
void partial_sort_copy(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result_first,RandomAccessIterator result_last,StrictWeakOdering cmp);

　　与partial_sort基本类似，复制[firstlast)中n个最小的元素到[result_first,result_first+n)中，n为[first,last)和[result_first,result_last)中的最小值，然后在进行排序。

　　不能copy到标准输出设备，result为RandomAccessIterator

nth_element

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last);

template <class RandomAccessIterator,class StrickWeakOrdering>
void nth_element(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last,StrickWeakOrdering cmp);

　　这里唯一的保证是数组被分为两段，第一段内的任何元素都不大于第二段，而每段中的内部排序并非重点

is_sorted

//版本一：调用operator < 
template <class ForwardIterator>
bool is_sorted(ForwardIterator first,ForwardIterator last);

//版本二：调用自己定义的function object
template <class ForwardIterator,class StrictWeakOrdering>
bool is_sorted(ForwardIterator first,ForwardIterator last,StrictWeakOrdering cmp);

　　两个版本都不操作range，只是测试range是否已经排过序，若first==last，两个版本都返回true。

码农公寓