二分法

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.完整代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#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)。

递归版：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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.完整代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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.完整代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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。

代码如下：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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;
 
 
 
}