[数据结构与算法]数据结构复习

前言

临时抱佛脚…

二叉树

度数为0的结点(叶子) 数量比度数为2的结点数量多一个。
$$n_0=n_2+1$$

排序算法

完整代码请查看 排序类完整代码

冒泡排序

(1)基本思想: 从前往后(或从后往前)两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完

//升序
template<class T>
void LinearSort<T>::BubbleSort() {
    if (!array)
        return;
    bool exchange;
    int i, j;
    int count = 0;//统计排序趟数
    for (i = 0; i < currentSize; i++) {
        exchange = false;
        for (j = 0; j < currentSize - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(j, j + 1);
                exchange = true;
            }
        }
        count++;
        if (!exchange)
            break;
    }
    cout << "经过 " << count << "次BubbleSort排序获得有序序列" << endl;
}

(2) 时间效率:

• 平均 $O(n^2)$
• 最坏 $O(n^2)$
• 最好 $O(n)$ , 但通常这个指标没什么意义

(3) 空间复杂度 $O(1)$
(4) 稳定性: 稳定

快速排序

基本思想: 在待排序表中任取一个元素pivot作为枢轴, 通过一趟排序将排序表分成两个部分 1…k-1, k + 1…n
，使得前者所有的元素小于pivot, 后者所有元素都大于pivot, 最终pivot放到该线性表下标为k的位置上。

template<class T>
void LinearSort<T>::QuickSort() {
    QuickSort(0, currentSize - 1);
}

template<class T>
int LinearSort<T>::QuickPass(int low, int high) {
    int down = low;
    int up = high;
    array[currentSize] = array[down];
    //此时array[down]空出来了
    while (down < up) {
        while (down < up && array[up] > array[currentSize])
            up--;       //从右边找到第一个比基准值array[down]小的就停下来
        if (down < up)
            array[down++] = array[up];
        //此时array[up]空出来了
        while (down < up && array[down] <= array[currentSize])
            down++;
        if (down < up)
            array[up--] = array[down];
        //此时array[down]空出来了
    }
    //此时down与up相遇了
    array[down] = array[currentSize];
    return down;//此时return的是一次操作基准值放的位置
}

template<class T>
void LinearSort<T>::QuickSort(int low, int high) {
    //这里判断只是为了排除没有数组的情况
    //实际上写快排算法不用的
    if (!array)
        return;
    if (low < high) {
        int mid = QuickPass(low, high);
        QuickSort(low, mid - 1);
        QuickSort(mid + 1, high);
    }
}

这里也给出非递归写法

struct quNode {
    int low;
    int high;
};

template<class T>
void LinearSort<T>::QuickSortByQueueNonRecursion() {
    int mid; //mid为一趟快速排序后，基准记录所在位置指示器

    quNode xNode, yNode;
    queue<quNode> qu;

    xNode.low = 0;
    xNode.high = currentSize - 1;
    qu.push(xNode);

    while (!qu.empty()) {
        xNode = qu.front();
        qu.pop();
        mid = QuickPass(xNode.low, xNode.high);
        if (xNode.low < mid - 1) { //当左侧序列大于1则排序
            yNode.low = xNode.low;
            yNode.high = mid - 1;
            qu.push(yNode);
        }
        if (xNode.high > mid + 1) {//当右侧序列大于1则排序
            yNode.low = mid + 1;
            yNode.high = xNode.high;
            qu.push(yNode);
        }
    }
}

struct stNode {
    int low;
    int high;
};

template<class T>
void LinearSort<T>::QuickSortByStackNonRecursion() {
    int mid;

    stNode xNode, yNode;
    stack<stNode> st;

    xNode.low = 0;
    xNode.high = currentSize - 1;
    st.push(xNode);
    while(!st.empty()){
        xNode = st.top();
        st.pop();
        mid = QuickPass(xNode.low, xNode.high);
        if(xNode.low < mid - 1){ //当左侧序列大于1则排序
            yNode.low = xNode.low;
            yNode.high = mid - 1;
            st.push(yNode);
        }
        if(xNode.high > mid + 1){//当右侧序列大于1则排序
            yNode.low = mid + 1;
            yNode.high = xNode.high;
            st.push(yNode);
        }
    }
}

(2) 时间复杂度:

• 平均 $O(nlo{g}_{2}n)$
• 最坏 $O(n^2)$
  (3) 空间复杂度: 平均$O(lo{g}_{2}n)$
  (4) 稳定性: 不稳定

(简单)选择排序

(1) 基本思想
摘选自王道考研数据结构考研复习指导P313
假设排序表为L[1…n], 第i趟排序即从L[i…n]中选择关键字最小的元素与L[i]交换，每一趟排序可以确定一个元素的最终位置。

template<class T>
void LinearSort<T>::SelectSort() {
    int i, j, pos;
    for (i = 0; i < currentSize; i++) {
        pos = i;
        //前i个单元已经有序
        for (j = i + 1; j < currentSize; j++) {
            if (array[j] < array[pos])
                pos = j;
        }
        if (pos != j) {
            swap(i, pos);
        }
    }
}

(2) 时间复杂度：平均情况$O(n^2)$
(3) 空间复杂度: 平均情况$O(1)$
(4) 稳定性: 不稳定。
关于简单选择排序的优化有 锦标赛排序算法，它保留了一些比较信息，从而减少了重复比较的次数。

堆排序

(1) 基本思想: 可以借助一个大根堆或者小根堆，然后从堆中取出元素一次放入表中即可。

template<class T>
void LinearSort<T>::HeapSort() {
    MinHeap<T> hp(array, currentSize);
    for (int i = 0; i < currentSize; i++) {
        hp.RemoveMin(array[i]);
    }
}

关于堆的实现可看这篇: 最小堆c++实现
(2) 时间复杂度: 平均情况 $O(nlo{g}_{2}n)$
(3) 空间复杂度：$O(1)$
(4) 稳定性: 不稳定

归并排序

(1)基本思想: 先拆分，再两两合并

template<class T>
void LinearSort<T>::MergeSort() {
    MergeSort(0, currentSize - 1);
}

template<class T>
void LinearSort<T>::MergeSort(int left, int right) {
    if (left == right)
        return;
    int mid = (left + right) / 2;
    MergeSort(left, mid);
    MergeSort(mid + 1, right);
    Merge(left, mid, right);
}

template<class T>
void LinearSort<T>::Merge(int l, int m, int r) {
    int n = r - l + 1, i = 0;
    T *temp = new T[n];
    int left = l;
    int right = m + 1;
    while (left <= m && right <= r) {
        if (array[left] <= array[right])
            temp[i++] = array[left++];
        else
            temp[i++] = array[right++];
    }
    while (left <= m) {
        temp[i++] = array[left++];
    }
    while (right <= r) {
        temp[i++] = array[right++];
    }
    for (i = 0; i < n; i++)
        array[l + i] = temp[i];
    delete[] temp;
}

(2) 时间复杂度: $O(nlo{g}_{2}n)$
(3) 空间复杂度: $O(n)$
(4) 稳定性: 稳定

基数排序

(1) 基本思想：不急于比较和移动进行排序, 而基于关键字各位的大小。

//digit为最高位，example：999 --> digit=3
template<class T>
void LinearSort<T>::MSDSort(int digits) {
    queue<T> bucket[10];
    //当然也可以合并到上面，不过这里为了直观
    //就单独拿出来了，取名为line
    queue<T> line;
    int weight, i;
    T bucketNum, data;

    for (i = 0; i < currentSize; i++) {
        line.push(array[i]);
    }

    for (int times = 1; times <= digits; times++) {
        //求比该位大一位数的权值
        weight = 1;
        for (i = 1; i < times; i++)
            weight = 10 * weight;

        while (!line.empty()) {
            data = line.front();
            line.pop();
            bucketNum = (data / weight) % 10;
            bucket[bucketNum].push(data);
        }
        cout << "第 " << times << "次: ";
        for (i = 0; i < 10; i++) {
            while (!bucket[i].empty()) {
                data = bucket[i].front();
                cout << data << " ";
                bucket[i].pop();
                line.push(data);
            }
        }
        cout << endl;
    }

    cout << "最终结果: " << endl;
    i = 0;
    while (!line.empty()) {
        data = line.front();
        line.pop();
        cout << data << " ";
        array[i++] = data;
    }
    cout << endl;
}

(2) 时间复杂度: $O(d(n+r))$, d是趟数，即d个关键字，r是队列数
(3) 空间复杂度: $O(r)$, r个队列
(4) 稳定性: 稳定

直接插入排序

(1) 基本思想：将整个数组a分为有序和无序的两个部分。开始有序的部分只有a[0] , 其余都属于无序的部分。每次取出无序部分的第一个（最左边）元素，把它加入有序部分。假设插入合适的位置p，则原p位置及其后面的有序部分元素都向右移动一个位置，有序的部分即增加了一个元素。一直做下去，直到无序的部分没有元素。
(该段文字来自插入排序算法思想, 感觉这位博主表达得很清楚，就不自己码字了)

template<class T>
void LinearSort<T>::InsertSort() {
    if (!array)
        return;
    int i, j;
    //多开了一个空间，放在了array[currentSize]
    for (int i = 1; i < currentSize; i++) {
        array[currentSize] = array[i];
        j = i - 1;
        while (array[currentSize] < array[j] && j >= 0) {
            //如果array[0]是多开的浪费空间的话可以把它考虑为哨兵,
            //这样就不用判断j >= 0
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = array[currentSize];
    }
}

(2) 时间复杂度: $O(n^2)$
(3) 空间复杂度: $O(1)$
(4) 稳定性: 稳定

希尔排序

(1) 基本思想: 直接插入排序可能插入后需要移动很多单元。因此希尔排序觉得不如减少元素移动的次数，即移动步伐大一些。这里在此借鉴一下其他博主的 希尔排序的基本思想:
将数组序列从大化中，中化小的一种排序方式，每一个化简的过程也是利用了直接插入排序，将数组基本排序，对于基本排序也就是大致有一个从小到大的顺序，在对这个基本的序列进行排序，在基本的序列里有的序列可能已经按照顺序排好，所以会省去一些步骤，以此来对排序算法进行优化。

template<class T>
void LinearSort<T>::ShellSort() {
    int i, j, gap;
    gap = currentSize / 2;
    while (gap >= 1) {
        for (i = gap; i < currentSize; i++) {
            array[currentSize] = array[i]; //array[currentSize]为浪费的空间
            j = i - gap;
            while (array[currentSize] < array[j] && j >= 0) {
                array[j + gap] = array[j];
                j = j - gap;
            }
            array[j + gap] = array[currentSize];
        }
//        cout << "array: ";
//        printArray();
        gap = gap / 2;
    }
}

(2) 时间复杂度: $O(nlo{g}_{2}n)$ ~ $O(n^2)$
(3) 空间复杂度: $O(1)$
(4) 稳定性: 不稳定