专栏首页小浩算法漫画:排序算法系列 第一讲(利用插入算法思想解题)

漫画:排序算法系列 第一讲(利用插入算法思想解题)

在本系列中,将为大家讲解排序算法相关内容。同时,由于网上排序相关的教程太多了,我会尽可能的讲解一些不一样的内容。而不是按照 排序讲解 标准Titile,什么“十大排序算法”,“经典排序算法”,“排序算法必知必会” 之类的一个一个来进行讲解。所以,如果内容引起不适,概不负责...

01 排序的重要性

在leetcode中,直接搜索排序标签出现的题目有80余道,这是与排序直接相关的题目,不包括其他一些用到排序思想的题目。

同时,各个公司在面试的过程中,或多或少都直接或间接问到过排序相关的内容(毕竟面试官不知道问什么时,都会用排序算法来救救场。不要问我是怎么知道的...),尤其是 快排、堆排序、全排列 等 Topic,在面试中屡试不爽。

百度:堆排序

滴滴:全排列

综上,得出结论:为了offer~排序很重要,我们需要进行掌握。

02 从“插入排序”说起

为什么要先讲插入排序的原因,是因为我觉得插入排序是最容易理解的一个,而且插入这个词有一定的神秘感(好吧,反正我不觉得冒泡最容易理解,谁没事一天去观察吐泡泡?)

插入排序:就是炸金花的时候,你接一个同花顺的过程。(标准定义:在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的)

代码示例:

//go语言示例
func main() {
    arr := []int{5, 4, 3, 2, 1}
    insert_sort(arr)
}

func insert_sort(arr []int) {
    for i := 1; i < len(arr); i++ {
        for j := i; j > 0; j-- {
            if arr[j] < arr[j-1] {
                arr[j], arr[j-1] = arr[j-1], arr[j]
            }
        }
        fmt.Println(arr)
    }
}

输出:

讲解完了插入排序,我们根据其思想,完成一道题目:

03

905. 按奇偶排序数组

第905题:给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。你可以返回满足此条件的任何数组作为答案。

示例:

输入:[3,1,2,4]

输出:[2,4,3,1]

输出 [4,2,3,1],[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示:

1 <= A.length <= 5000

0 <= A[i] <= 5000

这道题,按照插入排序的思想,很容易可以想到题解。我们只需要遍历数组,当我们遇到偶数时将其插入到数组前最近的一个为奇数的位置,与该位置的奇数元素交换。为了达成该目的,我们引入一个指针 j,来维持这样一个奇数的位置。

假设我们的数组为:[3,1,2,4]

根据分析,得到代码:

//go
func sortArrayByParity(A []int) []int {
    j := 0
    for i := range A {
        if A[i]%2 == 0 {
            A[j], A[i] = A[i], A[j]
            j++
        }
    }
    return A
}

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

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

原始发表时间:2020-02-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》第22天:链表成环的新解法

    思路:通过hash表来检测节点之前是否被访问过,来判断链表是否成环。这是最容易想到的一种题解了。过于简单,直接上代码,go:

    程序员小浩
  • 图解:「归并排序」

    今天小浩给大家分享一篇关于归并排序的文章。考察归并排序的题目可以形态各异,但是万变不离其宗,希望看完今日之章,你能掌握归并排序及其思想大成。

    程序员小浩
  • 漫画:三次反转旋转数组

    第189题:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    程序员小浩
  • PHP实现插入排序

    关于排序的算法,就此告一段落。冒泡排序、快速排序、选择排序、加上本篇的插入排序,这四种算法都是相对简单,容易理解的。更复杂的算法,就不献丑了,以免误人子弟。

    猿哥
  • 在django中使用post方法时,需要增加csrftoken的例子

    从百度查到在django中,使用post方法时,需要先生成随机码,以防止CSRF(Cross-site request forgery)跨站请求伪造,并稍加修改...

    砸漏
  • 快速排序算法介绍

    快速排序(QuickSort)是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的...

    大江小浪
  • 面试官问:孤儿进程和僵尸进程,你造吗~

    那时刚写公众号,当时记录的学习笔记,现在看来,之前记录的有一个错误的地方,当时也没察觉到。

    Java小咖秀
  • 排序算法之希尔排序

    希尔排序是优化后的插入排序,又名玄学排序,因为希尔排序是不稳定的。希尔排序就是将一个数组分成间隔为h的子数组,并对这些子数组进行插入排序,通过不断地缩小h的值,...

    dejavu1zz
  • PHP 循环引用的问题

    这段代码很简单, 输出数组的元素两次, 感觉会输出两次 abcd? 不好意思, 输出结果如下: 

    烟草的香味
  • OneinStack 一键安装 JAVA/Tomcat/Nginx/MySQL 等 PHP 环境

    魏艾斯博客www.vpsss.net

扫码关注云+社区

领取腾讯云代金券