各种排序算法实现

C++实现各种排序算法。
上张图。

排序算法稳定性.png

自定义的swap函数。

template <typename T>
void myswap(T &a, T &b) {
    T tem = a;
    a = b;
    b = tem;
}

冒泡排序

void bubblesort(std::vector<int> &arr) {
    int n = arr.size();
    if (n <= 1) return;
    for (int i = 0; i < n; ++i) {
        for (int j = n - 1; j > i; --j) {
            if (arr[j] < arr[j - 1]) myswap(arr[j], arr[j - 1]);
        }
    }
}

插入排序

void insertsort(std::vector<int> &arr) {
    int n = arr.size();
    if (n <= 1) return;
    for (int i = 1; i < n; ++i) {
        int tem = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > tem) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tem;
    }
}

希尔排序

void shellsort(std::vector<int> &arr) {
    int n = arr.size();
    for (int incr = n / 2; incr > 0; incr /= 2) {
        for (int i = incr; i < n; i++) {
            int tem = arr[i];
            int j = i - incr;
            while (j >= 0 && arr[j] > tem) {
                arr[j + incr] = arr[j];
                j -= incr;
            }
            arr[j + incr] = tem;
        }
    }
}

选择排序

void selectsort(std::vector<int> &arr) {
    int n = arr.size();
    if (n <= 1) return;
    for (int i = 0; i < n; ++i) {
        int j = i, minv = arr[i], mini = i;
        for (; j < n; ++j) {
            if (arr[j] < minv) {
                minv = arr[j];
                mini = j;
            }
        }
        myswap(arr[i], arr[mini]);
    }
}

快速排序

void _quicksort(std::vector<int> &arr, int l, int r) {
    // select target
    int mid = (l + r) >> 1;
    if (arr[mid] < arr[l]) myswap(arr[l], arr[mid]);
    if (arr[r] < arr[mid]) myswap(arr[r], arr[mid]);
    if (arr[mid] < arr[l]) myswap(arr[l], arr[mid]);
    if (r - l < 3) return;
    int target = arr[mid];

    int i = l + 1, j = r - 1;
    while (i < j) {
        while (arr[i] < target) i++;
        while (arr[j] >= target) j--;
        if (i < j) myswap(arr[i], arr[j]);
    }
    _quicksort(arr, l, i);
    _quicksort(arr, i + 1, r);
}
void quicksort(std::vector<int> &arr) {
    if (arr.size() <= 1) return;
    _quicksort(arr, 0, arr.size() - 1);
}

归并排序

void _mergesort(std::vector<int> &arr, int l, int r) {
    if (r - l <= 0) return;
    int mid = (l + r) >> 1;
    _mergesort(arr, l, mid);
    _mergesort(arr, mid + 1, r);
    std::vector<int> tem;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (arr[i] < arr[j])
            tem.push_back(arr[i++]);
        else
            tem.push_back(arr[j++]);
    }
    while (i <= mid) {
        tem.push_back(arr[i++]);
    }
    while (j <= r) {
        tem.push_back(arr[j++]);
    }
    for (i = l; i <= r; ++i) {
        arr[i] = tem[i - l];
    }
}
void mergesort(std::vector<int> &arr) {
    if (arr.size() <= 1) return;
    _mergesort(arr, 0, arr.size() - 1);
}

堆排序

// 大顶堆
void _percalatedown(std::vector<int> &arr, int n, int idx) {
    int child;
    for (int i = idx; i * 2 <= n; i = child) {
        child = i * 2;
        if (i * 2 + 1 <= n && arr[i * 2] > arr[i * 2 - 1]) {
            child++;
        }
        if (arr[i - 1] < arr[child - 1])
            myswap(arr[i - 1], arr[child - 1]);
        else
            break;
    }
}
void heapsort(std::vector<int> &arr) {
    if (arr.size() <= 1) return;
    int n = arr.size();
    for (int i = n / 2; i > 0; --i) {
        _percalatedown(arr, n, i);
    }
    while (n > 0) {
        myswap(arr[0], arr[n - 1]);
        n--;
        _percalatedown(arr, n, 1);
    }
}

基数排序

struct Node {
    int val;
    Node *next;
    Node() { next = nullptr; }
    Node(int _val, Node *_next) : val(_val), next(_next) {}
};
// 仅能用于正整数
void radixsort(std::vector<int> &arr) {
    int n = arr.size();
    if (n <= 1) return;
    std::vector<Node *> bucket(10, nullptr);  //链表数组
    std::vector<Node *> tail(10, nullptr);  //链表数组每一项的最后一个元素
    Node nodes[n];  // 提前分配节点空间，避免用new/delete
    // 得到最大值
    int maxv = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (arr[i] > maxv) maxv = arr[i];
    }

    for (int low = 1; low < maxv; low *= 10) {
        int high = low * 10;
        for (int i = 0; i < n; ++i) {
            int digit = (arr[i] % high) / low;
            nodes[i].val = arr[i];
            nodes[i].next = nullptr;
            if (bucket[digit] == nullptr) {
                bucket[digit] = &nodes[i];
                tail[digit] = &nodes[i];
            } else {
                tail[digit]->next = &nodes[i];
                tail[digit] = &nodes[i];
            }
        }
        int idx = 0;
        for (int i = 0; i < 10; ++i) {
            Node *cur = bucket[i];
            bucket[i] = nullptr;
            tail[i] = nullptr;
            while (cur) {
                arr[idx++] = cur->val;
                cur = cur->next;
            }
        }
    }
}