1. 排序算法

1.1. 排序算法比较

1.2. 起泡排序

• 起泡排序思路：
  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

void swap(int & a, int & b) {
    int c = a;
    a = b;
    b = c;
}
int bubble(int *num, int m) {
    int flag = 0;
    for (int i = 1; i < m; i++) {
        if (num[i-1] > num[i]) {
            swap(num[i-1], num[i]);
            flag = i;
        }
    }
    return flag;
}
void bubbleSort(int *num, int n) {
    int fl = bubble(num, n);
    while (fl) {
        fl = bubble(num, fl);
    }
}

1.3. 选择排序

• 选择排序思路：
  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  3. 以此类推，直到所有元素均排序完毕

void SelectionSort(vector<int>& v) {
    int min, len = v.size();
    for (int i = 0; i < len - 1; ++i) {
        min = i;
        for (int j = i + 1; j < len; ++j) {
            if (v[j] < v[min]) {    // 标记最小的
                min = j;
            }
        }
        if (i != min)  // 交换到前面
            swap(v[i], v[min]);
    }
}

// 模板实现
template<typename T> 
void Selection_Sort(std::vector<T>& arr) {
    int len = arr.size();
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++)
            if (arr[j] < arr[min])
                min = j;
        if(i != min)
            std::swap(arr[i], arr[min]);
    }
}

1.4. 插入排序

• 插入排序思路：
  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

void InsertSort(vector<int>& v)
{
  int len = v.size();
    for (int i = 1; i < len - 1; ++i) {
        int temp = v[i];
        for(int j = i - 1; j >= 0; --j)
        {
            if(v[j] > temp)
            {
                v[j + 1] = v[j];
                v[j] = temp;
            }
            else
                break;
        }
    }
}

1.5. 快速排序

• 快速排序思路：
  1. 选取第一个数为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面
  3. 对左右区间重复第二步，直到各区间只有一个数

template <typename T> 
T * QuickSort(T * num, int low, int hi) {
    if (low >= hi)
        return num;
    int left = low;
    int right = hi;
    while (left < right) {
        while ((num[right] >= num[low]) && (left < right)) {
            right--;
        }
        while ((num[left] < num[low]) && (left <right)){
            left++;
        }
        std::swap(num[left], num[right]);
    }
    std::swap(num[left], num[low]);

    QuickSort(num, low, left - 1);
    QuickSort(num, left + 1, hi);
    return num;
}

// ----------------------------------------------------

// 模板实现快速排序（迭代）
struct Range {
    int start, end;
    Range(int s = 0, int e = 0) {
        start = s, end = e;
    }
};
template <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort(T arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負值時宣告堆疊陣列當機
    // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right) left++;
            while (arr[right] >= mid && left < right) right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}

1.6. 归并排序

• 分而治之

template<typename T>
void merge(vector<T> &num, int lo, int mi, int hi) {
    int lb = mi - lo;
    int lc = hi - mi;
    T *pa = &num[lo];
    T *pb = new T[lb];
    T *pc = &num[mi];
    for (int i = 0; i < lb; i++) {
        pb[i] = pa[i];
    }
    for (int m = 0, n = 0, k = 0; (m < lb) || (n < lc);) {
        if ((m < lb) && ((n >= lc) || (pb[m] < pc[n])))
            pa[k++] = pb[m++];
        else
            pa[k++] = pc[n++];
    }
}
template <typename T>
void mergeSort(vector<T> & A,int lo, int hi) {
    if (hi - lo < 2)        //递归条件
        return;
    int mi = (hi + lo) >> 1;
    mergeSort(A,lo, mi);
    mergeSort(A,mi, hi);
    merge(A,lo, mi, hi);
}

template<typename T>
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

1.7. 堆排序