数据结构和算法学习 排序 快速排序—分治

步骤：

专业成都网站建设公司，做排名好的好网站，排在同行前面，为您带来客户和效益!创新互联公司为您提供成都网站建设，五站合一网站设计制作，服务好的网站设计公司，成都做网站、网站设计负责任的成都网站制作公司!

1. 确定分界点x,可以是左边界可以是右边界可以是中点
2. 调整区间（左边段小于等于x，右边段大于等于x）重点和难点 ⭐
3. 递归处理左右两端（最终使左右两断有序，因为左边始终小于等于右边，所以整个有序）

#includeusing namespace std;
const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r) {if (l >= r) return;
    int x = q[l], i = l - 1, j = r + 1;//选择左右都是可以的
    while (i< j) {do {i++;
        } while (q[i]< x);
        do {j++;
        } while (q[j] >x);
        if (i< j) {swap(q[i], q[j]);
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main() {scanf("%d", &n);
    for (int i = 0; i< n; ++i) {scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);
    for (int i = 0; i< n; ++i) {printf("%d", n);
    }
    return 0;
}

归并排序—分治

步骤：

1. 确定分界点—中点
2. 递归排序左右两边
3. 将左右两个数组合并成一个有序的数组—归并 ⭐

#includeusing namespace std;
const int N = 1e6;
int n;
int arr1[N], temp[N];

void merge_sort(int arr[], int l, int r) {if (l >= r) return;
    int midNum = arr[l + (r - l) >>1];
    int k = 0, i = 0, j = 0;
    merge_sort(arr, l, midNum);
    merge_sort(arr, midNum + 1, r);
    while (i<= midNum && j<= r) {if (arr[i]<= arr[j]) temp[k ++] = arr[i ++];
        else temp[k ++] = arr[j ++];
    }
    while (i<= midNum) temp[k ++] = arr[i ++];
    while (j<= r) temp[k ++] = arr[j ++];
    for (int m = 0; m< n; ++m) {arr[m] = temp[m];
    }
}

int main() {//归并排序
    //1.选择中点作为分界
    //2.对左右两边不断进行递归
    //3.声明i，j两个指针进行比较，放入到中间数数组中；
    //当其中一个指针到达结尾时，另一个数据全部接入中间数据
    //4.将中间数组复制到原数组中结束
    scanf("%d", &n);
    for (int i = 0; i< n; ++i) {scanf("%d", &arr1[i]);
    }
    merge_sort(arr1, 0, n - 1);
    for (int i = 0; i< n; ++i) {printf("%d", arr1[i]);
    }
    return 0;
};

---

二分

二分的本质并不是单调性，通过二分保证答案在区间内

整数二分

步骤：

针对有序数组

1. 找出中间值
2. 判断中间值是否为真，根据情况更新区间 注意是否需要+1 处理边界问题

#include//using namespace std;
//const int N = 100000;
//int n,m;
//int q[N];
using namespace std;

int main() {//scanf("%d%d",&n,&m);
    //读入从n个数的数组中读取m的开始位置和结束位置
    int n = 6, m = 3;
    bool flag = true;
    int q[6] = {1, 2, 3, 3, 3, 6};
    while (flag) {int l = 0, r = n - 1;
        while (l< r) {int midNum = l + r >>1;
            if (q[midNum] >= m) {r = midNum;
            } else {l = midNum + 1;
            }
        }
        if (q[l] != m) {cout<< "-1 -1"<< endl;
            flag = false;
        } else {cout<< l<< " ";
            l = 0, r = n - 1;
            while (l< r) {int midNum = l + r + 1 >>1;
                if (q[midNum]<= m) {l = midNum;
                } else {r = midNum - 1;
                }
            }
            cout<< l<< endl;
            flag = false;
        }
    }
    return 0;
}

浮点数二分

不用考虑边界问题

#includeusing namespace std;

int main(){int n;
    scanf("%d",&n);
    double l = 0, r = n;
    double minigap = 1e-8;
    while ((r - l) >minigap) {double midnum = (l + r) / 2;
        if ((midnum * midnum)<= n) l = midnum;
        else r = midnum;
    }
    if (1) cout<< 0<< endl;
    printf("%f", l);

    return 0;
};

---

高精度

C++中存在的问题

• 大整数的存储问题，是将数据存储到数组中，从索引0开始到最后，分别存储个位、十位、百位…最高位，因为运算过程中可能存在进位问题，数组在尾部加数据更加方便。

A + B 类型

#include#includeusing namespace std;
int N = 100000 + 10;

vectoraddbignum (vector&A, vector&B){int t = 0;
    vectorC;
    for (int i = 0; i< A.size()|| i< B.size(); ++i) {if (i< A.size()) t += A[i];
        if (i< B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    return C;
}

int main(){//高精度大整数相加
    //1.先将两个大整数倒叙写入到各自的vector集合(头文件需要定义)中
    //2.调用自定义的add函数实现相加和进位，最终以集合返回
    //3.倒叙遍历输出最终结果

    //大整数用string
    string a = "12",b = "30";//例如a = 123456
    vectorA,B;//最为A,B的集合存放数据
    for (int i = a.size() - 1; i >= 0; --i) {A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; --i) {B.push_back(b[i] - '0');
    }
    vectorC = addbignum(A, B);
    for (int i = C.size() - 1 ; i >= 0; --i) {cout<< C[i];
    }
    return 0;
}

A - B 类型

#include#includeusing namespace std;

bool cmp(vector&A, vector&B) {
    //减法计算前需要判断AB的大小关系
    //分几种情况，AB长度相同，不相同
    if (A.size() != B.size()) return A.size() - B.size();
    else {
        for (int i = A.size() - 1; i >= 0; --i) {
            if (A[i] != B[i]) {
                return A[i] - B[i];
            }
        }
        return true;
    }
}

vectordec(vector&A, vector&B) {
    vectorC;//存放结果的数组
    int t = 0;
    for (int i = 0; i< A.size(); ++i) {
        t = A[i] - t;
        if (i< B.size()) t = t - B[i];
        C.push_back((t + 10) % 10);
        if (t< 0) t = 1;
        else t = 0;
    }
    while (C.size() >1 && C.back() == 0) C.pop_back();//解决输出结果为0009这些情况
    return C;
}

int main() {
    string a = "10", b = "1";//a,b两个大正整数
    vectorA, B;//集合AB存放数据
    for (int i = a.size() - 1; i >= 0; --i) {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; --i) {
        B.push_back(b[i] - '0');
    }
    vectorC;
    //首先需要判断AB谁大，是谁减谁
    if (cmp(A, B)) {
        //true 则A >= B
        C = dec(A, B);
        for (int i = C.size() - 1; i >= 0; --i) {
            printf("%d", C[i]);
        }
    } else {
        //B >A
        C = dec(B, A);
        cout<< '-';
        for (int i = C.size() - 1; i >= 0; --i) {
            printf("%d", C[i]);
        }
    }
    return 0;
}

A * a 类型

#include#includeusing namespace std;
vectormul(vector&A, int b) {
    vectorC;
    int t =0;
    for (int i = 0; i< A.size() || t; ++i) {
        if (i< A.size()) t = b * A[i] + t;
        C.push_back((t) % 10);
        t /= 10;
    }
    return C;
}
int main(){
    string a = "999";
    int b = 9;
    vectorA, C;
    for (int i = a.size() - 1; i >= 0; --i) {
        A.push_back(a[i] - '0');
    }
    C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; --i) {
        printf("%d",C[i]);
    }
    return 0;
}

A / a 类型

#include#include#include 

using namespace std;

vectordiv(vector&A, int b, int &r) {//余数通过引用&返回回去
    vectorC;
    for (int i = A.size() - 1; i >= 0; --i) {r = r * 10 + A[i];
        C.push_back(r / b);
        r = r % b;
    }
    reverse(C.begin(), C.end());//得反转以下，否则输出不一致
    while (C.size() >1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {string a = "1247";
    int b = 4, r = 0;
    vectorA, C;
    for (int i = a.size() - 1; i >= 0; --i) {A.push_back(a[i] - '0');
    }
    C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; --i) {printf("%d", C[i]);
    }
    cout<< endl<< r<< endl;
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：数据结构和算法视频学习-创新互联
文章链接：http://kswjz.com/article/icdge.html