算法学习(2):分治法(上)

二分法

1.算法设计

用一维数组S[]存储该有序序列,设变量low和high表示查找范围的下界和上界,middle表示查找范围的中间位置,x为特定的查找元素。

(1)初始化。令low=0,high=n-1。

(2)middle=(high-low)/2。

(3)判断low<=high是否成立,若成立,到第4步,否则算法结束。

(4)判断S[middle]与x的关系:若S[middle]>x,则x位于low~middle之间,令high=middle-1,;若S[middle]<x,则x位于middle~high之间,令low=middle+1;转第2步。若S[middle]==x,则搜索成功,退出。

2.图解

数据结构学习笔记已有整理,在此省略图解。

3.完整代码

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int M = 10000;

int x, n, i;

int s[M];

int BinarySearch(int n, int s[], int x)

{

    int low = 0;

    int high = n - 1;

    while (low <= high)

    {

        int middle = low +(high - low) / 2;

        if (x < s[middle])

            high = middle - 1;

        else if (x > s[middle])

            low = middle + 1;

        else

            return middle;

    }

    return -1;

}



int main()

{

    cout << "Please enter the number of these elements: ";

    cin >> n;

    cout << "Please enter the element: " << endl;

    for (i = 0; i < n; i++)

    {

        cout << "Element " << i+1 << ": ";

        cin >> s[i];

    }

    sort(s, s + n);

    cout << "After sorted: " << endl;

    for (i = 0; i < n; i++)

        cout << s[i] << " ";

    cout << endl;

    cout << "Please enter the element that you want to find: " << endl;

    cin >> x;

    int ans = BinarySearch(n, s, x);

    if (ans == -1)

        cout << "Sorry, we can not find it.\n";

    else

        cout << "The answer is " << ans+1 << ".\n";



    system("pause");

    return 0;

}

 

排序复杂度为O(nlogn),二分查找复杂度为O(logn)。

递归版:

int BinarySearch(int n, int s[], int x,int low, int high)

{

    if (low > high)

        return -1;

    int middle = (low + high) / 2;

    if (x == s[middle])

        return middle;

    else if (x > s[middle])

        return BinarySearch(n, s, x, middle + 1, high);

    else

        return BinarySearch(n, s, x, low, middle - 1);

}

 

此方法二分查找复杂度仍旧是O(logn)。

合并排序

1.算法原理

将一大组数据,采用分治策略,分成很多个小问题。由于给定的是一个无序的大序列,可以把待排序列分解成两个规模大致相等的子序列,如果排序还是比较困难,则将子序列继续分解成两个规模大致相等的子序列,直到每个子序列的元素个数为1。然后进行合并,合并成完整的有序序列。

2.算法设计

(1)分解:将待排序列分解成大小相等的两个子序列;

(2)治理:将两个子序列进行合并排序;

(3)合并:将排好序的有序子序列进行合并,得到最终的序列。

合并的策略:采用i,j,k三个标志位,以及一个名为B的辅助数组。i,j分别位于A数组的0和mid+1位置,k指向B的起始位。由于A数组的0~mid,mid+1~end均为已经排好序的子序列,所以开始比较A[i]和A[j]。若A[i]>A[j],则将A[j]的数字存入B[k],然后j++,k++;若A[i]<A[j],则将A[i]的数字存入B[k],然后i++,k++;若此时某个数组已经比较完,则直接将另一个数组依序存入B,然后把B重新一一赋值给A,完成对A的排序。

3.完整代码

void Merge(int A[], int low, int mid, int high)

{

    int *B = new int[high - low + 1];

    int i = low, j = mid + 1, k = 0;

    while (i <= mid && j <= high)

    {

        if (A[i] >= A[j])

            B[k++] = A[j++];

        else

            B[k++] = A[i++];

    }

    while (i <= mid)

        B[k++] = A[i++];//把剩下的元素复制到B中

    while (j <= high)

        B[k++] = A[j++];//把剩下的元素复制到B中

    for (i = low,k=0; i <= high; i++)

    {

        A[i] = B[k++];

    }

    delete[] B;

}

void MergeSort(int A[], int low, int high)

{

    if (low < high)

    {

        int mid = (low + high) / 2;//取中间点

        MergeSort(A, low, mid);//对A[low:mid]中的元素进行合并排序

        MergeSort(A, mid + 1, high);//对A[mid+1:high]中的元素进行合并排序

        Merge(A, low, mid, high);//合并

    }

}

 

4.复杂度分析

时间复杂度:

(1)分解:O(1);

(2)治理:2T(n/2);

(3)合并:O(n)。

总的来说,T(n)=O(nlogn)。

空间复杂度:O(logn)。

快速排序

1.算法原理

通过一组排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有数据都要笑,然后按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此使所有数据变成有序序列。

快速排序是不稳定的算法!

2.算法设计

(1)分解:先从数列中取出一个元素作为基准元素,以基准元素为准,将问题分解为两个子序列,使小于等于基准元素的子序列在左侧,大于基准元素的子序列在右侧。

(2)治理:对两个子序列进行快速排序。

(3)合并:将排好序的两个子序列合并在一起,得到原问题的解。由于排序是原地进行的,所以在排好序后,合并步骤无需做什么,序列就已经排好序了。

一般来说,基准元素的选取有以下几种方法:

(1)取第一个元素;

(2)取最后一个元素;

(3)取中间位置的元素;

(4)取第一个、最后一个、中间位置元素三者的中位数;

(5)去第一个和最后一个之间位置的随机数k(low<=k<=high),选取R[k]做基准元素。

这个算法的难点在于“划分”,也就是分解这个步骤。

我们编写划分函数对原序列进行分解,分解为两个子序列,以基准元素pivot为界,左侧子序列都比pivot小,右侧子序列逗比pivot大。先从右向左扫描,找到小于等于pivot的数后,执行R[i]与R[j]的交换,然后进行i++,也就是从左向右扫描,找到比基准元素大的数,执行R[i]与R[j]的交换,然后进行j++……如此交替进行,直到i=j的时候停止。

3.完整代码

int Partition(int r[], int low, int high)

{

    int i = low, j = high;

    int pivot = r[low];

    while (i < j)

    {

        //当r[j]>pivot的时候,就继续由右往左寻找小于的元素

        while (i<j && r[j]>pivot)

            j--;

        //跳出while循环说明找到了,再判断下i<j,然后交换i和j的元素,然后i++,再开始从左向右寻找r[i]>pivot的元素

        if (i<j)

            swap(r[i++], r[j]);

        //当r[i]<pivot的时候,就继续加i,直到找到r[i]>pivot的时候,跳出wile循环

        while (i < j && r[i] <= pivot)

            i++;

        //跳出while循环说明找到了,再判断下i<j,然后交换i和j的元素,然后j--,再开始从右向左寻找小于的元素

        if (i<j)

            swap(r[i], r[j--]);

    }

    return i;

}

void QuickSort(int R[], int low, int high)

{

    //先从一堆元素中找到一个基准元素,然后以这个基准元素为准,左侧都小于它,右侧都大于它。然后再对左侧和右侧分别进行快速排序。

    int mid;

    if (low < high)

    {

        mid = Partition(R, low, high);

        QuickSort(R, low, mid - 1);//左侧快速排序

        QuickSort(R, mid + 1, high);//右侧快速排序

    }

}

 

4.复杂度分析

1.时间复杂度分析

(1)最好时间复杂度

①分解:O(n);

②解决子问题:在最理想情况下,每次将问题划分为规模相当的两个子序列,也就是规模为n/2,即求解两个规模为n/2的子问题,所需时间为2T(n/2);

③合并:没有任何操作,不需要时间复杂度。

所以

经过递归求解(规模为1,令n=2x,则x=logn),所以T(n)=O(nlogn)

(2)最坏时间复杂度

①分解:O(n);

②解决子问题:在最坏情况下,基准元素的一侧无元素,另一次有1个规模为n-1的子问题,那么递归出来所需要的时间为T(n-1);

③合并:没有任何操作,不需要时间复杂度。

所以

所以T(n)=O(n2)

空间复杂度:O(n)

(3)平均时间复杂度:O(nlogn)

5.算法优化扩展

上述算法都是每次交换与基准元素进行交换,实际上没必要这样,我们的目的就是把原序列分为以基准元素为界的两个子序列,左侧子序列小于等于基准元素,右侧子序列大于基准元素。步骤如下:

步骤1:首先取数据第一个元素作为基准元素pivot=R[low]。i=low, j=high。

步骤2:从右向左扫描,找小于等于pivot的数R[j]。

步骤3:从左向右扫描,找大于pivot的数R[i]。

步骤4:R[i]和R[j]交换,然后i++, j–。

步骤5:重复步骤2~步骤4,直到i和j相等,如果R[i]大于pivot,则R[i-1]和基准元素R[low]交换,返回该位置mid=i-1;否则R[i]跟基准元素交换,返回该位置mid=i,该位置的数正好是基准元素。

至此完成一趟排序。此时以mid为界,左侧子序列均小于pivot,右侧子序列均大于pivot。

代码如下:

int Partition2(int r[],int low, int high)

{

    int i = low, j = high;

    int pivot = r[low];

    while (i < j)

    {

        while (i<j && r[j]>pivot)

            j--;

        while (i < j && r[i] <= pivot)

            i++;

        if (i < j)

        {

            swap(r[i++], r[j--]);

        }

    }

    if (r[i] > pivot)

    {

        swap(r[i - 1], r[low]);

        return i - 1;

    }

    swap(r[i], r[low]);

    return i;



}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注