手写排序算法总结

堆排序

最大堆，先建堆，再 pop 直至堆空，此时得到升序序列。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return _heap_sort(nums);
    }

private:
    void _max_heapify(vector<int> &nums, int curr, int len) {
        if (nums.empty())
            return;
        int max_child = -1;
        int left_child_idx = -1, right_child_idx = -1;
        while (curr * 2 + 1 < len) {
            left_child_idx = curr * 2 + 1;
            right_child_idx = curr * 2 + 2;
            max_child = 
                right_child_idx < len ? 
                (nums[left_child_idx] < nums[right_child_idx] ? right_child_idx : left_child_idx)
                : left_child_idx;
            if (nums[curr] < nums[max_child]) {
                swap(nums[curr], nums[max_child]);
                curr = max_child;
            }
            else 
                break;
        }
    }

    void _build_max_heap(vector<int> &nums, int len) {
        for (int curr = len / 2; curr >= 0; --curr) {
            _max_heapify(nums, curr, len);
        }
    }

    vector<int> &_heap_sort(vector<int> &nums) {
        if (nums.empty() || nums.size() == 1)
            return nums;
        int len = nums.size();
        _build_max_heap(nums, len);
        for (int i = len - 1; i >= 1; --i) {
            swap(nums[len - 1], nums[0]);
            len -= 1;
            _max_heapify(nums, 0, len);
        }
        return nums;
    }
};

插入排序

插入排序的中心思想是维护指针左侧数组的一致性，所谓一致性即数组有序。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return insertion_sort(nums);
    }

private:
    vector<int> &insertion_sort(vector<int> &nums) {
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = i; j > 0; --j) {
                if (nums[j] < nums[j - 1])
                    swap(nums[j], nums[j - 1]);
                else
                    break;
            }           
        }
        return nums;
    }
};

插入排序为稳定排序，最好情况为数组已经排序的情况为$\Omega (N)$，时间复杂度$O(N^2)$。

希尔排序

希尔排序是插入排序的改版，插入排序为希尔排序的特例，即插入排序的步长为1，而希尔排序的步长选择会影响其时间复杂度。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return shell_sort(nums);
    }

private:
    vector<int> &shell_sort(vector<int> &nums) {
        int step_size = nums.size() / 2;
        while (step_size > 0) {
            for (int i = step_size; i < nums.size(); i += step_size) {
                for (int j = i; j > 0; j -= step_size) {
                    if (nums[j] < nums[j - step_size])
                        swap(nums[j], nums[j - step_size]);
                    else
                        break;
                }
            }
            step_size /= 2;
        }
        return nums;
    }
};