回首頁

第九章 排序

原 Google Sites 連結：/cppzero/ch09

目錄

9.1 特殊條件排序

第七章中我們用 中的 sort 函數來排序。但是它只能依數值由小到大排序。可是如果遇到特殊條件的排序，Sort 就不知道要如何去排了。

d750. 11321 - Sort! Sort!! and Sort!!!

這題的排序條件很詭異。

//11321 - Sort! Sort!! and Sort!!! (by Snail)
#include <iostream>
#include <algorithm>                            // for sort
using namespace std;

int m;                                          // cmp 中要用到 m
                                                // 故宣告為全域
bool cmp (int a, int b) {
    if (a%m != b%m)                             // 若餘數不等
        return a%m < b%m;                       // 按餘數排序
    if ((a+b)%2)                                // 若一奇一偶
        return (a&1) > (b&1);                   // 奇數在前
    if (a%2)                                    // 同為奇數
        return a > b;                           // 大在前
    return a < b;                               // 否則小在前
}

int main () {
    int i, n, a[10000];
    while (cin >> n >> m, n) {
        for (i=0; i<n; i++)
            cin >> a[i];
        sort (a, a+n, cmp);
        cout << n << ' ' << m << endl;
        for (i=0; i<n; i++)
            cout << a[i] << endl;
    }
    cout << "0 0\n";
}

d731. 11039 - Building designing

d385. 10905 - Children’s Game

2005 NPSC 國中組決賽 E. 誰先晚餐 (高中組決賽 pE)

9.2 字典序

d829. 146 - ID Codes

給你一串陣列，要你找出下一個排列

規則

  1. 找出最右邊一組 a[x] 小於 a[x+1]
  2. 找不到時已經到最大排列，停止搜尋
  3. 否則找出在 a[x] 右邊大於 a[x] 的最小值 a[y]
  4. 交換 a[x] 和 a[y]
  5. 翻轉 a[x] 的序列
  6. 所得排列即得所求

以下是範例程式碼

#include <iostream>
using namespace std;
#define N 5
#define INF 100000
int a[N] = {1, 2, 3, 4, 5};

void reserve(int i, int j) {
    int b[N], x, y;
    for (x = 0; x <= j - i; x++)
        b[i + x] = a[j - x];
    for (y = i; y <= j; y++)
        a[y] = b[y];
    return;
}

bool find_next() {
    int i, j, t;
    for (i = N - 2; i >= 0; i--)
        if (a[i] < a[i + 1])break;
    if (i == -1)return 0;
    int min_value = INF, min_pos = -1;
    for (j = i + 1; j < N; j++) {
        if (a[j]>a[i] && a[j] < min_value) {
            min_pos = j;
            min_value = a[j];
        }
    }
    t = a[i], a[i] = a[min_pos], a[min_pos] = t; // swap
    reserve(i + 1, min_pos);
}

int main() {
    while (find_next()) {
        for (int i = 0; i < N; i++) {
            if (i)cout << ' ';
            cout << a[i];
        }
        cout << endl;
    }
}

next_permutation

c++ 裡已有內建字典序排列，是在的 next_permutation

範例如下

#include <iostream>
#include <algorithm>
using namespace std;
#define N 5
int a[N] = {1, 2, 3, 4, 5};

int main() {
    while (next_permutation(a, a+N)) {
        for (int i = 0; i < N; i++) {
            if (i)cout << ' ';
            cout << a[i];
        }
        cout << endl;
    }
}

是不是簡潔許多?

9.3 排序演算法

在第七章使用 “algorithm” 裡的 sort 解題目時，你可能遇到 TLE ，這時你可能會懷疑是不是自己寫出無限迴圈，但其實是 sort 讓你超過時間了，在 Wiki 的排序演算法內有各種演算法，例如 sort 是內省排序。這些演算法各有優缺點，有的省時，有的省空間，有的很好寫，以下介紹幾種

氣泡排序

氣泡排序是一種最基本的排序，是兩兩元素做比較然後交換。時間複雜度為 O(n^2)，空間複雜度為 O(n)。

範例程式碼

function bubble_sort (array, length) {
    var i, j;
    for (i from 0 to length-1) {
        for (j from 0 to length-1-i) {
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}
//from wiki

合併排序

合併排序法是使用分治法的概念，先將陣列分成兩半，再將兩個小陣列進行比大小，合併成一個陣列，以此類推，時間複雜度為 O(n log n)，空間複雜度為 O(n)

範例程式碼

#define L 500010
int arr[L], buf[L];

function mergesort(int left, int right) {
    if (right - left <= 1)return 0;
    int middle = (right + left) / 2;
    mergesort(left, middle);
    mergesort(middle, right);
    int i = left, j = middle, k = left;
    while (i < middle || j < right) {
        if (i >= middle)
            buf[k] = arr[j++];
        else if (j >= right)
            buf[k] = arr[i++];
        else {
            if (arr[i]<=arr[j])
                buf[k] = arr[i++];
            else
                    buf[k] = arr[j++];
        }
        k++;
    }
    for (int k = left; k < right; k++)
        arr[k] = buf[k];
}

計數排序

計數排序是一種線性時間排序算法，須先開一個陣列來計算各個數字的總數，再開另一個陣列，把數字由小(大)到大(小)填入，時間複雜度為 O(n+k)，空間複雜度為 O(n+k)，n 為陣列大小，k 為數字範圍。

範例程式碼

function countingsort() {
    int arr[M], a[N]
    memset(arr, 0, sizeof(arr));
    int x, i = 0;
    for (; i<n; i++) {
        scanf("%d", &x);
        arr[x]++;
    }
    for (i = x = 0; i<M; i++)
        while (arr[i]--)
            b[x++] = i;
}

補充資料