。

冒泡排序

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
#include "bits/stdc++.h"

using namespace std;
/**
 * flag == 1  从小到大
 * flag == 2  从大到小
*/
int bubbleSort(vector<int> &vec, int flag){//冒泡排序
    int temp;
    for(int i = vec.size()-1; i > 0; i--){
        for(int j = 0; j < i; j++){
            if(vec[j] > vec[j+1] && flag == 1){
                vec[j+1] = vec[j+1]^vec[j];//这样使用虽然可以提高速度，但是一定要保证变换的是两个量，否则会出错
                vec[j]   = vec[j+1]^vec[j];
                vec[j+1] = vec[j+1]^vec[j];
            }
            else if(vec[j] < vec[j+1] && flag == 2){
                vec[j+1] = vec[j+1]^vec[j];
                vec[j]   = vec[j+1]^vec[j];
                vec[j+1] = vec[j+1]^vec[j];
            }
        }
    }
    return 0;
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int selectionSort(vector<int> &vec, int flag){//选择排序
    int index, j;
    for(int i = 0; i < vec.size() - 1; i++){
        for(j = i+1, index = i; j < vec.size(); j++){
            if(vec[j] < vec[index] && 1 == flag) index = j;
            else if(vec[j] > vec[index] && 2 == flag) index = j;
        }
        if(i == index) continue; //这样使用虽然可以提高速度，但是一定要保证变换的是两个量，否则会出错
        vec[i] = vec[i] + vec[index];
        vec[index] = vec[i] - vec[index];
        vec[i] = vec[i] - vec[index];
    }
    return 0;
}

插入排序

1
2
3
4
5
6
7
8
9
10
int insertionSort(vector<int> &vec, int flag){//插入排序
    int tmp = 0, j;
    for(int i = 1; i < vec.size(); i++){
        tmp = vec[i];
        if(1 == flag) for(j = i-1; j >= 0 && vec[j] > tmp; j--) vec[j+1] = vec[j];
        else if(2 == flag)  for(j = i-1; j >= 0 && vec[j] < tmp && 2 == flag; j--) vec[j+1] = vec[j];
        vec[j+1] = tmp;
    }
    return 0;
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
int shellSort(vector<int> &vec, int flag){ //希尔排序
    int temp, j, startIndex;
    for(int gap = vec.size()/2; gap >= 1; gap /= 2){
        for(startIndex = 0; startIndex < gap; startIndex++){
            for(int i = startIndex + gap; i < vec.size(); i += gap){
                if(1 == flag) for(temp = vec[i], j = i - gap; j >= 0 && vec[j] > temp; j -= gap) vec[j+gap] = vec[j];
                else if(2 == flag) for(temp = vec[i], j = i - gap; j >= 0 && vec[j] < temp; j -= gap) vec[j+gap] = vec[j];    
                vec[j+gap] = temp;
            }
        }
    }
    return 0;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int quickSort(vector<int> &vec, int flag, int first, int end){ //快排
    if(first >= end || first < 0 || end >= vec.size()) return 0;  // 注意前面是 first >= end 不能是 first != end
    int mid_num = vec[first], i, j;
    for(i = first, j = end; i < j; ){
        for(; i < j && vec[j] >= mid_num && 1 == flag; j--);       // flag == 1
        if(i < j && vec[j] < mid_num && 1 == flag) vec[i] = vec[j];
        for(; i < j && vec[i] <= mid_num && 1 == flag; i++);
        if(i < j && vec[i] > mid_num && 1 == flag) vec[j] = vec[i];

        for(; i < j && vec[j] <= mid_num && 2 == flag; j--);       //  flag == 2
        if(i < j && vec[j] > mid_num && 2 == flag) vec[i] = vec[j];
        for(; i < j && vec[i] > mid_num && 2 == flag; i++);
        if(i < j && vec[i] <= mid_num && 2 == flag) vec[j] = vec[i];
    }
    vec[i] = mid_num;
    quickSort(vec, flag, first, i-1);
    quickSort(vec, flag, i+1, end);
    return 0;
}

堆排序

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/**
 * 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
 * 左右子节点不需要满足大小关系。建好堆后，每取出堆顶值，需要重新排序一次，适合于大量数据中搜索top k
*/
int heapCreate(vector<int> &vec, int flag){
    vec.insert(vec.begin(), 0);
    int temp;
    if(vec.size()%2 == 1){  // vec 数组包含偶数个数时（注意前面加了个0）//主要是为了把最后一个父节点处理了，他可能没有右节点
        if(1 == flag && vec[vec.size()/2] > vec[(vec.size()/2)*2]){
            temp = vec[(vec.size()/2)*2];
            vec[(vec.size()/2)*2] = vec[vec.size()/2];
            vec[vec.size()/2] = temp;
        }
        else if(2 == flag && vec[vec.size()/2] < vec[(vec.size()/2)*2]){
            temp = vec[(vec.size()/2)*2];
            vec[(vec.size()/2)*2] = vec[vec.size()/2];
            vec[vec.size()/2] = temp;
        }
    }
    for(int j = vec.size() / 2 - 1; j >= 1; j--){ // 每个父节点都有左右子节点
        int i = j;
        while(2*i < vec.size()){
            if(1 == flag && (vec[i] > vec[2*i] || vec[i] > vec[2*i+1])){
                if(vec[2*i] >= vec[2*i+1]){
                    temp = vec[2*i+1];
                    vec[2*i+1] = vec[i];
                    vec[i] = temp;
                    i = 2*i+1;
                    continue;
                }
                else{
                    temp = vec[2*i];
                    vec[2*i] = vec[i];
                    vec[i] = temp;
                    i=2*i;
                    continue;
                }
            }
            else if(2 == flag && (vec[i] < vec[2*i] || vec[i] < vec[2*i+1])){
                if(vec[2*i] <= vec[2*i+1]){
                    temp = vec[2*i+1];
                    vec[2*i+1] = vec[i];
                    vec[i] = temp;
                    i = 2*i+1;
                    continue;
                }
                else{
                    temp = vec[2*i];
                    vec[2*i] = vec[i];
                    vec[i] = temp;
                    i = 2*i;
                    continue;
                }
            }
            break;
        }
        
    }
    return 0;
}
int heapGetMax(vector<int> &vec, int flag){
    int res = vec[1];
    int temp;
    vec[1] = vec[vec.size()-1];
    vec.pop_back();
    if(vec.size() == 1) return res;
    int i = 1;
    while(1 == flag && (2*i < vec.size()) && ((vec[i] > vec[2*i]) || ((2*i+1)>=vec.size()?0:(vec[i] > vec[2*i+1])))){
        if((2*i+1)>=vec.size() || vec[2*i] < vec[2*i+1]){
            temp = vec[2*i];
            vec[2*i] = vec[i];
            vec[i] = temp;
            i = 2*i;
            continue;
        }
        else{
            temp = vec[2*i+1];
            vec[2*i+1] = vec[i];
            vec[i] = temp;
            i = 2*i + 1;
            continue;
        }
        break;
    }
    while(2 == flag && (2*i < vec.size()) && ((vec[i] < vec[2*i]) || ((2*i+1)>=vec.size()?0:(vec[i] < vec[2*i+1])))){
        if((2*i+1)>=vec.size() || vec[2*i] > vec[2*i+1]){
            temp = vec[2*i];
            vec[2*i] = vec[i];
            vec[i] = temp;
            i = 2*i;
            continue;
        }
        else{
            temp = vec[2*i+1];
            vec[2*i+1] = vec[i];
            vec[i] = temp;
            i = 2*i+1;
            continue;
        }
        break;
    }
    return res;
}
int heapSort(vector<int> &vec, int flag){ //堆排序
    vector<int> out;
    heapCreate(vec, flag);
    while(vec.size() >= 2){
        out.push_back(heapGetMax(vec, flag));
    }
    vec.swap(out);
    return 0;
}

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(void){
    vector<int> vec{7,5,9,6,4,12, 68,4,5,1,2,6,7};
    //bubbleSort(vec, 2);
    //for(auto var : vec)  cout << var << "  ";
    //selectionSort(vec, 2);
    //for(auto var : vec)  cout << var << "  ";
    //insertionSort(vec, 2);
    //for(auto var : vec)  cout << var << "  ";
    //shellSort(vec, 2);
    //for(auto var : vec)  cout << var << "  ";
    //quickSort(vec, 2, 0, vec.size()-1);
    //for(auto var : vec)  cout << var << "  ";
    heapSort(vec, 2);
    for(auto var : vec)  cout << var << "  ";
    return 0;
}

二分查找

可以参考这篇内容详解二分查找算法

码题集2072：

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h> 

using namespace std;

int check(int interval, const vector<int> &pos, int target){
    int pre = pos[0];
    int cnt = 1;
    for(int i = 1; i < pos.size(); i++){
        if(pos[i] - pre >= interval){
            cnt++;
            pre = pos[i];
        }
    }
    if(cnt == target) return 1;
    else if(cnt > target) return 2;
    else return -1;
}
int main( )
{
    int N, M;
    cin >> N >> M;
    vector<int> pos(N);
    for(int i = 0; i < N; i++) cin>>pos[i];
    sort(pos.begin(), pos.end());
    int l = 1;
    int r = (pos[pos.size()-1] - pos[0]) / (M - 1) + 1;
    int mid;
    int res;
    //cout<<r<<" "<<l <<" "<<pos[pos.size()-1] <<" \n";
    while(l <= r){
        mid = l + (r - l) / 2;
        int flag = check(mid, pos, M);
        if(flag == 1){
            l = mid+1;
            res = mid;
        }
        else if(flag == 2){
            l = mid+1;
            res = mid;
        }
        else{
            r = mid-1;
        }
    }
    cout<<r;//l-1，r应该都行吧；但是不能是mid，因为每次进入循环mid都会更改，不能够代表有效的最大值
    return 0;
}

链接中给出的一般二分查找是查找在数组中已有的值，拓展后可以找到左右边界。而本题中也不是找一个具体的值，而是找一个最大值，类似找右边界，代码也是类似的。

二分查找和排序有共同点，进行循环查找前，都需要先明确是左闭右闭或者是其他。根据这个，每次左边界，右边界变化情况不同，并且跳出循环后，左右边界代表的意义也不同。本代码中，是左闭右闭，while循环条件需要是等于，因为哪怕是l == r时，都还有个区间[l, r]的值没进行判断，跳出循环的条件是l = r+1（肯定不会是l = r+2之类的，不要钻牛角尖，仔细想想）。最后一次check值返回1，2时的mid就应该是最终的结果，可以用个res保存。最后l会被赋值为mid+1。故最终 l-1 即为结果。又因为l = r + 1，r也是最终结果。