机试第3章

快速排序(quicksort)

void quicksort(int *a, int l, int r)
{
    int mid = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j)
    {
        while (a[i] < mid)
            i++;
        while (a[j] > mid)
            j--;
        if (i <= j)
        {
            swap(a[i], a[j]);
            i++, j--;
        }
    }
    if (i < r)
        quicksort(a, i, r);
    if (l < j)
        quicksort(a, l, j);
}

结构体排序

struct student
{
    int x, y;
};

bool cmp(const student &a, const student &b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

二分查找

bool search(int *a, int n, int target)
{
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if (a[mid] < target)
            l = mid + 1;
        else if (a[mid] > target)
            r = mid - 1;
        else
            return true;
    }
    return false;
}

lower_bound(begin, end, val); // 返回大于等于val的地址
upper_bound(begin, end, val); // 返回大于val的地址