算法笔记

学习一些入门算法应该不会很难吧，哈哈(C++)

快排

假设q[n]是一个整数数组需要排序

void quicksort(int q[],int l,int r)
{
    ​ if (l >= r) return;
    ​ int mid = q[l];
    ​ int i = l - 1, j = r + 1;
    ​ while (l < r)
    {
        ​ do { i++; }
        ​ while (q[i] < mid);
        ​ do { j++; }
        ​ while (q[j] > mid);
        ​ if (i < j) swap(q[i], q[j]);
    }
    ​ quicksort(q, l, j); //这时不能用i-1，因为最后不一定就是i>j也可能是i=j，就可能i-1会比l小
    ​ quicksort(q, j + 1, r); //
}

归并

​ 分两步：递归和合并

void merge(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge(q, l, mid);//一开始就要递归
    merge(q, mid + 1, r);
    for (int i = l; i <= r; i++)//把q数组l到r的内容复制到p
        p[i] = q[i];
    int i = l, j = mid + 1, x = l;
    while (i <= mid && j <= r)//进行合并，循环条件是两部分没有到端点
    {
        if (p[i] < p[j])//把的那个放入q中
            q[x++] = p[i++];
        else
            q[x++] = p[j++];
    }
    if (i <= mid)//如果一方没到终点则直接放到q后面
    {
        while (i <= mid)
            q[x++] = p[i++];
    }
    else
        while (j <= r)
            q[x++] = p[j++];
}

整数二分

1.从左往右逼近

解释：1 2 2 2 2 2 3，在这里面找2的话，二分肯定要取1到2，或者是2到3这个区间，但是不可能找到2到2这个区间，所以会失去一些数

int half(int q[], int l, int r, int x)
{ //找x
    int mid = l + r >> 1;
    while (l < r)
    {
        mid = l + r + 1 >> 1;
        if (q[mid] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    cout << r;
}

2.从右往左逼近

int half(int q[], int l, int r, int x)
{ //找x
    int mid ;
    while (l < r)
    {
        mid = l + r  >> 1;
        if (q[mid] >=x)
            r = mid;
        else
            l = mid+1;
    }
    cout << l;
}

Donate