排序专题
2021-05-11 / IOAOl   


​ 依赖于leetcode上的基本排序题目的校对，编写的排序专题。实现了十大基本排序算法。梳理了STL中排序的主要逻辑思路。

选择排序

1
2
3
4
5
6
7
8
9
10
11
void selectSort(vector<int>& nums){ //选择排序 //超时
        for(int i=0;i<nums.size()-1;i++){
            int min=i;
            for(int j=i+1;j<nums.size();j++){
                if(nums[min]>nums[j])
                    min=j;
            }
            if(min!=i)
                swap(nums[min],nums[i]);
        }
    }

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(vector<int>& nums){ //冒泡排序 //超时
    for(int i=1;i<nums.size();i++){
        bool flag=false;
        for(int j=nums.size()-1;j>=i;j--){
            if(nums[j-1]>nums[j]){
                swap(nums[j-1],nums[j]);
                flag=true;
            }
        }
        if(!flag)return;
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
void insertSort(vector<int> nums){
        for(int i=1;i<nums.size();i++){	//i代表现在要插入的元素的序号
            int j=i,tmp=nums[i];		//
            while(j>0&&nums[j-1]>tmp){
                nums[j]=nums[j-1];
                j--;
            }            
            nums[j]=tmp;
        }
    }

希尔排序

1
2
3
4
5
6
7
8
9
10
11
void shellSort(vector<int>& nums){  //希尔排序
        for(int grap=nums.size()/2;grap>0;grap=grap/2){
            for(int i=grap;i<nums.size();i++){
                int tmp=nums[i],j;
                for(j=i;j>=grap&&nums[j-grap]>tmp;j-=grap){
                    nums[j]=nums[j-grap];
                }
                nums[j]=tmp;
            }
        }
    }

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
random_device rd;
   void quickSort(vector<int>& nums,int leftIndex,int rightIndex){ //快排
       if(leftIndex>rightIndex)
           return ;
       int left=leftIndex;
       int right=rightIndex;
       int index=rd()%(right-left+1)+left;
       int privt=nums[index];
       swap(nums[index],nums[left]);
       while(left<right){
           while(left<right&&nums[right]>=privt)right--;
           nums[left]=nums[right];
           while(left<right&&nums[left]<=privt)left++;
           nums[right]=nums[left];
       }
       nums[left]=privt;
       quickSort(nums,leftIndex,left-1);
       quickSort(nums,left+1,rightIndex);
   }

归并排序

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void mergeSort(vector<int>& nums){
       int len=nums.size();
       vector<int> helper(len);
       for(int seg=1;seg<len;seg+=seg){//seg是现在处理的区间大小，从小到大
           for(int start=0;start<len;start+=(seg<<1)){	//处理seg大小的区间，从左到右
               //(注释s=start) k是总区间现在的处理序号，s1是左区间现在的序号，s2是右区间现在的序号
               //初始化时，左区间[start1,end1),右区间[start2,end2)
               int start1=start,end1=min(len,start+seg);
               int start2=min(len,start+seg),end2=min(len,start+(seg<<1));
               int k=start;
               while(start1<end1&&start2<end2)//两个区间都还有数，选择小的放前面，直到其中一个放完
                   helper[k++]=(nums[start1]<nums[start2])?nums[start1++]:nums[start2++];
               while(start1<end1)	//如果左区间还有数,全部放入
                   helper[k++]=nums[start1++];
               while(start2<end2)	//如果右区间还有数,全部放入
                   helper[k++]=nums[start2++];
           }
           std::swap(nums,helper);		//合并好的数放回原数组
       }
   }

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void mergeSort1(vector<int>& nums){
       vector<int> helper(nums.size());
       merge(nums,helper,0,nums.size());	//左闭右开
   }
   void merge(vector<int>& nums,vector<int>& helper,int left,int right){
       if(right-left<=1)return ;		//小于等于一不需要合并
       int mid=left+((right-left)>>1);
       merge(nums,helper,left,mid);	//归并左半部分
       merge(nums,helper,mid,right);	//归并右半部分
       //(注释s=start) s是总区间现在的处理序号，s1是左区间现在的序号，s2是右区间现在的序号
       int start=left,start1=left,start2=mid;	
       while(start<right){ 	//直到处理完总区间全部的数
           //当右区间到头或者，左区间还有并且左区间对于右区间满足条件，辅助数组放左区间的数
           if(start2>=right||(start1<mid&&nums[start1]<nums[start2]))
               helper[start++]=nums[start1++];
           else helper[start++]=nums[start2++];	//辅助数组放右区间的数
       }
       for(int i=left;i<right;i++)	//合并好的数放回原数组
           nums[i]=helper[i];
   }

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void heapSort(vector<int>& nums){
    for(int i=nums.size()/2-1;i>=0;i--)
        maxHeapify(nums,i,nums.size()-1);	//初始化大顶堆，nums.size()/2-1第一个父节点
    for(int i=nums.size()-1;i>0;i--){
        swap(nums[i],nums[0]);	//将最大的换到后面
        maxHeapify(nums,0,i-1);	//将前面的数继续堆化
    }
}

void maxHeapify(vector<int>& nums,int start,int end){
    int dad=start;
    int son=start*2+1;
    while(son<=end){
        if(son+1<=end&&nums[son+1]>nums[son])	//找到儿子中最大的
            ++son;
        if(nums[dad]>nums[son])	//父节点已经大于子节点，退出
            return;
        else{
            swap(nums[dad],nums[son]);		//继续往下堆化
            dad=son;
            son=dad*2+1;
        }
    }
}

基数排序

注意不能处理负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int maxBit(const vector<int> nums){		//找到数组中最大的数十进制有多少位
        int maxval= *max_element(nums.begin(),nums.end());
        int count=0;
        while(maxval>0){
            maxval/=10;
            ++count;
        }
        return count;
    }
    void radixSort(vector<int>& nums){
        int k=maxBit(nums),radix=1;//radix基数，1开始，个位开始
        int len=nums.size();
        vector<int> count(10);	//十进制数每个位10个可能
        vector<int> tmp(len);	//临时数组
        for(int j=1;j<=k;++j){		//有多少位就循环几次
            fill(count.begin(),count.end(),0); //处理新的位时，将count数组置0，重新计数
            for(auto num:nums)
                ++count[(num/radix)%10];	//每个元素找到自己的基数
            for(int i=0;i<count.size()-1;++i)
                count[i+1]+=count[i];	//将count数组的所有位叠加前面位的和
            for(int i=len-1;i>=0;--i)	//从数组后面开始找，保持算法稳定性
                tmp[--count[(nums[i]/radix)%10]]=nums[i];	//从count数组找到自己的位置，填入临时数组
            std::swap(tmp,nums);		//将临时数组赋值到nums数组
            radix*=10;			//处理下一位
        }
    }

处理负数的方法

思路1：这里将负数处理成正数（所有数加上最小值的绝对值，不过可能会溢出）

思路2：将负数和正数分开，负数处理成正数，反向拼接到正数，（未实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int maxBit(const vector<int> nums){
       int maxval= *max_element(nums.begin(),nums.end());
       int count=0;
       while(maxval>0){
           maxval/=10;
           ++count;
       }
       return count;
   }
   void radixSort(vector<int>& nums){
       int minval=*min_element(nums.begin(),nums.end());
       if(minval<0)
           for(int& num:nums){ 
               num+=(abs(minval)+1);
           }
       int k=maxBit(nums),radix=1;
       int len=nums.size();
       vector<int> count(10);
       vector<int> tmp(len);
       for(int i=1;i<=k;++i){
           fill(count.begin(),count.end(),0);
           for(auto num:nums)
               ++count[(num/radix)%10];
           for(int i=0;i<count.size()-1;++i)
               count[i+1]+=count[i];
           for(int i=len-1;i>=0;--i)
               tmp[--count[(nums[i]/radix)%10]]=nums[i];
           std::swap(tmp,nums);
           radix*=10;
       }
       if(minval<0)
           for(int& num:nums){ 
               num-=(abs(minval)+1);
           }
   }

计数排序

思路：建立一个(max-min)+1大小的数组。对数组的每一个元素都可以找到对应的x-min的位置

该数组记录每一个数到底有多少个。然后通过寻找这个数组，就可以确定元素在排序后的位置。

1
2
3
4
5
6
7
8
9
10
给出一个例子:[5,1,1,2,0,0]
该计数数组的变化为：
         2 2 1 0 0 1 //记录了数组中对应的个数
         2 4 5 5 5 6 //前一个元素加到后面的元素 countArray[i+1]+=countArray[i];
nums:5 ::2 4 5 5 5 5 //找元素5找到6，6-1就是5在排序好的数组的位置，更新数组为6-1
nums:1 ::2 3 5 5 5 5 //找元素1找到5，5-1就是1在排序好的数组的位置，更新数组为5-1
nums:1 ::2 2 5 5 5 5 //找元素1找到5，5-1就是1在排序好的数组的位置，更新数组为5-1
nums:2 ::2 2 4 5 5 5 //找元素2找到4，4-1就是2在排序好的数组的位置，更新数组为4-1
nums:0 ::1 2 4 5 5 5 //找元素0找到2，2-1就是0在排序好的数组的位置，更新数组为2-1 
nums:0 ::0 2 4 5 5 5 //找元素0找到1，1-1就是0在排序好的数组的位置，更新数组为1-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void CountingSort(vector<int>& nums){
        if(nums.size()==0)return;
        // int maxnum=*max_element(nums.begin(),nums.end());
        // int minnum=*min_element(nums.begin(),nums.end());
        int maxnum=nums[0];
        int minnum=nums[0];
        for(int i=1;i<nums.size();i++){
            maxnum=max(maxnum,nums[i]);
            minnum=min(minnum,nums[i]);
        }
        int offset=maxnum-minnum+1;
        vector<int> countArray(offset,0);
        for(int num:nums)
            ++countArray[num-minnum];
        for(int i=0;i<countArray.size()-1;i++)
            countArray[i+1]+=countArray[i];
        vector<int> tmpArray(nums.size());
        for(int i=nums.size()-1;i>=0;--i)
            tmpArray[--countArray[nums[i]-minnum]]=nums[i];
        nums.assign(tmpArray.begin(),tmpArray.end());
    }

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 假如对数组nums进行桶排序，nums的长度为L，最小元素为A，最大元素为B。
   // 则gap为(B-A)/L+1，桶的个数为(B-A)/gap+1。
   void bucketSort(vector<int>& nums){
       int maxval=*max_element(nums.begin(),nums.end());
       int minval=*min_element(nums.begin(),nums.end());
       int gap=(maxval-minval)/2+1;				//桶大小
       int bucketCount=(maxval-minval)/gap+1;		//桶数量
       vector<vector<int>> buckets(bucketCount,vector<int>());
       for(auto num:nums){			//装桶
           buckets[(num-minval)/gap].emplace_back(num);
       }
       int k=0;
       for(int i=0;i<bucketCount;++i){
           mergeSort(buckets[i]);				//桶内排序，随意一种排序
           for(int j=0;j<buckets[i].size();++j){
               nums[k++]=buckets[i][j];			//桶拼接
           }
       }
   }

STL中的Sort

快排在几乎数据几乎顺序的情况下，时间复杂度达到O（）。

堆排序的时间复杂度稳定在O（）。

插入排序在数据几乎顺序下的情况下，时间复杂度可以近乎O（）。

了解到以上三点。可以设计出一个泛用的算法。他就是std::sort。

具有以下特点：

  • 在数据量很大时采用正常的快速排序，此时效率为O()。
  • 一旦分段后的数据量小于某个阈值，就改用插入排序，因为此时这个分段是基本有序的，这时效率可达O()。
  • 在递归过程中，如果递归层次过深，分割行为有恶化倾向时，它能够自动侦测出来，使用堆排序来处理，在此情况下，使其效率维持在堆排序的O()，但这又比一开始使用堆排序好。

具体实现：

1
2
3
4
5
6
7
8
9
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        //传入首尾迭代器，类型，log10（长度*2）
        __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
        //插入排序，传入首尾迭代器
        __final_insertion_sort(first, last);
    }
}

首先执行__introsort_loop，然后在执行插入排序

看看__introsort_loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,	//传入首尾迭代器，类型，log10（长度*2）
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
    while (last - first > __stl_threshold) {   //__stl_threshold是宏，等于16，说明区间小于16就退出了
        if (depth_limit == 0) {					//传进来的最大深度被减完了,每一层减一
            partial_sort(first, last, last);	//说明深度太高，调用堆排序
            return;
        }
        --depth_limit;		//最大深度每一层减一
        RandomAccessIterator cut = __unguarded_partition			//调用快排，传入了首尾迭代器和快排的pivit
            //__median函数，它的作用是取首部、尾部和中部三个元素的中值作为pivot
          (first, last, T(__median(*first, *(first + (last - first)/2),
                                   *(last - 1))));
        __introsort_loop(cut, last, value_type(first), depth_limit);	//递归右区间
        last = cut;			//右区间递归完，右端点改为中点，改为递归左区间，这种调用可以减少递归调用，改为循环调用。
    }
}

看看快排。也就是上面的__unguarded_partition,返回一个根据pivit把左右区间分割开的中间点的迭代器

注意下面的first和last不需要判断越界，选择了首尾中间位置三个值的中间值作为pivot，因此一定会在超出此有效区域之前中止指针的移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
                                           RandomAccessIterator last, 
                                           T pivot) {
    while (true) {
        while (*first < pivot) ++first;	//比pivot小，first右移到比pivot大的元素
        --last;	//一开始是end，需要左移，后来的是已经交换过的元素，所以左移
        while (pivot < *last) --last;	//比pivot大，last左移到比pivot小的元素
        if (!(first < last)) return first;	//二者相遇，退出
        iter_swap(first, last);		//交换
        ++first;		//已经交换过的元素，所以右移
    }
}

返回来看上面的__introsort_loop函数

它有两种方法退出，

一是

1
while (last - first > __stl_threshold) {   //__stl_threshold是宏，等于16，说明区间小于16就退出了

二是

1
2
3
4
if (depth_limit == 0) {					//传进来的最大深度被减完了,每一层减一
   partial_sort(first, last, last);	//说明深度太高，调用堆排序
   return;
}

第一种对应了区间小于16，第二种对应深度太大，调用堆排序。

两种方法退出后都会执行__final_insertion_sort 也就是插入排序。

先看下堆排序partial_sort。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*, Compare comp) {
    make_heap(first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (comp(*i, *first))
            __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last, Compare comp) {
    __partial_sort(first, middle, last, value_type(first), comp);
}

看完了堆排序，这里可以看出堆排序和快排都会将数组中最小的放在第一个小区间中，堆排序无疑最小是第一个元素，快排到16大小区间之后，最小的元素必然在第一个16大小区间内。

了解到这点后，现在要看退出__introsort_loop后执行的

__final_insertion_sort函数

1
2
3
4
5
6
7
8
9
10
template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, 
                            RandomAccessIterator last) {
    if (last - first > __stl_threshold) {	//长度大于16，0到15用__insertion_sort 16到末尾用__unguarded_insertion_sort处理
        __insertion_sort(first, first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    }
    else	//小于16，执行__insertion_sort
        __insertion_sort(first, last);
}

看看这两个函数的区别

__unguarded_insertion_sort

1
2
3
4
5
6
7
8
9
10
11
12
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));		//这个函数在下面有//不带检查的插入
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, 	//从这里开始
                                RandomAccessIterator last) {
    __unguarded_insertion_sort_aux(first, last, value_type(first));	//传入首位迭代器和类型
}

__insertion_sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {	//不带检查的插入
    RandomAccessIterator next = last;
    --next;
    while (value < *next) {		//边找边将元素后移，注意这里next不可能越界，因为第一个元素比value小
        *last = *next;
        last = next;
        --next;
    }
    *last = value;	//找到就插入
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
                            RandomAccessIterator 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>
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));
}

插入完就结束算法。

具体的可以参考这篇博客,部分内容从此摘抄。

本文链接：
https://ioaol.github.io/%E6%8E%92%E5%BA%8F%E4%B8%93%E9%A2%98.html