头像

烟花易冷


访客:438

在线 



烟花易冷
49分钟前
代码就是yxc大佬的代码,我来贴个注释
// 贪心

//将所有奶牛按照 minSPF 从大到小的顺序排序,然后依次考虑每头奶牛;
//对于每头奶牛,扫描当前所有能用的防晒霜,选择 SPF 值最大的防晒霜来用;

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

typedef pair<int,int> PII;
const int N = 2510;

int n, m, res = 0;
PII cows[N];
map<int, int> spfs;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) 
        cin >> cows[i].first >> cows[i].second;// n头牛的minSPF值和maxSPF值 
    for (int i = 0; i < m; i ++ )
    {
        int spf, cover;
        cin >> spf >> cover;// 防晒霜的spf值和数量 
        spfs[spf] += cover; // spf值可能相同 
    }
    sort(cows, cows + n);// 将所有奶牛按照 minSPF 从小到大的顺序排序 
    spfs[0] = spfs[1001] = n;// 哨兵 
    for (int i = n - 1; i >= 0; i -- )// 倒序(拨正排序)
    {
        auto spf = spfs.upper_bound(cows[i].second);// 大于第i头牛的maxSPF的最小元素 
        spf --;// spf--即为小于等于第i头牛的maxSPF值的最大元素 
        if (spf -> first >= cows[i].first)// 如果spf值大于第i头牛的minSPF值
        {
            res ++ ;// 发放防晒霜
            if (--spf -> second == 0)// 数量为零,删除防晒霜名字 
                spfs.erase(spf);
        }
    }
    cout << res << endl;
    return 0;
}



偷懒写法(next_permutation nb!)

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> permutation(vector<int>& nums) {
        do
        {
            ans.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));                             // 全排列 
        return ans;
    }
};





分享 STL之pair

自己综合了一些大佬的代码,做个笔记。
其实就是复习一下。。。
整理STL偷懒,现在就遇到了。。。
// pair

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

// 关联式容器 

// 创建

pair <string, double> pair1;
pair <string, string> pair2("调用第 2 种","构造函数");  
pair <string, string> pair3(pair2);
pair <string, string> pair4(make_pair("调用移动", "构造函数"));
pair <string, string> pair5(string("调用第 5 种"), string("构造函数"));

// 属性值 

p.first;
p.second; 

// 运算符 

<,<=,>,>=,==,!=;

//函数

sort();                                                                         // 默认对first升序,当first相同时对second升序
swap();                                                                         // 2个 pair 对象的键和值的类型要相同

125题
125.png

125题题解
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    pair<int, int> a[n];
    int w, s;
    for (int i = 0; i < n; i++)
    {
        cin >> w >> s;
        a[i].first = w + s;
        a[i].second = s;
    }
    sort(a, a + n); // pair 默认对first升序,当first相同时对second升序(完美符合题意)
    long long res = -1e18, sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum -= a[i].second;  //减去当前牛的强壮程度
        res = max(res, sum); //选取最小危险值
        sum += a[i].first;   //加上当前牛的重量和强壮程度,即sum变为重量之和
    }
    cout << res;
    system("pause");
    return 0;
}
参考资料

https://www.acwing.com/solution/content/845/
http://c.biancheng.net/view/7169.html
https://blog.csdn.net/sevenjoin/article/details/81937695
125题链接
https://www.acwing.com/problem/content/description/127/







自己综合了一些大佬的代码,做个笔记。
其实就是复习一下。。。
整理STL偷懒,现在就遇到了。。。

// 优先级队列Priority Queue

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

// 适配器容器 

// 利用堆实现

//创建

priority_queue<int> values; 

int values[]{4,1,3,2};                                                          // 普通数组初始化 
priority_queue<int> copy_values(values, values+4);                              // {4,2,3,1}
array<int,4> values{ 4,1,3,2 };                                                 // 序列式容器初始化 
priority_queue<int> copy_values(values.begin(), values.end());                  // {4,2,3,1}

int values[]{ 4,1,2,3 };                                                        // 手动指定排序规则和底层容器 
priority_queue<int, deque<int>, greater<int> > copy_values(values, values+4);   // {1,3,2,4}

//方法

Heap.empty();
Heap.push();
Heap.pop();
Heap.top();
Heap.size();

priority_queue.png
54题
54.png

54题题解
class Solution {
public:
    void insert(int num){
        maxHeap.push(num);//推n入大顶堆
        if(maxHeap.size() > minHeap.size() + 1)//大顶堆比小顶堆+1大
        {
            int t = maxHeap.top();//t=最大值
            maxHeap.pop();//删除最大值
            minHeap.push(t);//推入小顶堆
        }
        while(minHeap.size() && maxHeap.top() > minHeap.top())//大顶堆最大值 比 小顶堆最小值大 且 小顶堆存在
        {
            int t1 = maxHeap.top();//交换两个极值
            int t2 = minHeap.top();
            maxHeap.pop(); maxHeap.push(t2);
            minHeap.pop(); minHeap.push(t1);
        }
    }
    double getMedian(){
        int n1 = minHeap.size();
        int n2 = maxHeap.size();
        if(n1 == n2) return (minHeap.top() + maxHeap.top()) / 2.0;//输出大顶堆最大值与小顶堆最小值的平均数,即中位数
        else return maxHeap.top();
    }
private:
    priority_queue<int> maxHeap;//优先队列声明大顶堆
    priority_queue<int, vector<int>, greater<int>> minHeap;//优先队列声明小顶堆
    //int-数据类型,vector<int>-数据容器,greater<int>-仿函数声明用于小顶堆
};
参考资料

https://www.acwing.com/solution/content/1665/
https://blog.csdn.net/txl16211/article/details/44588487
http://c.biancheng.net/view/6987.html
54题链接
https://www.acwing.com/problem/content/88/



分享 尺取

自己综合了一些大佬的代码,做个笔记。
其实就是复习一下。。。
poj3061
转载 

https://blog.csdn.net/doubleguy/article/details/81265327
尺取.png

// 尺取

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

int main()
{
    int ans, i, j, n, a[200], sum, max;
    cin>>n>>max;
    for(i=0;i<n;i++)
        cin >> a[i];
    i = j = sum = 0;
    ans = n;
    while(1)
    {
        while(j < n && sum < max)                                               // 求a[i]到a[j]和sum,使其大于等于max 
            sum += a[j++];                                                      // 毛毛虫伸腿 
        if(sum < max)                                                           // 如果sum<max(统计完成)退出 
            break;
        ans = min(ans, j - i);                                                  // 求满足要求最小长度 
        sum -= a[i++];                                                          // 毛毛虫收腿 
    }
    cout << ans;
    return 0;
}


分享 贪心

自己综合了一些大佬的代码,做个笔记。
其实就是复习一下。。。
我修改一些代码,并代入数据模拟一下(方便理解)
原分享在文中已贴出(大佬讲得十分详细)
// 贪心

从问题的某一初始解出发;
while(能朝给定总目标前进一步)
{
    利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
}
// 旅行家

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

const int N = 110;
int i, j, n;
double d1, d2, c, w, ans, p[N], d[N], s[N];

int main()
{
    cin >> d1 >> c >> d2 >> p[0] >> n;                                              
    for(i = 1; i <= n; i++)
        cin >> d[i] >> p[i];
    d[n + 1] = d1;                                                              // 终点(另一个城市)
    d[0] = 0;                                                                   // 起点加油站距离为0
    for(i = 0; i <= n; i++)
        s[i] = (d[i + 1] - d[i]) / d2;                                          // 相邻油站(i,i+1)花费的油
    i = 0;  
    while(i < n)
    {
        j = i + 1, w = c;
        while(p[i] < p[j] && w)                                                 // 如果i比j价格低且油未装满
        {
            double now = min(s[j], w);                                          // 避免油箱装满(加油增量最多为路径量) 
            if (s[i] + now > c)                                                 // 避免出界(在便宜的前站多加,上限为c) 
                now = c - s[i];
            s[i] += now;                                                        // 多装now
            s[j] -= now;                                                        // 少装now
            w -= now;                                                           // 剩余油量减少
            j++;                                                                // 下一个
        }
        i = j;
    }
    for(i = 0; i <= n; i++)
    {
        if (s[i] > c)                                                           // 加油量大于容量 
        {
            cout << "No Solution";                                              // 无解快乐
            return 0;
        }
        ans += p[i] * s[i];                                                     // 统计
    }
    cout << fixed << setprecision(2) << ans;
    return 0;
}

旅行家1~1.jpg
旅行家2~1.jpg
https://www.acwing.com/blog/content/245/

// 特技飞行(贪心排序) 

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

const int N = 1100;
int n, m, k, a[N], ans;

int cmp(int a, int b)
{
    return a > b;
}

int main()
{
    cin.tie(0);                                                                 // 解除cin与cout绑定 
    ios::sync_with_stdio(false);                                                // 打消iostream的输入 输出缓存

    cin >> n >> k;
    for(int i = 1; i <= k; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + k, cmp);                                                // 贪心排序(由大到小)
    m = n - 1;                                                                  // 最大距离
    for(int i = 1;i <= min(k, n / 2); i++)
    {
        ans += a[i] * m;                                                        // 加上本次项目的价值
        m -= 2;                                                                 // 距离减少两个
    }
    cout << ans;
    return 0;
}

旅行家1~1.jpg
https://www.acwing.com/blog/content/246/

// 斐波那契 

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 110;
int f[N], x, n;

inline int check(int x)
{
    int cnt = 0, p = 0;
    while(x)
    {
        p = lower_bound(f + 1, f + 1 + 98, x) - f;                              // p 大于等于x中 最小数下标 
        x = min(x - f[p - 1], f[p] - x);                                        // p-1 小于等于x中 最大数下标 
        cnt++;
    }
    return cnt;
}

inline void init()
{
    cin >> n;
    f[0] = 0;
    f[1] = 1;
    for(int i = 2; i <= 98; i++)
        f[i] = f[i - 1] + f[i - 2];                                             // 建立斐波那契数列 
    while(n--)
    {
        cin >> x;
        cout << check(x) << endl;
    }
}

signed main()
{
    init();
    return 0;
}

斐波那契~1.jpg
https://www.acwing.com/blog/content/769/

// sticks

#include <bits/stdc++.h>
const int N = 1000010;
using namespace std;
int i, n, t, tot, s1, s2, s3;

struct node
{
    int c, l;
} a[N]; 

int cmp(node a, node b)                                                         // 对l排序 
{
    return a.l < b.l;
}

int main()
{
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> t;
        while(t--)
        {
            a[++tot].c = i;
            cin >> a[tot].l;
        }
    }
    sort(a + 1, a + 1 + tot, cmp);

    for(i = 1; i <= tot; i++)                                                   // s1为最长木棒,s2次之,s3再次之 
    {
        if(a[i].c == a[s1].c)                                                   // 和s1颜色相同
        {
            if(a[s3].l + a[s2].l > a[i].l)
            {
                cout << a[s3].c << " " << a[s3].l << " " << a[s2].c << " " << a[s2].l << " " << a[i].c << " " << a[i].l;
                break;
            }
            s1=i;                                                               // 此棒变为为s1 
        }
        else if(a[i].c == a[s2].c)                                              // 和s2颜色相同
        {
            if(a[s3].l + a[s1].l > a[i].l)
            {
                cout << a[s3].c << " " << a[s3].l << " " << a[s1].c << " " << a[s1].l << " " << a[i].c << " " << a[i].l;
                break;
            }
            s2 = s1, s1 = i;                                                    // s1变为s2,此棒变为s1 
        }
        else                                                                    // 和s3颜色相同
        {
            if(a[s2].l + a[s1].l > a[i].l)
            {
                cout << a[s2].c << " " << a[s2].l << " " << a[s1].c << " " << a[s1].l << " " << a[i].c << " " << a[i].l;
                break;
            }
            s3 = s2, s2 = s1, s1 = i;                                           // s2变为s3,s1变为s2,此棒变为s1 
        }
    }
    if(i > tot)
        cout << "NIE";
    return 0;
}

sticks~1.jpg
https://www.acwing.com/blog/content/771/

 以上题解均来自秦淮岸大大


分享 STL

自己综合了一些大佬的代码,做个笔记。
其实就是复习一下。。。

#include <bits/stdc++.h>
using namespace std;
//序列式容器(类数组) 
#include <vector>

// 定义 初始化 

vector<int> v;                                                                  // 默认初始化
vector<int> v(v1);                                                              // 用v1初始化v
vector<int> v(v1.begin(), v1.end());                                            // 用v1初始化v 
vector<int> v(10);                                                              // 定义一个大小为10的数组!
vector<int> v(10,1);                                                            // 定义个全为1而且长度为10的数组 

// 方法

v.front();                                                                      // 首元素
v.back();                                                                       // 尾元素
v.begin();                                                                      // 头指针 
v.end();                                                                        // 尾指针+1 
v.rend();                                                                       // begin-1 
v.rbegin();                                                                     // end-1 
v.push_back();                                                                  // 尾增
v.pop_back();                                                                   // 尾删
v.size();                                                                       // 长度 
v.empty();                                                                      // 判空
v.clear();                                                                      // 清空
v.insert(); 
   v.insert(p, t);                                                              // 将t插到p的前面
   v.insert(p, n, t);                                                           // 将n个t插入p之前
   v.insert(p, i, j);                                                           // 将区间[i,j)的元素插入到p之前
v.erase(t,k);
   v.erase(t, k);                                                               // 删除他们之间的元素
   v.erase(p);                                                                  // 删除p指向的元素

// 遍历 

for(int i = 0; i < v.size(); i++)                                               // 下标法
    cout << v[i];
vector <int>::const_iterator iterator = v.begin();                              // 迭代器法
for(; iterator != v.end(); iterator++)
    cout << *iterator;

#include <deque>

// 方法(较vector新增) 

d.push_front();                                                                 // 头增 
d.pop_front();                                                                  // 头删 

#include <list>

// 方法(新增) 

l.sort();                                                                       // 排序,O(nlogn)
merge(list<T,Alloc>&x);                                                         // 将x放入T中合并,x为空
remove(const T &val);                                                           // 删除val的所有元素 
l.splice(iterator pos, list<T,Alloc>x);                                         // 将x的内容加到pos的前面
l.unique();                                                                     // 去重

容器简介.png
容器函数.png

// 适配器容器
#include <stack>

// 创建

stack<int> values;                                                              // 默认基础容器 deque 
stack<string, list<int>> values;                                                // 修改基础容器为 vector、deque、list
list<int> values {1, 2, 3};                                                     // 用基础容器来初始化 stack 适配器
stack<int, list<int>> my_stack (values);

// 方法

s.empty();                                                                      // 判空
s.size();                                                                       // 长度
s.pop();                                                                        // 删除栈顶
s.top();                                                                        // 返回栈顶
s.push(item);                                                                   // 压入新元素

#include <queue>

// 创建

queue<int> values;                                                              // 默认基础容器 deque 
queue<int, list<int>> values;                                                   // 修改基础容器为 deque、list
deque<int> values{1,2,3};                                                       // 用基础容器来初始化 queue 适配器
queue<int> my_queue(values);

// 方法

q.empty();                                                                      // 判空
q.size();                                                                       // 长度
q.push(item);                                                                   // 队尾压入新元素
q.front();                                                                      // 返回队首元素
q.back();                                                                       // 返回队尾元素
q.top();                                                                        // 返回具有最高优先级的元素

stack.png
queue.png

// 关联式容器  
#include <set>

// 创建

set<string> myset;
set<string> myset{"abc", "defg", "hijk"};
set<string> copyset(myset);                                                     // 复制原有set 

// 方法

s.size();
s.empty();
s.clear();
s.begin();
s.end();
s.insert(); 
s.find();                                                                       // 查找
s.count();                                                                      // 统计
s.erase();

#include <map>

// 创建

map<string, int> mymap;
map<string, int> mymap{ {"set",1},{"map",2} };
map<string, int> newmap(mymap);

// 方法

m.size(); 
m.empty();
m.clear();
m.begin();
m.end();
m.insert(); 
m.erase();  
m.find(); 

set.png
map.png
总览
总览.jpg

图片来自c语言中文网


分享 排序模板

自己综合了一些大佬的代码,做个笔记。
其实就是复习一下。。。

#include <iostream>

using namespace std;
int cnt = 0; 
int range = 20;

// 冒泡排序 O(n^2) 稳定

void bubbleSort(int a[], int n)
{
    for(int i = n - 1; i > 0; i--)
    {
        bool flag = true;
        for(int j = 0; j < i; j++)
        {
            if(a[j] > a[j+1]) 
            {
                swap(a[j], a[j+1]);                                             // 从前到后遍历,依次冒泡最大的数 
                flag = false;
            }                                               
        }
        if(flag)
             break;
    }
}

// 梳排序(冒泡优化) O(nlog(n)) 

void combSort(int a[],int l,int r)
{
    float factor = 1.3;
    int g = r - l + 1;
    int n = r + 1;
    bool flag = true;
    while( g > 1 || flag )
    {
        g = ( g > 1 ) ? g / factor : g;                                         // 确定梳长g,由旧g/factor确定 
        flag = false;
        int i = 0;
        while( i + g < n )                                                      // flag为false且g=1直接跳出循环
        {
            if(a[i] > a[g+i])
            {
                swap(a[i], a[g+i]);
                flag = true;
            }
            i = i + 1;
        }
    }
}

// 快速排序 O(nlogn)

void quickSort(int a[], int l, int r)
{
   if(l>=r) return;                                                             // 输入错误 

   int i = l, j = r, tmp = a[l];                                                // 取值 

   while(i < j)
   {
        while(i < j && a[j] >= tmp)                                             // j下标移动直到右端数值比基准小 
            j--;
        while(i < j && a[i] <= tmp)                                             // i下标移动直到左端数值比基准大 
            i++;
        if(i < j) 
            swap(a[i],a[j]); 
   }
   a[l] = a[i];                                                                 // 基准与a[i]交换,归位 
   a[i] = tmp;
   quickSort(a,l,i-1);                                                          // a[i]已归位 
   quickSort(a,i+1,r);
}

// 快速排序(优化) O(nlogn)

void quickSort_pro(int a[], int l, int r)
{
   if(l>=r) return;                                                             // 输入错误 

   int i = l-1, j = r+1, tmp = a[l];                                            // 取值 

   while(i < j)
   {
        do i++; 
           while(tmp>a[i]);                                                     // i下标移动直到左端数值比基准大 
        do j--; 
            while(tmp<a[j]);                                                    // j下标移动直到右端数值比基准小 
        if(i < j) 
            swap(a[i],a[j]); 
   }
   quickSort(a,l,j);                                                            // a[j]未归位,继续代入排序 
   quickSort(a,j+1,r);
}

// 插入排序 O(n^2) 稳定

void insertSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        int tmp = a[i], j;
        for(j = i; j > 0 && tmp < a[j-1]; j--)                                  // 从第二位开始向后遍历,倒序与之前比较,大值后移,停止时插入 
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

// 折半插入排序 O(n^2) 

void insertSort_pro(int a[], int n)
{
    int i, j, low, high, mid, temp;
    for(i = 1; i < n; i++)
    {
        temp = a[i];
        low = 0;
        high = i - 1;

        while(low <= high)                                                      // 从前往后,逐次二分查找a[i]位置 
        {
            mid = (low + high) >> 1;
            if(temp < a[mid])
                high = mid - 1;
            else low = mid + 1;
        }

        for(j = i ; j >= low ; j--)                                             // low后的元素后移 
            a[j] = a[j - 1];    
        a[low] = temp;
    }
}

// 选择排序 O(n^2)

void selectSort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] > a[j]) 
                swap(a[i], a[j]);                                               // 从前到后遍历,依次与后值比较,大于便交换 
        }
    }
}

// 归并排序 O(nlogn) 稳定

void mergeSort(int a[], int l, int r)
{
    if(l >= r) return;

    int tmp[r+1];
    int mid = l + r >> 1;
    mergeSort(a,l,mid), mergeSort(a,mid+1,r);
    int i = l , j = mid + 1, k = 0;                                             // a,j分别为两个区间的起点 

    for(k = l; k <= r; k++)
    {
        if(j > r || (i <= mid && a[i] <= a[j]) )                                // 右区间已遍历完成 或 左区间未遍历完成且a[i]<=a[j]    
            tmp[k] = a[i++];                                                    // 获得左区间数值 
        else                                                                    // 右区间未遍历完成 且 左区间遍历完成或a[i]>a[j] 
        {    
            cnt += mid - i + 1;                                                 // 统计逆序对 
            tmp[k] = a[j++];
        }    
    } 

    for( k = l; k <= r; k++)
      a[k] = tmp[k];                                                            // 赋值原数组 
}

// 堆排序 O(nlogn)

void adjust_heap(int a[], int x, int n)
{
    int l = x * 2 + 1;                                                          // 左孩子结点 
    int r = x * 2 + 2;                                                          // 右孩子结点 
    int max = x;                                                                // 临时变量 

    if(l < n && a[l] > a[max])                                                  // 左孩子大于叶子结点 
        max = l;
    if(r < n && a[r] > a[max])                                                  // 右孩子大于叶子结点 
        max = r;

    if(max != x)
    {
        swap(a[x], a[max]);                                                     // 调整 
        adjust_heap(a, max, n);
    }
}

void heapSort(int a[], int n)
{
    for(int i = n/2-1; i >= 0; i--)                                             // 非叶子结点最大序号值 
        adjust_heap(a, i, n);

    for(int i = n-1; i > 0; i--)
    {
        swap(a[0], a[i]);                                                       // 每次将剩余元素中的最大者放到最后面--排序 
        adjust_heap(a, 0, i);                                                   // 重新调整堆顶为大顶堆
    }
}

// 计数排序 o(n+k) 

void countSort(int a[], int n)
{
    int cnt[range]={0};
    for(int i = 0; i < n; i++) 
        cnt[a[i]]++;                                                            // 计数a[i]中数值出现次数于cnt[a[i]] 

    for(int i = 1, k = 0; i <= n; i++)
    {
        while(cnt[i]--)
            a[k++]=i;                                                           // 将cnt中统计数据逐个赋值给a[k] 
    }
}

// 基数排序 O(n*k) 

int maxbit(int a[], int n) 
{
    int d = 1;                                                                  // 保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(a[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}

void radixSort(int a[], int n) 
{
    int d = maxbit(a, n);
    int tmp[n];
    int count[10];                                                              // 计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++)                                                     // 进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0;                                                       // 每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (a[j] / radix) % 10;                                            // 统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j];                                 // 将tmp中的位置依次分配给每个桶,count中的数字为之前所有个数之和 
        for(j = n - 1; j >= 0; j--)                                             // 将所有桶中记录依次收集到tmp中
        {
            k = (a[j] / radix) % 10;                                            // 求单个数位k 
            tmp[count[k] - 1] = a[j];                                           // a中数值据count数组分配给tmp 
            count[k]--;
        }
        for(j = 0; j < n; j++)                                                  // 将临时数组的内容复制到data中
            a[j] = tmp[j];
        radix = radix * 10;
    }
}

// 希尔排序(选择法) O(nlogn) 

void shellSort_se(int a[], int n)
{
    for(int gap = n / 2; gap > 0; gap /= 2)
    {
        for(int i = gap; i < n; ++i)                                            // 从第gap个元素,逐个对其所在组进行排序操作
        {
            int j = i;
            while(j >= gap && a[j] < a[j - gap])
            {
                swap(a[j], a[j - gap]);                                         // 交换数值 
                j -= gap;
            }
        }
    }
}

// 希尔排序(插入法) O(nlogn) 

void shellSort_in(int a[], int n)
{
    for(int gap = n / 2; gap > 0; gap /= 2)
    {
        for(int i = gap; i < n; i++)
        {
            int j = i;
            int temp = a[i];
            if(a[j] < a[j - gap])
            {
                while(j - gap >= 0 && temp < a[j - gap])
                {
                    a[j] = a[j - gap];                                          // 元素后移 
                    j -= gap;
                }
                a[j] = temp;
            }
        }
    }
}

int main()
{
    int a[] = {3, 2, 1, 5, 3, 10, 3, 7, 6, 7, 9, 8, 1};
    int n = sizeof(a)/sizeof(int);
//    bubbleSort(a, n); 
//  combSort(a, 0, n-1);
//    quickSort(a, 0, n-1);
//    quickSort_pro(a, 0, n-1);
//    insertSort(a, n);
//  insertSort_pro(a, n);
//  shellSort_in(a, n);
//    selectSort(a, n);
//  shellSort_se(a, n);
//    heapSort(a, n);
//  countSort(a, n);
//  radixSort(a, n);
//    mergeSort(a, 0, n-1);
//  cout << cnt << endl;
    for(int i = 0; i < n; i++) 
        cout << a[i] << ' ';
    cout << endl;
}