专栏首页MasiMaro 的技术博文算法与数据结构(五):基本排序算法

算法与数据结构(五):基本排序算法

前面几篇基本上把基本的数据结构都回顾完了,现在开始回顾那些常见的排序算法。

排序是将一组无序的数据根据某种规则重新排列成有序的这么一个过程,当时在大学需要我们手工自己实现的主要有三种:选择排序、插入排序和冒泡排序。因为它比较简单,所以这里把他们放到一起作为最基本的排序算法。

插入排序

插入排序的思路是这样的:首先假设{k1, k2, k3, ...., kn} 中第一个元素是一个有序序列,从k2 开始插入到前面有序序列的适当位置从而使之前的有序序列仍然保持有序

这么说可能有点抽象,我们以一个实例来说明:

假设现在有这么一组待排元素: 3,6,1,2,8,4,7; 先假设第一个元素3 是一个有序序列,从后续序列中取出6这个元素插入到前面的有序序列,得到3, 6 这么一个有序序列,此时序列为:3, 6, 1, 2, 8, 4, 7 现在3, 6 是一个有序序列,从之前的序列中取出1,插入到有序序列的合适位置,得到1, 3, 6 这么一个有序序列,此时序列为: 1, 3, 6, 2, 8, 4, 7 接着从待排元素中取出2,插入到适当位置,得到有序序列 1, 2, 3, 6;此时序列为 1, 2, 3, 6, 8, 4, 7 以此类推,直到所有元素都排列完成,下面是每次排序后生成的序列 1) 3 6 1 2 8 4 7 2) 1 3 6 2 8 4 7 3) 1 2 3 6 8 4 7 4) 1 2 3 6 8 4 7 5) 1 2 3 4 6 8 7 6) 1 2 3 4 6 7 8 7) 1 2 3 4 6 7 8

那么知道了这个算法的思想,下面就是考虑该如何将其转化为代码,由计算机帮助我们实现这些事了。

首先这段代码至少有一层循环来依次取出序列中的待排元素,由于假定第一个元素已经是有序的,所以循环次数应该是n - 1次,而且从序列的第2个元素开始。

for(int i = 1; i < n; i++)
{
    //do something;
}

那么如何确定元素的适当位置呢,我们人从肉眼上来看肯定是可以看出来的,计算机并不知道啊。由于之前的序列肯定是有序的,所以这里我们只需要从前往后将有序序列中的数与待插入数比较,只要序列中的数大于待插入数,那么将带插入数插入到该数的前面就可以了。因为之前的序列是有序的,插入到该位置肯定能保证新插入数大于它之前的数但是小于它之后的数。这个时候我们可以写出这样一段伪代码

for(int i = i; i < n; i++)
{
    for(int j = 0; j < i; j++)
    {
        if(a[i] < a[j])
        {
            //此时j就是插入的位置,插入即可
        }
    }
}

同时在插入的时候需要考虑腾挪后续的元素,为了方便腾挪元素,应该从有序列表的后方向前面进行比较,在比较的同时进行元素的腾挪,直到找到位置,这个时候的代码应该替换为这样

for(int i = i; i < n; i++)
{
    int tmp = a[i];
    int j = i - 1; //从有序列表的最后一个元素开始往前找
    while(j >= 0 && tmp < a[j])
    {
        a[j + 1] = a[j]; //将对应元素往后挪一个位置
        j--;
    }

    a[j + 1] = tmp;
}

从算法上来看,插入排序是一种O(n^2)的算法

选择排序

选择排序是最好理解的一种算法,选择排序的基本思路是每次从待排序列中选择最大(或者最小)的一个,放到已排好的序列的最前面,形成一个新的有序序列,直到所有元素都完成排序

仍然是之前的一个序列 3, 6, 1, 2, 8, 4, 7

首先找到最小的数1,排到最前面:1, 6, 3, 2, 8, 4, 7 再找到后续最小数2,排到1后面:1, 2, 3, 6, 8, 4, 7 接着找到后续最小数3,排到2后面:1, 2, 3, 6, 8, 4, 7

以此类推,得到每次排序后的序列: 1) 1 6 3 2 8 4 7 2) 1 2 3 6 8 4 7 3) 1 2 3 6 8 4 7 4) 1 2 3 4 8 6 7 5) 1 2 3 4 6 8 7 6) 1 2 3 4 6 7 8 7) 1 2 3 4 6 7 8

从上面来看,每次确定了最小数之后只需要将对应位置的数与这个最小数交换就完成了排序,这也是与插入排序不同的地方,插入排序在处理元素的时候采用腾挪的方式,而选择排序则直接采用交换,也就是说插入排序在处理未排序元素的时候并没有改变他们的位置,而选择排序则有可能修改他们的位置,因此我们说选择排序是一种不稳定的排序,而插入排序是稳定的排序.

实现的算法如下:

for (int i = 0; i < n - 1; i++)
{
  int k = i; //k 表示当前剩余序列中最小数的位置
  //该循环从当前剩余数中找到最小数位置
  for (int j = i; j < n; j++)
  {
    if (a[j] < a[k])
    {
      k = j;
    }
  }

  if (k != i)
  {
    int tmp = a[k];
    a[k] = a[i];
    a[i] = tmp;
  }
}

选择排序的时间复杂度仍然是 O(n^2)

冒泡排序

冒泡排序是在C语言课上讲到的一种排序方式,简单来说就是将待排序列中的数据从头开始两两比较,然后将大数交换到后面,这样每次循环之后总是大数沉到最后面,进行多次这样的循环,就能完成排序

还是从 3, 6, 1, 2, 8, 4, 7 序列的排序开始 首先3与6相比,6大,此时不用交换,接着,6与1比较,6大然后进行交换。接着6与2比较,再交换,6与8比较,不用交换,8与4比较需要交换,8与7比较需要交换,因此第一次冒泡的结果是3, 1, 2, 6, 4, 7, 8 依次类推得到每次结果如下: 1) 3 1 2 6 4 7 8 2) 1 2 3 4 6 7 8 3) 1 2 3 4 6 7 8 4) 1 2 3 4 6 7 8 5) 1 2 3 4 6 7 8 6) 1 2 3 4 6 7 8 7) 1 2 3 4 6 7 8

实现的算法如下:

for (int i = 0; i < nLength - 1; i++)
{
  for (int j = 0; j < nLength - i - 1; j++)
  {
    if (a[j] > a[j + 1])
    {
      int tmp = a[j];
      a[j] = a[j+ 1];
      a[j + 1] = tmp;
    }
  }
}

冒泡排序也是一个不稳定的排序算法,它的时间复杂度也是O(n^2)


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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法与数据结构(七):快速排序

    在上一篇中,回顾了一下针对选择排序的优化算法——堆排序。堆排序的时间复杂度为O(nlogn),而快速排序的时间复杂度也是O(nlogn)。但是快速排序在同为O(...

    Masimaro
  • 算法与数据结构(三):栈

    栈与队列一样也是一种线性的数据结构,与队列不同的是栈是一种先进后出的结构,有点类似于现实中的弹夹,最后压进去的子弹总是最先被打出来,在计算机中栈用到的地方就是用...

    Masimaro
  • socket模型处理多个客户端

    最近学完了简单的socket编程,发现其实socket的网络编程其实并没有什么难度,只是简单的函数调用,记住客户端与服务端的步骤,写起来基本没有什么问题。 ...

    Masimaro
  • 八大排序算法

    版权声明:本文为博主原创文章,未经博主允许不得转载。 ...

    用户2965768
  • 揭秘:从内部源码看Facebook技术(第一集)

    Warning 本文中所有代码都是通过合法途径获得。 写在前面 我是一名铁杆Facebook粉丝。Facebook为开源社区贡献了许多力量,经常开放他们内部的软...

    FB客服
  • 存储过程和触发器的应用

    L宝宝聊IT
  • 通俗易懂:8大步骤图解注意力机制

    BERT、RoBERTa、ALBERT、SpanBERT、DistilBERT、SesameBERT、SemBERT、MobileBERT、TinyBERT和C...

    AI科技大本营
  • 如何做到企业合规看这里——介绍Salesforce Shield

    互联网的创建是为了共享信息。但是随着互联网的应用已经扩大到包括电子商务和企业软件领域,很明显,并不是所有的信息都是要与所有人共享。很多行业,如金融服务、医疗保健...

    臭豆腐
  • PostgreSQL的clog—从事务回滚速度谈起

    如果是之前学习别的数据库的人,看PostgreSQL会感觉到有句话非常奇怪:“PostgreSQL的回滚是立即完成的,不会受到事务大小本身的影响”。

    数据和云
  • PostgreSQL的clog—从事务回滚速度谈起

    原文:http://www.enmotech.com/web/detail/1/701/1.html  (复制链接,打开浏览器即可查看)

    数据和云01

扫码关注云+社区

领取腾讯云代金券