专栏首页算法其实很好玩Day23-排序-快排&堆排&归并排序

Day23-排序-快排&堆排&归并排序

一 鸽王回来了!

由于前段时间真的有点忙,鸽了大家一个礼拜多

然后,鸽王今天回来了,明天继续更图,今天小试牛刀一下

排序算法很基础,基础还是要打扎实~

像冒泡排序这种时间复杂度为O(N²)的渣渣排序算法就不更了

快排的平均时间复杂度,堆排和归并的时间复杂度都是O(nlog(n))

所以这仨都值得一写,也是面试的高频排序题

二 快排开始搞起来!

Q:实现快速排序

冷静分析一下快排的基本思想:(以最终升序为例)

1.取数组第一个元素,为基准值;

2.建立左右指针,分别指向第一个和最后一个元素;

3.在左指针 < 右指针 下进行循环:

右指针--,直到找到比基准值小的元素,将左右指针指向的元素进行交换;

左指针++,直到找到比基准值大的元素,将左右指针指向的元素进行交换;

4.此时初始数组的第一个元素,即我们刚才定义的基准值,已在其最终位置上,那么对该数左边的部分递归快排,对该数右边的部分递归快排;

//
// Created by renyi on 2019-07-26.
//
#include <iostream>
#include <vector>
using namespace std;

void printArray(vector<int> nums){
    for (int i = 0; i < nums.size(); i++) {
        printf("[%d]", nums[i]);
    }
    printf("\n");
}

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void quickSort(vector<int> &nums, int low, int high){
    if (low >= high){
        return;
    }

    int i = low;
    int j = high;
    int base = nums[i];

    while (i < j){
        while (i < j && nums[j] >= base){
            j--;
        }
        swap(nums[i], nums[j]);

        while (i < j && nums[i] <= base){
            i++;
        }
        swap(nums[i], nums[j]);
    }

    quickSort(nums, low, i-1);
    quickSort(nums, i+1, high);
}

int main(){
    int temp[] = {7, 9, 5, 1, 2, 8, 6, 4, 0, 3, 10};
    vector<int> result;
    for (int i = 0; i < 11; i++) {
        result.push_back(temp[i]);
    }
    
    printArray(result);
    quickSort(result, 0, result.size()-1);
    printArray(result);
    
    return 0;
}

三 堆排开始搞起来!

Q:实现堆排序

冷静分析:先知道堆排序要干什么(仍然以最终升序为例)

网上找个图

堆排序的思路就是:这是初始的堆,我们现在要构造一个大顶堆。然后将大顶堆的堆顶,即当前最大的元素和最后一个元素交换,即把最大的堆顶,放到了最后面。同时将堆可操作的长度-1,即后面的堆顶,放到了倒数第二个位置。同时需要实现一个函数,完成每次交换完两个元素之后,调整堆使其继续保持为大顶堆。

这是初始的堆

利用我们自己实现的函数,将初始堆,构造为大顶堆

这是最终构造好的大顶堆

然后开始堆排序,将堆顶80与最后一个元素40进行交换,此时80就在其最终位置上了,可操作长度-1。接下来利用我们自己实现的函数,调整堆,使其继续为大顶堆,那么此时大顶堆的堆顶一定是70,将堆顶70交换到了下标为7的位置,依次类推~

//
// Created by renyi on 2019-07-26.
//
#include <iostream>
#include <vector>
using namespace std;

void printArray(vector<int> nums){
    for (int i = 0; i < nums.size(); i++) {
        printf("[%d]", nums[i]);
    }
    printf("\n");
}

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void adjustHeap(vector<int>& nums, int parNode, int high){
    int newParNode = parNode;
    int j = 2 * parNode + 1;//取根节点的左孩子

    while (j <= high){//如果j=high,说明没有右孩子,high就是左孩子
        if (j < high && nums[j] <= nums[j+1]){
            j += 1;//一个根节点下如果有两个孩子,将j指向更大的那个孩子
        }

        if (nums[j] >= nums[newParNode]){//如果j指向的孩子大于父节点,就交换
            swap(nums[j], nums[newParNode]);
            newParNode = j;
            j = j * 2 + 1;
        } else{
            break;
        }
    }
}

void heapSort(vector<int>& nums){
    int last = nums.size() - 1;
    int lastParNode = nums.size() / 2 - 1;//最后一个父节点

    while (lastParNode >= 0){
        adjustHeap(nums, lastParNode, last);
        lastParNode -= 1;//建立最大堆,是从后往前调整,每调整好一个节点,就从后往前移动一个节点
    }

    //上面的while循环结束之后,即建立起了一个最大堆
    //接下来开始堆排序,精髓就是,交换头和尾,把最大的放最后面,再调整为最大堆,继续交换
    while (last > 0){
        swap(nums[0], nums[last]);
        adjustHeap(nums, 0, last-1);//从前往后调整最大堆
        last -= 1;
    }
}

int main(){
    int temp[] = {7, 9, 5, 1, 2, 8, 6, 4, 0, 3, 10};
    vector<int> result;
    for (int i = 0; i < 11; i++) {
        result.push_back(temp[i]);
    }

    printArray(result);
    heapSort(result);
    printArray(result);
    return 0;
}

四 归并排序搞起来!

Q:实现归并排序

冷静分析:

归并排序也很经典,我就不画图了,大概讲一下思路:

归并排序的精髓:将大问题不断递归拆分为小问题,直到不能拆分为止,对最终拆分的一个个小部分进行排序&合并,然后一步一步向上回溯,最后一次是将两个有序数组合并为了一个有序数组,整体是递归&回溯的思想~

至于代码实现,就是讲原始数组,按下标一半进行拆分,然后将左边的数组递归拆分,将右边的数组递归拆分,直到不能拆分;此时进行回溯,即合并两个有序数组,一步一步向上回溯,最终合并两个大的有序数组~

个人认为归并排序的算法思路最精妙,也是本人最喜欢的排序算法

//
// Created by renyi on 2019-07-26.
//
#include <iostream>
#include <vector>
using namespace std;

void printArray(vector<int> nums){
    for (int i = 0; i < nums.size(); i++) {
        printf("[%d]", nums[i]);
    }
    printf("\n");
}

void mergeTwoSortedVector(vector<int>& vec1, vector<int>& vec2, vector<int>& vec){
    int i = 0;//遍历vec1的下标
    int j = 0;//遍历vec2的下标

    while (i < vec1.size() && j < vec2.size()){
        if (vec1[i] <= vec2[j]){
            vec.push_back(vec1[i]);
            i++;
        } else{
            vec.push_back(vec2[j]);
            j++;
        }
    }

    for (; i < vec1.size(); i++) {//谁更长,直接把剩余部分追加进去vec
        vec.push_back(vec1[i]);
    }
    for (; j < vec2.size(); j++) {
        vec.push_back(vec2[j]);
    }
}

void mergeSort(vector<int>& vec){
    if (vec.size() < 2){
        return;
    }

    int mid = vec.size() / 2;
    vector<int> vec1;
    vector<int> vec2;

    for (int i = 0; i < mid; i++) {
        vec1.push_back(vec[i]);
    }
    for (int j = mid; j < vec.size(); j++) {
        vec2.push_back(vec[j]);
    }

    mergeSort(vec1);
    mergeSort(vec2);
    vec.clear();
    mergeTwoSortedVector(vec1, vec2, vec);
}

int main(){
    int temp[] = {7, 9, 5, 1, 2, 8, 6, 4, 0, 3, 10};
    vector<int> result;
    for (int i = 0; i < 11; i++) {
        result.push_back(temp[i]);
    }
    
    printArray(result);
    mergeSort(result);
    printArray(result);

    return 0;
}

这三份代码的运行结果皆一致,均为

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day15-递归&回溯-无重复数组的子集

    本来昨天题的代码都写完了,但pm姐姐说,这个需求明天必须上,没办法,昨天就没时间写文章了

    BUPTrenyi
  • Day16-递归&回溯-有重复数组的子集

    其实今天这道题本应该在昨天的,第二篇文章中的,奈何需求多而紧,着实没时间写第二篇文章了,你们可不要以为我是划水啊

    BUPTrenyi
  • Day6-线性表-堆-数组中第K大的数

    下午从5点开始需求评审开了仨小时,去食堂吃完饭回来又赶紧干活,毕竟节前要上线,最近确实有点忙的手忙脚乱,盒饭更的稍微简短一些,不过干货肯定还是少不了的...

    BUPTrenyi
  • LeetCode 90. Subsets II

    ShenduCC
  • LeetCode 47. Permutations II

    ShenduCC
  • 46. 全排列【回溯算法】

    输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...

    韩旭051
  • Leetcode 90 Subsets II

    Given a collection of integers that might contain duplicates, nums, return all ...

    triplebee
  • C++进阶高级练习试题

    简单来说, 指的是生成 序列中的第 个位置; 指的是使用 中的第 个元素

    AI之禅
  • 一个易于理解的C++全排列(permutation)实现

    通常我们用这两条语句可以得到一个数组的全排列: sort(nums.begin(),nums.end()); //调用next_permutation求全排列...

    kalifa_lau
  • LintCode 1210. 升序子序列(DFS)

    给定一个整数数组,找到所有不同的可能的升序子序列,一个升序子序列的长度至少应为2。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券