Sort

Sort: 排序。

排序是一个很重要的算法。

常见的排序算法有：（后面是它们的时间复杂度）

1. 冒泡排序 O(n²
2. 插入排序 O(n²
3. 选择排序 O(n²
4. 希尔排序 O(n^2/3
5. 堆排序 O(nlogn)
6. 归并排序 O(nlogn)
7. 快速排序 O(nlogn)

下面介绍冒泡排序、插入排序、归并排序、快速排序

首先假设我们有一些数：
std::vector<int> vec = {1, 0, 0, 3, 5, 7, 9, 2, 4, 6, 8, 10};

冒泡排序

从左至右两两比较，把最大的往后移。

void Sort::BubbleSort(std::vector<int> &array) {
    const int N = array.size();
    if (N <= 1) {
        return;
    }
    for (int i = 0; (i < N - 1); i++) {
        bool ok = true;
        for (int j = 0; (j < N - i - 1); j++) {
            if (array[j] > array[j + 1]) {
                std::swap(array[j], array[j + 1]);
                ok = false;
            }
        }
        if (ok) {
            break;
        }
    }
}

插入排序

从左至右，遍历一个数i，将i插入到前面已经排序好的数中。

void Sort::InsertionSort(std::vector<int> &array) {
    insertionSortPart(array, 0, array.size() - 1);
}

void Sort::insertionSortPart(std::vector<int> &array, int low, int high) {
    const int N = high - low + 1;
    if (N <= 1) {
        return;
    }

    for (int i = low + 1; i <= high; i++) {
        int value = array[i];

        int j = i;
        for (; j > 0 && (array[j - 1] > value); j--) {
            std::swap(array[j], array[j - 1]);
        }
    }
}

这里分开始实现是因为快速排序还会用的插入排序。

归并排序

将待排序的数，分成左右两半，分别将它们排序，然后将左右个有序表再合并成一个有序表。

void Sort::MergeSort(std::vector<int> &array) {
    const int N = array.size();
    if (N <= 1) {
        return;
    }
    msort_merge(array, 0, N - 1);
}

void Sort::msort_merge(std::vector<int> &array, int left, int right) {
    if (right <= left) {
        return;
    }

    int mid = left + (right - left) / 2;

    msort_merge(array, left, mid);
    msort_merge(array, mid + 1, right);

    std::vector<int> cache;

    int j = left;
    int k = mid + 1;

    while ((j <= mid) && (k <= right)) {    // merge two sub arrays
        if (array[j] <= array[k]) {
            cache.push_back(array[j]);
            j++;
        } else {
            cache.push_back(array[k]);
            k++;
        }
    }
    while (j <= mid) {
        cache.push_back(array[j++]);
    }
    while (k <= right) {
        cache.push_back(array[k++]);
    }

    std::copy(cache.begin(), cache.end(), array.begin() + left);
}

时间复杂度O(nlogn)，空间复杂度为O(n)

快速排序

将带排序的数分成两个部分，其中一部分的值都小于另一部分。

选定一个枢轴(pivot），让它左边的数独小于它，右边的数都大于它。

void Sort::QuickSort(std::vector<int> &array) {
    const int N = array.size();
    if (N <= 1) {
        return;
    }

    qsort(array, 0, N - 1);
}

void Sort::qsort(std::vector<int> &array, int low, int high) {
    if (low < high) {
        if (high - low + 1 <= QUICK_SORT_THRESHOLD) {
            insertionSortPart(array, low, high);
        } else {
            int pivot = qsort_partition(array, low, high);
            if (pivot - low <= high - pivot) {  // sort shorter partition first
                qsort(array, low, pivot - 1);
                qsort(array, pivot + 1, high);
            } else {
                qsort(array, pivot + 1, high);
                qsort(array, low, pivot - 1);
            }
        }
    }
}

int Sort::qsort_partition(std::vector<int> &array, int low, int high) {
    low = qsort_getPivotPos_low(array, low, high);
    int pivotValue = array[low];

    while (low < high) {
        while ((low < high) && (array[high] >= pivotValue)) {
            high--;
        }
        array[low] = array[high];
        // cannot increment low here.

        while ((low < high) && (array[low] <= pivotValue)) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = pivotValue;
    return low;
}

// high - low > 10
int Sort::qsort_getPivotPos_low(std::vector<int> &array, int low, int high) {
    if (high - low + 1 <= 2) {
        return low;
    }

    int mid = low + (high - low) / 2;
    if (array[mid] < array[low]) {
        std::swap(array[mid], array[low]);
    }
    if (array[high] < array[low]) {
        std::swap(array[high], array[low]);
    }
    if (array[high] < array[mid]) {
        std::swap(array[high], array[mid]);
    }
    std::swap(array[mid], array[low + 1]);   // swap center value to low + 1
    return low + 1;
}

当带排序的数小于10的时候，切换到插入排序，因为这时，快速排序的性能并没有插入排序高。

快速排序中，比较重要的一点是选取枢轴值。通常是选取left, center， right中的中值。

以上算法的头文件

#include <vector>

class Sort {
public:
    static void test();

    static int BiSearch(const std::vector<int> &arr, int key);

    static void BubbleSort(std::vector<int> &array);

    static void InsertionSort(std::vector<int> &array);

    static void QuickSort(std::vector<int> &array);

    static void MergeSort(std::vector<int> &array);

    static const int QUICK_SORT_THRESHOLD = 10;
protected:
    static void insertionSortPart(std::vector<int> &array, int low, int high);

    static int qsort_partition(std::vector<int> &array, int low, int high);

    static void qsort(std::vector<int> &array, int low, int high);

    static int qsort_getPivotPos_low(std::vector<int> &array, int low, int high);

    static void msort_merge(std::vector<int> &array, int left, int right);
};

#endif //AGORITHM_SORT_H

// .cpp

void Sort::test() {
    std::vector<int> vec = {1, 0, 0, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    MergeSort(vec);
    Util::PrintVec(vec);
    cout << endl;

    cout << "pos of 5: " << BiSearch(vec, 5) << endl;
}


int Sort::BiSearch(const vector<int> &arr, int key) {
    const int N = arr.size();
    if (N == 0) {
        return -1;
    }

    int low = 0;
    int high = N - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}