数据结构笔记

冒泡排序的数组和向量实现

void bubblesortA(int* A, int n) {
    bool sorted = false;
    while (!sorted)
    {
        sorted = true;
        for (int i = 1; i < n; i++) {
            if (A[i - 1] > A[i]) {
                swap(A[i - 1], A[i]);
                sorted = false;
            }
        }
        n--;
    }
}
void bubblesortB(vector<int> *B) {
    bool sorted = false;
    int n = B->size();
    while (!sorted)
    {
        sorted = true;
        for (int i = 1; i < n; i++) {
            if ((*B)[i - 1] > (*B)[i]) {
                swap((*B)[i - 1], (*B)[i]);
                sorted = false;
            }
        }
        n--;
    }
}

 向量唯一化实现

template <typename T>
int Vector<T>::deduplicate() {
    int oldSize = _size;
    Rank i = 1;
    while (i < _size)
        (find(_elem[i], 0, i) < 0) ? i++ : remove(i);
    return oldSize - _size;
}

 向量-归并排序

template <typename T>
void Vector<T>::mergeSort(int lo, int hi) {
    if (hi - lo < 2)
        return;
    int mi = (hi + lo) >> 1;
    mergeSort(lo, mi);
    mergeSort(mi, hi);
    merge(lo, mi, hi);
}
template <typename T>
void Vector<T>::merge(int lo, int mi, int hi) {
    T* A = _elem + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    for (int i = 0; i < lb; B[i] = A[i++]);
    int lc = hi - mi;
    T* C = _elem + mi;
    for (int i = 0, j = 0, k = 0; (j < lb) || (k < lc);) {
        if ((j < lb) && (!(k < lc) || (B[j] <= C[k])))
            A[i++] = B[j++];
        if ((k < lc) && (!(j < lb) || (C[k] < B[j])))
            A[i++] = C[k++];
    }
    delete[] B;
}