分治策略 #结点 #快排 #递归 #二分查找 #数据

二分查找

循环二分查找

int BinaryFindValue(const int* ar, int n, int val)//循环的二分查询
{
    assert(ar != NULL); // NULL  nullptr;
    int pos = -1;
    int left = 0, right = n - 1;
    while (left <= right) // left < right
    {
        //int mid = (right + left) / 2;//可能左右相加超出整形数组的范围，
        int mid = (right - left) / 2 + left;//
        if (val < ar[mid]) 
        {
            right = mid - 1;
        }
        else if (val > ar[mid])
        {
            left = mid + 1;
        }
        else
        {
            while (mid > left && ar[mid - 1] == val)
            {
                mid = mid - 1;
            }
            pos = mid;
            break;
        }
    }
    return pos;
}
int main()
{
    int ar[] = { 12,23,34,45,56,67,78,89,90,100 };
    int n = sizeof(ar) / sizeof(ar[0]);
    int val;
    cin >> val;
    int pos = BinaryFindValue(ar, n, val);//二分查询
    cout << pos << endl;

    return 0;
}

递归二分查找

int FindValue(const int* ar, int left, int right, int val)
{
    int pos = -1;
    if (left <= right)
    {
        int mid = (right - left) / 2 + left;
        if (val < ar[mid])
        {
            pos = FindValue(ar, left, mid - 1, val);
        }
        else if (val > ar[mid])
        {
            pos = FindValue(ar, mid + 1, right, val);
        }
        else
        {
            pos = mid;
        }
    }
    return pos;
}
//递归的二分查询
int BinFindValue(const int* ar, int n, int val)
{
    assert(ar != nullptr);
    return FindValue(ar, 0, n - 1, val);
}

int main()
{
    int ar[] = { 12,23,34,45,56,67,78,89,90,100 };
    int n = sizeof(ar) / sizeof(ar[0]);
    int val;
    cin >> val;
    pos = BinFindValue(ar, n, val);//递归的二分查询
    cout << pos << endl;

    return 0;
}

快速排序法

递归

void Print_Ar(int* ar, int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%4d ", ar[i]);
    }
    printf("\n");
}
int Parition(int* ar, int left, int right)
{
    int tmp = ar[left];
    while (left < right)
    {
        while (left < right && tmp < ar[right]) --right;
        if (left < right) ar[left] = ar[right];
        while (left < right && ar[left] <= tmp) ++left;
        if (left < right) ar[right] = ar[left];
    }
    ar[left] = tmp;
    return left;
}
void QuickPass(int* ar, int left, int right)//快速排序
{
    if (left < right)
    {
        int pos = OneParition(ar, left, right);
        QuickPass(ar, left, pos - 1);
        QuickPass(ar, pos + 1, right);
    }
}
void QuickSort(int* ar, int n)//快排
{
    assert(ar != NULL);
    QuickPass(ar, 0, n - 1);
}
int main()
{
    int ar[] = { 56,23,34,89,90,12,78,45,56,100,67 };
    int n = sizeof(ar) / sizeof(ar[0]);

    Print_Ar(ar, n);
    QuickSort(ar, n);
    Print_Ar(ar, n);
    return 0;
}

栈、

void NiceQuickSort(int* ar, int n)
{
    assert(ar != nullptr);
    stack<int> ist;
    ist.push(0);
    ist.push(n - 1);
    while (!ist.empty())
    {
        int right = ist.top(); ist.pop();
        int left = ist.top(); ist.pop();
        int pos = Parition(ar, left, right);

        if (left < pos - 1)
        {
            ist.push(left);
            ist.push(pos - 1);
        }
        if (pos + 1 < right)
        {
            ist.push(pos + 1);
            ist.push(right);
        }
    }
}

队列

void NiceQuickSort(int* ar, int n)
{
    assert(ar != nullptr);
    queue<int>  ist;
    ist.push(0);
    ist.push(n - 1);
    while (!ist.empty())
    {
        int left = ist.front(); ist.pop();
        int right = ist.front(); ist.pop();

        int pos = Parition(ar, left, right);

        if (left < pos - 1)
        {
            ist.push(left);
            ist.push(pos - 1);
        }
        if (pos + 1 < right)
        {
            ist.push(pos + 1);
            ist.push(right);
        }
    }
}

队的另一种方法：

void NiceQuickSort(int* ar, int n)
{
    assert(ar != nullptr);
    queue<std::pair<int, int> > ist;//pair 一对  有first,second

    std::pair<int, int> LR(0, n - 1);
    ist.push(LR);
    while (!ist.empty())
    {
        std::pair<int, int> LR = ist.front(); ist.pop();

        int pos = RandParition(ar, LR.first, LR.second);

        if (LR.first < pos - 1)
        {
            ist.push(pair<int, int>(LR.first, pos - 1));
        }
        if (pos + 1 < LR.second)
        {
            ist.push(pair<int, int>(pos + 1, LR.second));
        }
    }
}

若数据本来有序，（若从第一个开始划分，变成冒泡排序）

使用随机法

int Parition(int* ar, int left, int right)
{
    int tmp = ar[left];
    while (left < right)
    {
        while (left < right && tmp < ar[right]) --right;
        if (left < right) ar[left] = ar[right];
        while (left < right && ar[left] <= tmp) ++left;
        if (left < right) ar[right] = ar[left];
    }
    ar[left] = tmp;
    return left;
}
int RandParition(int* ar, int left, int right)
{
    assert(ar != nullptr);
    int index = rand() % (right - left + 1) + left;
    //模值加left,模值得到的是第几位，而不是物理下标，加left得到那一位的物理下标
    std::swap(ar[index], ar[left]);
    return Parition(ar, left, right);
}

适合单链表的：冒泡，选择

int OneParition(int* ar, int left, int right)
{
    int i = left, j = left - 1;
    int tmp = ar[i];
    while (i <= right)
    {
        if (ar[i] <= tmp)
        {
            j = j + 1;
            std::swap(ar[i], ar[j]);
        }
        ++i;
    }
    std::swap(ar[left], ar[j]);
    return j;
}

单链表的快排

含头结点的快排：

typedef int ElemType;
typedef struct ListNode
{
    ElemType data;
    struct ListNode* next;
}ListNode, * LinkList;

struct ListNode* Buynode()
{
    struct ListNode* s = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (NULL == s) exit(1);
    memset(s, 0, sizeof(struct ListNode));
    return s;
}
struct ListNode* InitList()
{
    struct ListNode* s = Buynode();
    return s;
}
void Push_Front(LinkList phead, ElemType val)
{
    ListNode* s = Buynode();
    s->data = val;
    s->next = phead->next;
    phead->next = s;
}
void PrintList(LinkList phead)
{
    ListNode* p = phead->next;
    while (p != nullptr)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
ListNode* Parition(ListNode* first, ListNode* end)
{
    ListNode* jp = first;
    ListNode* ip = first->next;//ip指向第一个数据的结点
    int tmp = ip->data;
    while (ip != end)
    {
        if (ip->data <= tmp)
        {
            jp = jp->next;
            std::swap(jp->data, ip->data);//交换函数
        }
        ip = ip->next;
    }
    std::swap(first->data, jp->data);//退出后第一个与jp指向的交换
    return jp;
}

void QuickPass(ListNode* first, ListNode* end)
{
    if (first != end)//first指第一个结点，end指向的是空
    { 
        ListNode* pos = Parition(first, end);
        QuickPass(first, pos);
        QuickPass(pos, end);
    }
}
void QuickSort(ListNode head)
{
    assert(head != nullptr);
    QuickPass(head, NULL);
}
int main()
{
    int ar[] = { 56,23,34,89,90,12,78,45,100,67 };
    int n = sizeof(ar) / sizeof(ar[0]);
    LinkList head = InitList();
    for (int i = n - 1; i >= 0; --i)
    {
       Push_Front(head, ar[i]);
    }

    PrintList(head);
    QuickSort(head);
    PrintList(head);
    return 0;
}

不含头结点的快排：

typedef int ElemType;
typedef struct ListNode
{
    ElemType data;
    struct ListNode* next;
}ListNode, * LinkList;

struct ListNode* Buynode()
{
    struct ListNode* s = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (NULL == s) exit(1);
    memset(s, 0, sizeof(struct ListNode));
    return s;
}
struct ListNode* InitList()
{
    struct ListNode* s = Buynode();
    return s;
}
ListNode* Push_Front(LinkList phead, ElemType val)
{
    if (phead == nullptr)
    {
        ListNode* s = Buynode();
        s->data = val;
        s->next = nullptr;
        return s;
    }
    ListNode* s = Buynode();
    s->data = val;
    s->next = phead;
    phead = s;
    return phead;
}
void PrintList(LinkList phead)
{
    ListNode* p = phead;
    while (p != nullptr)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
ListNode* Parition(ListNode* first, ListNode* end)
{
    ListNode* jp = first;
    ListNode* ip = first->next;//ip指向第一个数据的结点
    int tmp = jp->data;
    while (ip != end)
    {
        if (ip->data <= tmp)
        {
            jp = jp->next;
            std::swap(jp->data, ip->data);//交换函数
        }
        ip = ip->next;
    }
    std::swap(first->data, jp->data);//退出后第一个与jp指向的交换
    return jp;
}

void QuickPass(ListNode* first, ListNode* end)
{
    if (first != end)//first指第一个结点，end指向的是空
    { 
        ListNode* pos = Parition(first, end);
        QuickPass(first, pos);
        QuickPass(pos->next, end);
    }
}
void QuickSort(ListNode* phead)
{
    assert(phead != nullptr);
    QuickPass(phead, NULL);
}
int main()
{
    int ar[] = { 56,23,34,89,90,12,78,45,100,67 };
    int n = sizeof(ar) / sizeof(ar[0]);
    LinkList head = nullptr;
    for (int i = n - 1; i >= 0; --i)
    {
        head = Push_Front(head, ar[i]);
    }

    PrintList(head);
    QuickSort(head);
    PrintList(head);
    return 0;
}

寻找第k小的值：

int Parition(int* ar, int left, int right)
{
    int tmp = ar[left];
    while (left < right)
    {
        while (left < right && tmp < ar[right]) --right;
        if (left < right) ar[left] = ar[right];
        while (left < right && ar[left] <= tmp) ++left;
        if (left < right) ar[right] = ar[left];
    }
    ar[left] = tmp;
    return left;
}
int SelectK(int* ar, int left, int right, int k)
{
    if (left == right && k == 1) return ar[left];//此时下标只有一个值
    int pos = Parition(ar, left, right);
    int j = pos - left + 1;
    if (k <= j) return SelectK(ar, left, pos, k);
    else return SelectK(ar, pos + 1, right, k - j);
}
int Select_K_Min(int* ar, int n, int k)//找第k小
{
    assert(ar != NULL && k >= 1 && k <= n);
    return SelectK(ar, 0, n - 1, k);
}
int main()
{
    int ar[] = { 56,23,34,89,90,12,78,45,100,67 };
    int n = sizeof(ar) / sizeof(ar[0]);

    for (int k = 1; k <= n; ++k)
    {
        printf("%d => %d \n", k, Select_K_Min(ar, n, k));
    }

    return 0;

}

分治算法

int Parition(int* ar, int left, int right)
{
    int tmp = ar[left];
    while (left < right)
    {
        while (left < right && tmp < ar[right]) --right;
        if (left < right) ar[left] = ar[right];
        while (left < right && ar[left] <= tmp) ++left;
        if (left < right) ar[right] = ar[left];
    }
    ar[left] = tmp;
    return left;
}
int SelectK(int* ar, int left, int right, int k)
{
    if (left == right && k == 1) return ar[left];//此时下标只有一个值
    int pos = Parition(ar, left, right);
    int j = pos - left + 1;//pos-left指物理下标，实第几小时应加1
    if (k <= j) return SelectK(ar, left, pos, k);
    else return SelectK(ar, pos + 1, right, k - j);
}
int Select_K_Min(int* ar, int n, int k)//找第k小
{
    assert(ar != NULL && k >= 1 && k <= n);
    return SelectK(ar, 0, n - 1, k);
}

int MaxS1(int* ar, int left, int right)
{
    return ar[right];
}
int MinS2(int* ar, int left, int right)//物理区域找最小值
{
    int min = ar[left];
    for (int i = left + 1; i <= right; ++i)
    {
        if (min > ar[i])
        {
            min = ar[i];
        }
    }
    return min;
}
int Min(int a, int b)
{
    return a < b ? a : b;
}
int Min3(int a, int b, int c)//三个数比较最小值
{
    return Min(Min(a, b), c);
}
int Capir(int* ar, int left, int right)
{if (right - left <= 1) 
    {
        return INT_MAX;
    }
    int k = (right - left + 1) / 2;
    SelectK(ar, left, right, k);
    int pos = k + left - 1;//物理下标


    //此时是物理下标
    int d1 = Capir(ar, left, pos);     //s1;
    int d2 = Capir(ar, pos + 1, right); //s2;
    int p = MaxS1(ar, left, pos); //s1;
    int q = MinS2(ar, pos + 1, right);return Min3(d1, d2, d3);
}
int main()
{
    int ar[] = { 56,23,34,89,92,12,78,45,100,67,55 };
    int n = sizeof(ar) / sizeof(ar[0]);

    int dist= Capir(ar, 0, n - 1);
    printf("%d \n",dist);
    return 0;
}

分治策略

循环二分查找

递归二分查找

递归

栈、

队列

队的另一种方法：

单链表的快排

含头结点的快排：

不含头结点的快排：

寻找第k小的值：

继续阅读

线程通信和进程通信区别（线程进程区别）

Matlab随机波动率SV、GARCH用MCMC马尔可夫链蒙特卡罗方法分析汇率时间序列

微信小程序前端解密获取用户信息

Spring MVC 自学杂记（五） -- SpringMVC与前台的json数据交互

《MySQL技术内幕：InnoDB存储引擎》笔记

扩容TIKV节点遇到的坑

PHP辅导代做编程：CS353 Database System

自学Zabbix3.10.2-事件通知Notifications upon events-Actions报警配置点击返回：自学zabbix集锦

HDU 5678 ztr loves trees

拓端tecdat|R语言弹性网络Elastic Net正则化惩罚回归模型交叉验证可视化

二叉树及其应用--二叉树创建

UVA 110 Meta-Loopless Sorts

UVA 620 Cellular Structure

经典查找算法之二分查找

查找算法之二分查找查找算法之二分查找

详解STM32单片机的堆栈