排序算法

总览

常见的排序算法一览表如下，复杂的不常见的还有希尔排序、计数排序、基数排序、桶排序就不看了。

排序算法	时间复杂度（最好）	时间复杂度（最差）	时间复杂度（平均）	空间复杂度	稳定排序	相关函数
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	否	FindMinIndex
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
快速排序				$O(nlogn)$	否	Partition
堆排序				$O(1)$	否	Heapify

冒泡排序

代码

void BubbleSort(vector<int> &nums) {
    int n = nums.size();
    bool exchange = false;
    // 我们要依次把n-1个最大的数冒泡到最右边有序部分，还剩一个数字已经是最小，就有序了
    for (int i = 0; i < n - 1; ++i) {
        // 遍历当前无序部分，即[0,n-1-i]，因为要依次对比相邻数字，左边数字范围就是[0,n-1-i)
        for (int j = 0; j < n - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                exchange = true;
            }
        }
        // 如果本轮冒泡，从0到最后一个无序数字，没发生过一次交换
        // 那说明这段数字，已经有序，非递减，因此整个数组已经有序，可以提前退出了
        if (!exchange)
            break;
    }
}

分析

选择排序

代码

void SelectSort(vector<int> &nums) {
    int n = nums.size();
    // 找到范围内最小元素的下标
    auto FindMinIndex = [] (vector<int> &nums, int low, int high) -> int {
        int minIndex = low;
        for (int i = low + 1; i <= high; ++i) {
            if (nums[i] < nums[minIndex])
                minIndex = i;
        }
        return minIndex;
    };
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = FindMinIndex(nums, i, n - 1);  // i前面是有序部分，i以及i右边的元素是无序部分，从中找到最小元素的下标
        if (minIndex != i)
            swap(nums[i], nums[minIndex]);  // 如果最小元素不是i自己，那就交换一下，把本轮最小元素放到当前位置
    }
}

分析

插入排序

代码

void InsertSort(vector<int> &nums) {
    int n = nums.size();
    for (int j = 1; j < n; ++j) {
        // // 方法一：
        // int i = j - 1;
        // // 其实这个思路不太符合插入排序的思想，更像是冒泡排序
        // // 每次都是比较相邻元素，将元素j往左逐位冒泡到他应该在的位置
        // while (i >= 0 && nums[i] > nums[i + 1]) {
        //     swap(nums[i], nums[i + 1]);
        //     --i;
        // }

        // 方法二：
        int i = j - 1;
        int key = nums[j];  // 这里我们先记下当前数字，因为它最终要插入到前面，前面的元素要后移，会占用它当前位置
        while (i >= 0 && nums[i] > key) {
            // 比较完元素i后，先把它后移，再继续比较下一个元素
            nums[i + 1] = nums[i];
            --i;
        }
        // 最终，不管有没有到头，到头的话，i就是-1，最终key都插入到i+1位置
        nums[i + 1] = key;
    }
}

分析

快速排序

代码

int Partition(vector<int> &nums, int low, int high) {
    int pivot = nums[high];  // 先初始化选最右边的数字为目标
    int i = low - 1;  // i用来写数组，默认放在-1的位置，写元素的时候先++
    for (int j = low; j < high; ++j) {  // 遍历除了最后一个数字的其它数字
        // 如果当前元素比pivot大于等于，那么，先不管他，继续下一个
        // 如果当前元素比pivot小，那么把它和数组i位置的数字交换
        //  这一步相当于把比pivot小的数字放在前面，前面那个位置本来的元素，交换到后面
        //  这会导致比pivot大的元素，在遍历后面的元素时候，被交换到后面，顺序会乱掉
        //  但最终结果是不断把大的元素交换到后面
        if (nums[j] < pivot) {
            swap(nums[++i], nums[j]);
        }
    }
    // 直到交换到最后pivot的位置，把pivot放到i的位置
    //  这时候，pivot左边都是小的，pivot右边都是大的
    swap(nums[++i], nums[high]);
    return i;
};

void QuickSort(vector<int> &nums, int low, int high) {
    if (low < high) {
        // 找一个目标，比他小的放在左边，比他大的放在右边
        int pi = Partition(nums, low, high);
        // pi的位置就对了，然后再分别去快速排序它左边和右边
        QuickSort(nums, low, pi - 1);
        QuickSort(nums, pi + 1, high);
    }
}

void QuickSort(vector<int> &nums) {
    int n = nums.size();
    QuickSort(nums, 0, n - 1);
}

分析

堆排序

代码

void Heapify1(vector<int>& nums, int i, int n) {  // 迭代版本
    while (i * 2 + 1 < n) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int max = i;
        if (left < n && nums[left] > nums[max])
            max = left;
        if (right < n && nums[right] > nums[max])
            max = right;
        // 这里需要注意，堆化一个节点，只需要将最大值和节点i交换即可
        // 因此，不需要先和左孩子对比交换，再和右孩子对比交换
        // 只需要找到三者的最大值，直接交换一次即可
        if (max != i) {
            swap(nums[i], nums[max]);
            i = max;  // 如果节点i和节点max交换了，那么节点max也需要重新堆化
        } else {
            break;  // 如果节点i本身就是最大值，那堆化就到此为止了，返回
        }
    }
}

void Heapify2(vector<int>& nums, int i, int n) {  // 递归版本
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int max = i;
    if (left < n && nums[left] > nums[max])
        max = left;
    if (right < n && nums[right] > nums[max])
        max = right;
    // 这里需要注意，堆化一个节点，只需要将最大值和节点i交换即可
    // 因此，不需要先和左孩子对比交换，再和右孩子对比交换
    // 只需要找到三者的最大值，直接交换一次即可
    if (max != i) {
        swap(nums[i], nums[max]);
        Heapify2(nums, max, n);  // 如果节点i和节点max交换了，那么节点max也需要重新堆化
    }
    // 如果节点i本身就是最大值，那堆化就到此为止了，返回
    // 如果已经是叶子节点，没有孩子节点，那么left和right就会不满足前面两个<n的if条件判断
    //  max==i，所以还是会在这里结束堆化，返回
}

/**
 * 堆排序
 */
void HeapSort(vector<int>& nums) {
    /**
     * 大体思路是，先把大顶堆构造好，此时，第0个元素就是堆顶，即最大值，将堆顶交换到最后边，它就不用再动了
     * 然后对于前面n-1的数组，本来是大顶堆，但是最大值被一个较小的值交换走了，因此这时大顶堆应该不对了，需要重新堆化第0个元素
     * 堆化一个节点，可能导致它左右孩子变化，变化的节点，也要递归往下堆化，直到叶子结点，重新完成堆化
     * 这时候，又是一个大顶堆了，再次把堆顶元素交换走
     * 重复这个操作
     */
    // 构建大顶堆
    int n = nums.size();
    for (int i = (n - 1) / 2; i >= 0; --i) {  // 从第一个非叶子节点开始，自右向左，自下而上堆化每一个节点，构建大顶堆
        Heapify2(nums, i, n);  // 堆化这个非叶子节点
    }
    // 循环把最大值交换到后面，然后重新堆化节点0，因为节点0变动了
    for (int i = n - 1; i > 0; --i) {
        swap(nums[0], nums[i]);
        Heapify2(nums, 0, i);
    }
}

分析