01.冒泡排序

02.选择排序

03.插入排序

04.希尔排序

05.归并排序

06.快速排序

07.堆排序

08.计数排序

09.桶排序

10.基数排序

11.sort()函数排序

12.multiset排序

//Written by liwenfang
#include <bits/stdc++.h>
using namespace std;

//假设待排序数组为:
int k[5]={5,1,3,2,4};
int len=5;   //数组长度

//目标顺序数组为: {1,2,3,4,5}

//辅助函数说明
/*
* swap(auto,auto);     //交换两个变量的值
* max_element(RandomAddressIterator begin,RandomAddressIterator end);    //求区间[begin,end)内的最大元素的地址，包含于<algorithm>头文件
*/

//其他
/*
* 对于序列中的重复元素，排序时需要尽可能保证重复元素之间的相对顺序不发生变化，这也是判断排序算法稳定性的根本依据；
*/

01.冒泡排序

void Bubble_Sort(int *k,int len) {
    //冒泡排序在原序列上进行操作，不会产生额外内存占用
    //核心原理：在上一次比较结果的基础上继续比较下一对相邻元素并对其排序，直至序列有序
    //时间复杂度：O(n~n^2) 平均为O(n^2)
    //空间复杂度：O(1)
    //稳定性：稳定
    for(int i=0;i<len;i++) {
        for(int j=1;j<len;j++) {
            if(k[j-1]>k[j]) {
                swap(k[j-1],k[j]);
            }
        }
    }
    
    /*步骤演练
    * 第1.1次判断：比较5和1后k={1,5,3,2,4};
    * 第1.2次判断：比较5和3后k={1,3,5,2,4};
    * 第1.3次判断：比较5和2后k={1,3,2,5,4};
    * 第1.4次判断：比较5和4后k={1,3,2,4,5};
    * 第2.1次判断：比较1和3后k={1,3,2,4,5};
    * 第2.2次判断：比较3和2后k={1,2,3,4,5};
    * 第2.3次判断：比较3和4后k={1,2,3,4,5};
    * 第2.4次判断：比较4和5后k={1,2,3,4,5};
    * 第3.1次判断：比较1和2后k={1,2,3,4,5};
    * 第3.2次判断：比较2和3后k={1,2,3,4,5};
    * 第3.3次判断：比较3和4后k={1,2,3,4,5};
    * 第3.4次判断：比较4和5后k={1,2,3,4,5};
    * 第4.1次判断：比较1和2后k={1,2,3,4,5};
    * 第4.2次判断：比较2和3后k={1,2,3,4,5};
    * 第4.3次判断：比较3和4后k={1,2,3,4,5};
    * 第4.4次判断：比较4和5后k={1,2,3,4,5};
    * 第5.1次判断：比较1和2后k={1,2,3,4,5};
    * 第5.2次判断：比较2和3后k={1,2,3,4,5};
    * 第5.3次判断：比较3和4后k={1,2,3,4,5};
    * 第5.4次判断：比较4和5后k={1,2,3,4,5};
    */
}

02.选择排序

void Select_Sort(int *k,int len) {
    //选择排序在原序列上进行操作，不会产生额外内存占用
    //核心原理：从乱序子序列中拿出(不放回)一个最大或最小值，放到有序子序列(初始为空)的末尾，直至序列有序
    //时间复杂度：O(n^2)
    //空间复杂度：O(1)
    //稳定性：不稳定
    for(int pos=0;pos<len;pos++) {  //pos的作用：参与分割原序列(指定了k中有序子序列的末位元素的下一个元素和乱序子序列的首位元素)、计数已排序元素个数、防止内存泄漏
        int min_val=k[pos];
        for(int i=pos;i<len;i++) {
            //寻找最小值
            if(min_val>k[i]) min_val=k[i];
        }
        //与前方元素交换位置，腾出空位储存结果
        for(int i=0;i<len;i++) {
            if(k[i]==min_val) {
                swap(k[pos],k[i]);
                break;
            }
        }
    }

    /*步骤演练
    * 第0次执行： 分割pos=0 未拿到任何值                              此时    k={5,1,3,2,4};
    * 第1次执行： 分割pos=0 拿到元素k[pos]开始的最小值1 交换元素1和k[pos]的位置后 k={1,5,3,2,4};
    * 第2次执行： 分割pos=1 拿到元素k[pos]开始的最小值2 交换元素2和k[pos]的位置后 k={1,2,3,5,4};
    * 第3次执行： 分割pos=2 拿到元素k[pos]开始的最小值3 交换元素3和k[pos]的位置后 k={1,2,3,5,4};
    * 第4次执行： 分割pos=3 拿到元素k[pos]开始的最小值4 交换元素4和k[pos]的位置后 k={1,2,3,4,5};
    * 第5次执行： 分割pos=4 拿到元素k[pos]开始的最小值5 交换元素5和k[pos]的位置后 k={1,2,3,4,5};
    */
}

03.插入排序

void Insert_Sort(int *k,int len) {
    //插入排序在原序列上操作，不会产生额外内存占用
    //核心原理：遍历序列拿出值(不放回)，向前查找并插入到第一个大于或小于该元素的元素的前面或后面，直至序列有序
    //时间复杂度：O(n~n^2)
    //空间复杂度：O(1)
    //稳定性：稳定
    for(int i=0,j;i<len;i++) {
        //取到k[i]
        int got=k[i];
        //向前搜索并移动元素直至遇到有序元素
        for(j=i-1;j>=0&&k[j]>got;j--) {
            k[j+1]=k[j];
        }
        //插入元素
        k[j+1]=got;
    }

    /*步骤演练
    * 第0次执行： 未拿取到任何元素 此时  k={5,1,3,2,4};
    * 第1次执行： 拿取到元素5 向前移动后 k={5,1,3,2,4};
    * 第2次执行： 拿取到元素1 向前移动后 k={1,5,3,2,4};
    * 第3次执行： 拿取到元素3 向前移动后 k={1,3,5,2,4};
    * 第4次执行： 拿取到元素2 向前移动后 k={1,2,3,5,4};
    * 第5次执行： 拿取到元素4 向前移动后 k={1,2,3,4,5};
    */
}

04.希尔排序

05.归并排序

06.快速排序

07.堆排序

08.计数排序

void Count_Sort(int *k,int len) {
    //计数排序借助一个外部统计数组，并且需要排序的元素的值域必须是已知的
    //核心原理：将各个元素进行计数统计后重复取回
    //时间复杂度：O(n+k)
    //空间复杂度：O(k)
    //稳定性：稳定
    int max_val=*max_element(k,k+len);
    int s[max_val+1]={};   //原数组内最大元素为5
    //计数
    for(int i=0;i<len;i++) {
        s[k[i]]++;
    }
    //取回
    int pos=0;
    for(int i=0;i<max_val+1;i++) {
        for(int j=0;j<s[i];j++) {
            k[pos]=i;
            pos++;
            if(pos>=len) return;
        }
    }
    
    /*步骤演练
    * k={5,1,3,2,4};
    * 依次计数到s对应下标后
    * s={0,1,1,1,1,1};
    * 第1次取回： 从s[0]取回0个0后 新的k={};
    * 第2次取回： 从s[1]取回1个1后 新的k={1};
    * 第3次取回： 从s[2]取回1个2后 新的k={1,2};
    * 第4次取回： 从s[3]取回1个3后 新的k={1,2,3};
    * 第5次取回： 从s[4]取回1个4后 新的k={1,2,3,4};
    * 第6次取回： 从s[5]取回1个5后 新的k={1,2,3,4,5};
    */
}

09.桶排序

10.基数排序

11.sort()函数排序

/* sort()函数包含于头文件<algorithm>中
 * sort()函数极其强大，适用于所有支持随机访问的容器(如数组、vector、string、deque等)
 * sort()函数不只是简单的快速排序，它还结合了插入排序、堆排序，会根据不同的处理数量级自动选取合适的排序方法，其时间复杂度稳定在 O(n*log2(n)) ，性能表现出色
 * sort函数原型为：
       void sort(RandomAddressIterator begin,RandomAddressIterator end);    //默认升序排序区间[begin,end)内的元素
       void sort(RandomAddressIterator begin,RandomAddressIterator end,Compare comp);   //按自定义规则排序区间[begin,end)内的元素
       //Compare comp是一个自定义的排序函数(函数名或函数指针)，其原型要求为: bool cmp(int,int);
*/

//sort升序排序
sort(k,k+len)

//sort降序排序
sort(k,k+len,greater<int>());

//用自定义规则cmp排序
bool cmp(int a,int b) {
    return a>b;   //降序排序
}
sort(k,k+len,cmp);

/*
写自定义比较器cmp时注意要保证以下原则：
    cmp(a,a)==false
    cmp(a,b)!=cmp(b,a)
    即在cmp中不允许出现(return a <= b;)的情况
*/

12.multiset排序

void Multiset_Sort(int *k,int len,bool if_reverse=0) {
    //multiset排序借助STL中的multiset容器，multiset自动排序且不去重
    //核心原理：将元素覆盖到multiset容器中后再覆盖回原序列
    //本函数默认升序排序
    //使用本函数需要包含<multiset>和<algorithm>头文件
    multiset<int> s;
    for(int i=0;i<len;i++) {
        //覆盖到multiset
        s.insert(k[i]);
    }
    if(if_reverse) {
        //逆序
        vector<int> ks(len,0);
        copy(s.begin(),s.end(),ks.begin());
        reverse(ks.begin(),ks.end());
        //覆盖回原序列
        copy(ks.begin(),ks.end(),k);
        return;
    }
    //覆盖回原序列
    copy(s.begin(),s.end(),k);
}