• 欢迎访问小澍的博客,编程记录,技术贴以及折腾的日常,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我的博客吧

排序速记

C++ root 1年前 (2019-07-02) 383次浏览 已收录 0个评论

本文学习内容来自极客时间专栏《数据结构与算法之美》,感兴趣的可以去看看。

排序的分类

按需求

按照业务需求,排序分为稳定以及不稳定排序。所谓不稳定即算法在处理两个具有相同value的元素时,将元素顺序进行改变,这种情况就是不稳定的;反之,不会交换相同value的算法即稳定排序。同时,在空间占用角度下还需要注意在排序过程中是否使用了额外的空间进行辅助排序,未使用即成为原地排序。总结如下:
blob.jpg
下面按照这种分类来分别描述一下排序们。

冒泡排序

要点:每一轮进行两两比较,经过第一轮比较后,最大的一定被排序到了最后的位置,下一轮则会将第二大的元素交换到倒数第二个位置,以此类推,直到有序:
blob.jpg
实现:

void BubbleSort(vector<int>& square,int size)
{
    if (size<=1) return;
    bool flag = false;
    for (int i = 0; i < size; ++i)
    {

        for (int j = 0; j <size-i-1 ; ++j)
        {
            if (square[j]>square[j+1])
            {
                int temp = square[j+1];
                square[j+1] = square[j];
                square[j] = temp;
                flag = true;
            }
        }
        if (!flag)
            break;
    }
}

插入排序:

要点: 有点类似拿到扑克牌后整理牌的原理,从序列第二个序列开始作为待插入元素,如果有人问为什么不从第一个开始,因为第一个元素自己就是一个有序的序列鸭。。从第二个元素开始,和第一个子序列(也就是第一个元素)中的数据比较,遍历一圈找到可以插入的位置,找到后插入;通过循环不断加入新的元素,直到加完。
blob.jpg
实现:

void InsertSort(vector<int>& square,int size)
{
    if (size<=1)
        return;
    for (int i = 1; i < size; ++i)
    {
        int value = square[i];
        int j = i-1;
        for (;j>=0; j--)
        {
            if (square[j]>value)
                square[j+1] = square[j];//数据后移,留出位置给value
            else
                break;
        }
        square[j+1] = value;//极端情况下,j是会变成-1的,所以极端情况下是将数据插入到头部
    }
}

归并排序

要点: 分两步,先不断的进行一半一半的分裂,直到分裂到单元素为之,然后相邻的单元素的序列进行合并,合并的过程中进行排序,即排序中合并,直到合并为原来的长度,就排序完了。
blob.jpg
难点就在如何合并的过程,在这个过程中,需要借助额外的序列来辅助排序,辅助序列里将两个待合并的元素有序填入序列中,之后再填入到原来的序列中。如果你把合并的过程逻辑理一遍,你会发现,原序列的相同位置将被重新填充若干次,填充的次数等于合并的次数/2.
实现:

void merge_square(vector<int>&square,int begin,int middle,int end,vector<int>&temp)
{
    int i = begin, j = middle+1; //两个序列各自的头部索引
    int m = middle, last = end ; //两个序列各自的尾部索引
    int tmppos = 0;
    while(i<=m&&j<=last)
    {
        if (square[i]<=square[j])
            temp[tmppos++] = square[i++];
        else if (square[j]<square[i])
            temp[tmppos++] = square[j++];
    }
    //经过第一个循环以后,需要合并的两段序列一定有一个已经完全入队
    while(i<=m)
        temp[tmppos++] = square[i++];
    while(j<=last)
        temp[tmppos++] = square[j++];   
    for (int i = 0; i < tmppos; ++i)
    {
        square[begin+i] = temp[i];
    }
}   


void merge_sort_core(vector<int>&square,int begin,int end,vector<int>&temp)
{
    if (begin<end)
    {
        int middle = (begin+end)/2;
        merge_sort_core(square,begin,middle,temp);
        merge_sort_core(square,middle+1,end,temp);
        merge_square(square,begin,middle,end,temp);
    }
}

快速排序

要点: 同样是一种可以使用递归来解决问题的排序算法,通过随机选取一个序列中的基准,将小于基准的排在基准左侧,大于基准的排在基准的右侧。基准的选择可以随机选取,比如选择中间位置的元素,或者选取序列中的最后一个,但如果要求性能,一般可选择数值靠近整体序列的平均值或中位数,下面的实现代码选择了序列的最后一位作为基准值进行比较。下图可以看出快排和归并的区别:
blob.jpg

int partition(vector<int> &square,int pivod,int left,int right)
{
    for (int j = left; j<right; ++j)
        {
            if (square[j]<=pivod)
            {
                int temp = square[j];
                square[j] = square[left];
                square[left] = temp;
                left++;
            }   
            if(j==right-1)
            {
                int temp = square[left];
                square[left] = pivod;
                square[j+1] = temp;
            }
        }
    return left;
}
void quicksort(vector<int> &square,int begin,int end)
{
    int left = begin;
    int right= end;
    int pivod = square[right]; //基准数

    if (left<right)
    {
        int q = partition(square,pivod,left,right);
        quicksort(square,begin,q-1);
        quicksort(square,q+1,end);
    }
}

这次先总结这几个经典排序算法,后面如果有用来解题再来讨论。。
Bye~


XiaoShuBlog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:排序速记
喜欢 (0)
[gaosirgoo@foxmail.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址