[数据结构与算法]十大排序理解及实现（C++）

冒泡排序

通过两两比较交换每次把较大或较小的放到末端，是一种交换排序。

void bubblesort(vector<int>& arr) {
    int n = arr.size();
    while (n > 0) {
        int j = n;
        n = 0;
        for (int i = 1; i < j; i++) {
            if (arr[i - 1] > arr[i]) {
                int t = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = t;
                n = i;
            }
        }
    }
}

插入排序

希尔排序

堆排序

堆是一棵完全二叉树，树中每个结点的值都不小于其左右孩子的值即为大顶堆。STL中的priority_queue默认为大顶堆。 如果将待排序序列构造成一个大顶堆（makeheap or heapify），此时整个序列的最大值就是根结点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆（siftdown），这样会得到n个元素的次小值，这样反复执行n-1次，便能得到一个升序序列（sortheap）。堆排序是一种选择排序。

void siftdown(vector<int>& arr, int n, int i) {  // 非递归
        int l = 2 * i + 1;
        int r = l + 1;
        int idx = i;
        int midx = i;
        if (l <= n && arr[l] > arr[midx])
            midx = l;
        if (r <= n && arr[r] > arr[midx])
            midx = r;
        while (midx != idx) {
            int t = arr[midx];
            arr[midx] = arr[idx];
            arr[idx] = t;
            idx = midx;
            l = 2 * idx + 1;
            r = l + 1;
            if (l <= n && arr[l] > arr[midx])
                midx = l;
            if (r <= n && arr[r] > arr[midx])
                midx = r;
        }
    }
    void makeheap(vector<int>& arr, int n) {
        for (int i = (n - 1) >> 1; i >= 0; i--) {
            siftdown(arr, n, i);
        }
    }
    void sortheap(vector<int>& nums) {
        int n = nums.size() - 1;
        makeheap(nums, n);
        for (int i = n; i > 0; i--) {
            int t = nums[0];
            nums[0] = nums[i];
            nums[i] = t;
            siftdown(nums, i - 1, 0);
        }
    }

与50位技术专家面对面

20年技术见证，附赠技术全景图