几种排序算法的实现

Post on Jul 30, 2023 · 排序算法 C++

排序算法是最经典的算法知识。因为其实现代码短，应该广，在面试中经常会问到排序算法及其相关的问题。一般在面试中最常考的是快速排序和归并排序等基本的排序算法，并且经常要求现场手写基本的排序算法。

排序算法稳定性：如果两个相等的数字，排序完成后，相对顺序不变，是稳定，否则是不稳定
排序算法优化思路：减少比较次数，减少交换次数。

 1#pragma once 
 2
 3#include <vector>
 4#include <utility>
 5
 6class MySort {
 7public:
 8    void bubble(std::vector<int>&);
 9    void insertion(std::vector<int>&);
10    void selection(std::vector<int>&);
11    void quick(std::vector<int>&, size_t, size_t);
12    void heap(std::vector<int>&);
13
14private:
15    void max_heapify(std::vector<int>&, size_t);
16};

1. 冒泡排序

冒泡排序两层循环，内层循环依次比较相邻值的大小，将较大值依次向后交换，类似水中上浮的泡泡，逐渐变大，每次内层循环结束，最大值均出现在正确的位置。

 1void MySort::bubble(std::vector<int>& nums) {
 2    for (size_t i = 0; i < nums.size(); i++)
 3    {
 4        for (size_t j = 0; j < nums.size()-i-1; j++)
 5        {
 6            if (nums[j] > nums[j+1])
 7            {
 8                std::swap(nums[j], nums[j+1]);
 9            }
10        }
11    }
12}

2. 选择排序

 1void MySort::selection(std::vector<int>& nums) {
 2    for (size_t i = 0; i < nums.size(); i++)
 3    {
 4        size_t min_index = i;
 5        for (size_t j = i+1; j < nums.size(); j++)
 6        {
 7            if (nums[j] < nums[min_index]) {
 8                min_index = j;
 9            }
10        }
11
12        std::swap(nums[i], nums[min_index]);
13    }
14}

3. 插入排序

 1void MySort::insertion(std::vector<int>& nums) {
 2    for (size_t i = 1; i < nums.size(); i++)
 3    {
 4        size_t j = i;
 5        while (j > 0) {
 6            if (nums[j] >= nums[j-1]) {
 7                break;
 8            }
 9            else // (nums[j] < nums[j-1])
10            {
11                std::swap(nums[j-1], nums[j]);
12            }
13            --j;
14        }
15    }
16}

4. 快速排序

 1void MySort::quick(std::vector<int>& nums, size_t low, size_t high) {
 2    if (low >= high) {
 3        return;
 4    }
 5
 6    size_t left = low;
 7    size_t right = high;
 8    int pivot = nums[left];
 9
10    // 选择第一个值作为基准值
11    // 从后往前，找第一个小于基准值的值，将其值调换到前面。
12    // 从前往后，找第一个大于基准值的值，将其值调换到后面
13    while (left < right) {
14        while (left < right && nums[right] >= pivot) {
15            --right;
16        }
17        nums[left] = nums[right];
18        while (left < right && nums[left] <= pivot) {
19            ++left;
20        }
21        nums[right] = nums[left];
22    }
23    nums[left] = pivot;
24
25    quick(nums, low, left - 1);
26    quick(nums, left + 1, high);
27}

5. 堆排序

 1void MySort::heap(std::vector<int>& nums) {
 2    for (size_t i = nums.size(); i > 0; --i)
 3    {
 4        max_heapify(nums, i);
 5
 6        // 堆顶元素和Kn交换
 7        std::swap(nums[0], nums[i-1]);
 8    }
 9}
10
11void MySort::max_heapify(std::vector<int>& nums, size_t limit) {
12    size_t length = nums.size();
13    if (length < 0 || length < limit) {
14        return;
15    }
16
17    int parent_idx = static_cast<int>(limit) >> 1;
18    for (; parent_idx >= 0; parent_idx--)
19    {
20        if (parent_idx * 2 >= limit) {
21            continue;
22        }
23
24        int left = parent_idx * 2;
25        int right = (left + 1) >= limit ? left : (left + 1);
26
27        int max_child_idx = nums[left] > nums[right] ? left : right;
28        if (nums[max_child_idx] > nums[parent_idx]) {
29            std::swap(nums[parent_idx], nums[max_child_idx]);
30        }
31    }
32}

本文的版权归作者 longfellow 所有，采用 The MIT License (MIT)。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！