数据结构学习笔记

#排序算法

排序算法总的来说有 *O(n2)** 和 *O(nlogn)*时间复杂度的两种解法。
**O(n2)*的代表:
- 选择排序
- 插入排序
**O(nlogn)**的代表:
- 归并排序
- 快速排序

#选择排序

时间复杂度为*O(n2)**，编码简单，易于实现。
从未排好序的元素中选出最小的元素加入到排好序的末尾。
简单实现:

1
2
3
4
5
6
7
8
9
10
11
template<typename T>
void selectionSort(T arr[], int n){
    for(int i = 0 ; i < n ; i ++){
        // 保存当前要选出的最小元素的位置
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;
        swap( arr[i] , arr[minIndex] );
    }
}

#插入排序

其中写法1和写法2相同。写法3的区别是使用赋值操作代替交换操作。
插入排序相对与选择排序的优点是可以提前结束内层循环，但是如果在数据量很大时，swap操作会消耗大量时间。
切记内层循环中不要使用swap。
即可以使用方法3进行优化。

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
template<typename T>
void insertionSort(T arr[], int n){

    for( int i = 1 ; i < n ; i ++ ) {

        // 寻找元素arr[i]合适的插入位置
        // 写法1
        for( int j = i ; j > 0 ; j-- )
            if( arr[j] < arr[j-1] )
                swap( arr[j] , arr[j-1] );
            else
                break;

        // 写法2
        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
            swap( arr[j] , arr[j-1] );
        
        // 写法3
        T e = arr[i];
        int j; // j保存元素e应该插入的位置
        for (j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }

    return;
}
int main() {

    int n = 20000;
    
    // 测试1 一般测试
    cout<<"Test for random array,size = "<<n<<", random range [0, "<<n<<"]"<<endl;
    int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
    int *arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
    SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);

    delete[] arr1;
    delete[] arr2;

    cout<<endl;


    // 测试2 有序性更强的测试
    cout<<"Test for more ordered random array, size = "<<n<<", random range [0, 3]"<<endl;
    arr1 = SortTestHelper::generateRandomArray(n,0,3);
    arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
    SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);

    delete[] arr1;
    delete[] arr2;

    cout<<endl;


    // 测试3 测试近乎有序的数组
    int swapTimes = 100;
    cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl;
    arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
    arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
    SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);

    delete[] arr1;
    delete[] arr2;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
//内层循环使用赋值
Test for random array, size = 20000, random range [0, 20000]
Insertion Sort : 0.265907 s
Selection Sort : 0.411309 s

Test for more ordered random array, size = 20000, random range [0, 3]
Insertion Sort : 0.197426 s
Selection Sort : 0.43127 s

Test for nearly ordered array, size = 20000, swap time = 100
Insertion Sort : 0.004048 s
Selection Sort : 0.417837 s
1
2
3
4
5
6
7
8
9
10
11
12
//内层循环使用swap
Test for random array, size = 20000, random range [0, 20000]
Insertion Sort : 0.557159 s
Selection Sort : 0.414171 s

Test for more ordered random array, size = 20000, random range [0, 3]
Insertion Sort : 0.412834 s
Selection Sort : 0.430294 s

Test for nearly ordered array, size = 20000, swap time = 100
Insertion Sort : 0.008028 s
Selection Sort : 0.432235 s

可以看到即使有提前结束循环的加成，但是由于swap操作相当于3次赋值操作，即导致插入排序相对于选择排序并不存在优势。

#归并排序

归并排序的思想是首先将左边的数据和右边的数据分别排序，然后进行归并，在两边的数据进行排序的过程和这个过程一样分为两个部分然后进行排序和归并。这是一个递归的过程。归并的操作时选出两个部分小的加入到排好序的序列中。

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
template<typename  T>
void __merge(T arr[], int l, int mid, int r){

    
    T *aux = new T[r-l+1];
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid ){  // 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j-l]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i-l]; i ++;
        }
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i-l]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j-l]; j ++;
        }
    }
    delete[] aux;
}

// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
    // 处理递归到底的情况
    if( l >= r )
        return;
    // 否则进行一次归并排序
    int mid = (l+r)/2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
    __merge(arr, l, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n){

    __mergeSort( arr , 0 , n-1 );
}

1
2
3
4
5
6
7
8
//测试结果
Test for random array, size = 100000, random range [0, 100000]
Insertion Sort : 6.43724 s
Merge Sort : 0.031772 s

Test for nearly ordered array, size = 100000, swap time = 10
Insertion Sort : 0.002678 s
Merge Sort : 0.024516 s

#优化方法

  1. 判断arr[mid]和arr[mid]的大小，当arr[mid]<arr[mid+1]说明已经有序，不必进行merge。
    1
    2
    3
    4
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
    if(arr[mid]>arr[mid+1])
        __merge(arr, l, mid, r);
  2. 当有巨量数据时，不将数组分割成很小的部分，例如当数据近乎有序时，插入排序的时间复杂度会降低到O(n),可利用这一特点进行优化。
    1
    2
    3
    4
    if( r-l<=16 ){
        insertionSort(arr,l,r);
        return;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    // 使用1和2进行优化的结果
    Test for random array, size = 100000, random range [0, 100000]
    Insertion Sort : 6.94346 s
    Merge Sort : 0.020683 s

    Test for nearly ordered array, size = 100000, swap time = 10
    Insertion Sort : 0.003424 s
    Merge Sort : 0.00362 s

    #快速排序

#堆排序

#辅助函数

辅助函数用于生成随机序列和检测排序结果。

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
#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cassert>
#include <string>

using namespace std;


namespace SortTestHelper {

    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
    int *generateRandomArray(int n, int range_l, int range_r) {

        int *arr = new int[n];

        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (range_r - range_l + 1) + range_l;
        return arr;
    }

    // 生成一个近乎有序的数组
    // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
    // swapTimes定义了数组的无序程度:
    // swapTimes == 0 时, 数组完全有序
    // swapTimes 越大, 数组越趋向于无序
    int *generateNearlyOrderedArray(int n, int swapTimes){

        int *arr = new int[n];
        for(int i = 0 ; i < n ; i ++ )
            arr[i] = i;

        srand(time(NULL));
        for( int i = 0 ; i < swapTimes ; i ++ ){
            int posx = rand()%n;
            int posy = rand()%n;
            swap( arr[posx] , arr[posy] );
        }

        return arr;
    }

    // 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组
    int *copyIntArray(int a[], int n){

        int *arr = new int[n];
        //* 在VS中, copy函数被认为是不安全的, 请大家手动写一遍for循环:)
        copy(a, a+n, arr);
        return arr;
    }

    // 打印arr数组的所有内容
    template<typename T>
    void printArray(T arr[], int n) {

        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;

        return;
    }

    // 判断arr数组是否有序
    template<typename T>
    bool isSorted(T arr[], int n) {

        for (int i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1])
                return false;

        return true;
    }

    // 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间
    template<typename T>
    void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {

        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;

        assert(isSorted(arr, n));

        return;
    }

};

#查找算法

#二分查找法

  • 时间复杂度O(log(n))
  • 输入的数据必须有序
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
template<typename T>
int binarySearch(T arr[], int n, T target){

    // 在arr[l...r]之中查找target
    int l = 0, r = n-1;
    while(l <= r){
        //int mid = (l+r)/2;//这里有溢出的可能
        int mid = l + (r-l)/2;
        if(arr[mid] == target)
            return mid;
        if(arr[mid]< target)
            l = mid + 1;
        else
            r = mid - 1;
    }
    // while( l <= r ){
    //
    //     //int mid = (l + r)/2;
    //     // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
    //     int mid = l + (r-l)/2;
    //
    //     if( arr[mid] == target )
    //         return mid;
    //
    //     if( arr[mid] > target )
    //         r = mid - 1;
    //     else
    //         l = mid + 1;
    // }

    return -1;
}