【数据结构】七大排序代码实现

Myth丶恋晨 2024-02-21 11:22 56阅读 0赞

#include <iostream>
    #include <vector>
    using namespace std;
    
    /**
     * 遍历并重新初始化
     * @param nums
     */
    void display(vector<int>& nums) {
        // 1. 打印数组
        for (int i = 0; i < nums.size(); ++i) {
            cout << nums[i] << " ";
        }
         cout << endl;
    
        // 2. 重置数组
        nums = {9,8,7,6,5,4,3,1,2};
    }
    
    /**
     * 交换数组中两元素的位置
     * @param nums
     * @param i
     * @param j
     */
    void swap(vector<int>& nums, int i, int j) {
        // 1. 记录i位置的值
        int tmp = nums[i];
        // 2. 将j位置的值给i位置
        nums[i] = nums[j];
        // 3. 最后将原先保存的i位置的值给j位置
        nums[j] = tmp;
    }
    
    /**
     * 插入排序
     * 时间复杂度： n²
     * 稳定性：    稳定
     * @param nums
     */
    void insert_sort(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            // 1. 找到当前位置的前一个下标
            int j = i - 1;
            // 2. 记录当前位置的值
            int tmp = nums[i];
            for ( ; j >= 0; j--) {
                // 3. 用选中元素与之前的元素进行比较
                if (nums[j] > tmp) {
                    // 4. j位置的值比选中元素的值大，后移一位
                    nums[j + 1] = nums[j];
                } else {
                    // 5. 此时j位置的值小于当前选中元素结束循环
                    break;
                }
            }
            // 6. 将j的后一个元素的值修改为选中的元素
            nums[j + 1] = tmp;
        }
    }
    
    /**
     * 希尔排序
     * 时间复杂度： O(n1.2 - 1.5)
     * 稳定性：    不稳定
     * @param nums
     */
    void shell_sort (vector<int>& nums) {
        // 1. 定义每次分组的元素个数
        vector<int> gap = {static_cast<int>(nums.size() / 2), 1};
        for (int i = 0; i < gap.size(); i++) {
            // 2. 按照不同的分组元素数进行直接插入排序
            for (int j = gap[i]; j < nums.size(); j++) {
                int k = j - gap[i];
                int tmp = nums[j];
                for ( ; k >= 0; k -= gap[i]) {
                    if (nums[k] > tmp) {
                        nums[k + gap[i]] = nums[k];
                    } else {
                        break;
                    }
                }
                nums[k + gap[i]] = tmp;
            }
        }
    }
    
    
    /**
     * 选择排序
     * 时间复杂度： O(n2)
     * 稳定性：    不稳定
     * @param nums
     */
    void select_sort(vector<int>& nums) {
        // 1. 定义左右边界指针
        int left = 0;
        int right = nums.size() - 1;
        // 2. 开始遍历
        while (left < right) {
            // 3. 定义最小值下标与最大值下标
            int min_index = left, max_index = right;
    
            // 4. 开始寻找最大值与最小值对应的下标
            for (int i = left; i <= right; i++) {
                if (nums[i] < nums[min_index]) {
                    min_index = i;
                }
    
                if (nums[i] > nums[max_index]) {
                    max_index = i;
                }
            }
    
            // 5. 将最小值与左边指针位置进行交换后左指针向右移
            swap(nums,left,min_index);
            if (max_index == left) {
                // 5.1 如果最大值刚好是最左边的元素，由于上述交换最小值时将最左边的最大值换走了，此处需要修改最大值指针
                max_index = min_index;
            }
            // 6. 将最大值与右边指针位置进行交换后右指针左移
            swap(nums,right,max_index);
            right--;
            left++;
        }
    }
    
    /**
     * 冒泡排序
     * 时间复杂度： O(n2)
     * 稳定性：    稳定
     * @param nums
     */
    void bubble_sort(vector<int>& nums) {
        bool flag = true;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size() - 1 - i; j++) {
                if (nums[j + 1] < nums[j]) {
                    flag = false;
                    swap(nums, j, j + 1);
                }
            }
            if (flag) break;
        }
    }
    
    /**
     * 堆排序
     * 时间复杂度：
     * 稳定性：
     * @param nums
     */
    void heap_sort(vector<int>& nums) {
        // 1. 建立大根堆
        for (int parent = (nums.size() - 1 - 1) >> 1; parent >= 0; parent--) {
            // 1.1 找到孩子节点
            int child = (parent << 1)+ 1;
            // 1.2 开始向下调整
            while (child < nums.size()) {
                // 1.3 两个孩子节点中找打最大值
                if (child + 1 < nums.size() && nums[child] < nums[child + 1]) {
                    child++;
                }
    
                // 1.4 如果子节点最大值的值比父节点大则交换，并将父节点指向子节点向下继续调整
                if (nums[child] > nums[parent]) {
                    swap(nums, child, parent);
    
                    parent = child;
                    child = (parent << 1)+ 1;
                } else {
                    // 1.5 如果没有进行了交换则说明已经调整完毕
                    break;
                }
            }
        }
    
        // 2. 交换堆尾与堆顶元素
        int end = nums.size() - 1;
        while (end != 0) {
            // 2.1 将堆顶最大值放在最后
            swap(nums, 0, end);
            // 2.2 此时由于末尾元素在堆顶，导致不是大根堆，于是进行调整为大根堆
            int parent = 0;
            int child = (parent << 1)+ 1;
            while (child < end) {
                if (child + 1 < end && nums[child] < nums[child + 1]) {
                    child++;
                }
    
                if (nums[child] > nums[parent]) {
                    swap(nums, child, parent);
    
                    parent = child;
                    child = (parent << 1)+ 1;
                } else {
                    break;
                }
            }
            // 2.3 将末尾的指针向前调整
            end--;
        }
    }
    
    /**
     * 快速排序
     * 时间复杂度： O(n*log（n）)
     * 稳定性：    不稳定
     * @param nums
     */
    void quick_sort(vector<int>& nums, int left, int right) {
        // 1. 判断递归终止条件
        if (left >= right) {
            return;
        }
    
        // 2. 找基准    // {9,8,7,6,5,4,3,1,2};
        int start = left, end = right;
        while (start < end) {
            // 2.1 找到右边小于基准的位置
            while (start < end && nums[end] > nums[left]) {
                end--;
            }
    
            // 2.2 找到左边大于基准的位置
            while (start < end && nums[start] < nums[left]) {
                start++;
            }
            // 2.3 将左右不符合规则（左边都小于基准，右边都大于基准）的位置进行交换
            swap(nums, start, end);
        }
        // 2.4 最后将基准与交叉的指针进行交换
        swap(nums, left, start);
    
        // 3. 递归
        quick_sort(nums, left, start);
        quick_sort(nums, start + 1, right);
    }
    
    /**
     * 归并排序
     * 时间复杂度：O(n*log（n）)
     * 稳定性：   稳定
     * @param nums
     */
    void merge_sort(vector<int>& nums, int left, int right) {
        // 1. 递归终止条件
        if (left >= right) {
            return;
        }
    
        // 2. 递归开始
        int mid = (left + right) >> 1;
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
    
        // 3. 开始合并
        int tmp[nums.size()];
        int s1 = left, s2 = mid + 1, k = 0;
        while (s1 <= mid && s2 <= right) {
            if (nums[s1] > nums[s2]) {
                tmp[k++] = nums[s2++];
            } else {
                tmp[k++] = nums[s1++];
            }
        }
    
        // 3.1 将剩余未合并的部分进行追加
        while (s1 <= mid) {
            tmp[k++] = nums[s1++];
        }
    
        while (s2 <= right) {
            tmp[k++] = nums[s2++];
        }
    
        // 4. 将合并后有序的部分同步到原始数组上
        for (int i = 0; i < k; i++) {
            nums[i + left] = tmp[i];
        }
    }
    
    int main() {
        vector<int> nums = {9,8,7,6,5,4,3,1,2};
        // 1. 插入排序
        insert_sort(nums);
        cout << "插入排序:";
        display(nums);
    
        // 2. 希尔排序
        shell_sort(nums);
        cout << "希尔排序:";
        display(nums);
    
        // 3. 选择排序
        select_sort(nums);
        cout << "选择排序:";
        display(nums);
    
        // 4. 冒泡排序
        bubble_sort(nums);
        cout << "冒泡排序:";
        display(nums);
    
        // 5. 堆排序
        heap_sort(nums);
        cout << "堆排序 :";
        display(nums);
    
        // 6. 快速排序
        quick_sort(nums, 0, nums.size() - 1);
        cout << "快速排序:";
        display(nums);
    
        // 7. 归并排序
        merge_sort(nums, 0, nums.size() - 1);
        cout << "归并排序:";
        display(nums);
    
        return 0;
    }