XIAOSUO 记录个人学习的足迹

摘要：一、如何选择合适的排序算法？ 排序算法一览表 时间复杂度 是稳定排序？ 是原地排序？ 冒泡排序 O(n^2) 是 是 插入排序 O(n^2) 是 是 选择排序 O(n^2) 否 是 快速排序 O(nlogn) 否 是 归并排序 O(nlogn) 是 否 桶排序 O(n) 是 否 计数排序 O(n+k)，k是数据范围 是 否 基数排序 O(dn)，d是纬度 是 否 为什选择快速排序？ 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。 同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。 二、如何优化快速排序？ 导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下： 三数取中法 从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。 如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。 随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 警惕快排的递归发生堆栈溢出，有2中解决方法，如下： 限制递归深度，一旦递归超过了设置的阈值就停止递归。 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。 三、通用排序函数实现技巧 数据量不大时，可以采取用时间换空间的思路 数据量大时，优化快排分区点的选择 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致 四、Go语言排序函数的实现 golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作，是基于首中尾中值的很复杂的变种 func quickSort(data Interface, a, b, maxDepth int) { for b-a 12 …… 阅读全文

摘要：一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。 对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。 二、桶排序（Bucket sort） 算法原理： 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 使用条件 要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。 数据在各个桶之间分布是均匀的。 代码实现 func tongSort(values []int) { t := make([]int, 10) for _, val := range values { t[val]++ } res := make([]int, 0, len(values)) for index, val := range t { //循环把排序元素添加到新的数组中 for ; val 0; val-- { res = append(res, index) } } fmt.Println(res) } 适用场景 桶排序比较适合用在外部排序中。 外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。 应用案例 需求描述： 有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序 但内存有限，仅几百MB 解决思路： 扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。 第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。 每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。 将100个小文件依次放入内存并用快排排序。 所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。 注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。 三、计数排序（Counting sort） 算法原理 计数其实就是桶排序的一种特殊情况。 当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶 …… 阅读全文

摘要：一、分治思想 分治思想：分治，顾明思意，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。 分治与递归的区别：分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。 二、归并排序 算法原理 先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢？写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。递推公式怎么写？如下 递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件：p = r 不用再继续分解。 代码实现 func mergeSort(arr []int, start, end int) { if start = end { return } mid:=(start + end) / 2 mergeSort(arr, start, mid) mergeSort(arr, mid+1, end) merge(arr, start, mid, end) } func merge(arr []int, start, mid, end int) { var tmparr = []int{} var s1, s2 = start, mid+1 for s1= mid s2= end{ if arr[s1] arr[s2] { tmparr = append(tmparr, arr[s2]) s2++ } else { tmparr = append(tmparr, arr[s1]) s1++ } } if s1=mid { tmparr = append(tmparr, arr[s1: mid+1]...) } if s2=end { tmparr = append(tmparr,…… 阅读全文

摘要：一、排序方法与复杂度归类 几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 复杂度归类 冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n) 二、算法的执行效率 算法的执行效率 最好、最坏、平均情况时间复杂度。 时间复杂度的系数、常数和低阶。 比较次数，交换（或移动）次数。 排序算法的稳定性 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 稳定性重要性：可针对对象的多种属性进行有优先级的排序。 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。 排序算法的内存损耗 原地排序算法：特指空间复杂度是O(1)的排序算法。 三、冒泡排序 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。 稳定性：冒泡排序是稳定的排序算法。 空间复杂度：冒泡排序是原地排序算法。 时间复杂度： 最好情况（满有序度）：O(n)。 最坏情况（满逆序度）：O(n^2)。 平均情况： “有序度”和“逆序度”：对于一个不完全有序的数组，如4，5，6，3，2，1，有序元素对为3个（4，5），（4，6），（5，6），有序度为3，逆序度为12；对于一个完全有序的数组，如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度。 最好情况下初始有序度为n*(n-1)/2，最坏情况下初始有序度为0，则平均初始有序度为n*(n-1)/4，即交换次数为n*(n-1)/4，因交换次数比较次数最坏情况时间复杂度，所以平均时间复杂度为O(n^2)。 func BubbleSort(values []int) { for i := 0; i len(values)-1; i++ { for j := i+1; j len(values); j++ { if v…… 阅读全文

摘要：一、什么是递归？ 递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。 基本上，所有的递归问题都可以用递推公式来表示，比如 f(n) = f(n-1) + 1; f(n) = f(n-1) + f(n-2); f(n)=n*f(n-1); 二、为什么使用递归？递归的优缺点？ 优点：代码的表达力很强，写起来简洁。 缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。 三、递归需要满足的三个条件 问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。 问题与子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件 四、如何实现递归？ 递归代码编写 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 递归代码理解 对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。 那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。 因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 五、递归常见问题及解决方案 警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。 六、如何将递归改写为非递归代码 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。 比如斐波拉契数列的实现 递归实现 func f(int n) int { if n == 1 { return 1 } if n == 2 { ret…… 阅读全文

摘要：一、什么是队列？ 1.先进者先出，这就是典型的“队列”结构。 2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。 3.所以，和栈一样，队列也是一种操作受限的线性表。 二、如何实现队列 1. 数组实现 type Queue struct { items []interface{} length int //数组大小 head int //表示队头下标 tail int //表示队尾下标 } func CreateStack(cap int) *Queue { if cap == 0 { panic(不能创建容量为0的队列！) } return Queue{ items: [capacity]interface, length: capacity, head:0, tail:0 } } func (this *Queue) Enqueue(item interface{})(err error){ if this.tail == this.length { return errors.New(queue full) } this.items[this.rear] = item this.tail++ return } func (this *Queue) Dequeue() (interface{},err error){ if this.head == this.tail { return _,errors.New(queue empty) } item = this.items[this.head] this.head++ return item,err } 比起栈的数组实现，队列的数组实现稍微有点儿复杂。 对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。 如下图：当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 …… 阅读全文

摘要：如何理解“栈” 栈是一种操作受限的数据结构，只支持入栈和出栈操作。 典型的“栈”结构：后进者先出，先进者后出。 从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 顺序栈的实现 type Item interface { } type ArrayStack struct { items []Item // 数组 count int //栈中元素个数 size int //栈的大小 } func CreateStack(cap int) *ArrayStack { if cap == 0 { panic(不能创建容量为0的栈！) } return ArrayStack{ items: make([]Item, cap), count: 0, size: cap, } } func (a *ArrayStack) Push(e Item) { if a.size=a.count { panic(栈已经满了！) } a.items[count] = e a.count++ } func (a *ArrayStack) Pop() *Item { if a.count == 0 { panic(栈已经空了！) } tmp = a.items[a.count-1] a.count-- return tmp; } } 链式栈实现 type Item interface { } type StackNode struct { el Item next *StackNode } type ListStack struct { top *StackNode count int //栈中元素个数 } func CreateStack() *ListStack { return new(LinkStack) } func (l *LinkStack) Push(el Item) { s := StackNode{el: el, next: l.top} l.t…… 阅读全文

摘要：什么是链表 和数组一样，链表也是一种线性表。 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。 链表的特点 插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。 常用链表 链表结构五花八门，本文来看一下最常见的三种链表结构，它们分别是：单链表、双向链表和循环链表。 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。 从图中可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。 循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。它像一个环一样首尾相连，所以叫作“循环”链表。 双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。 从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。 插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种…… 阅读全文

摘要：数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。 数组如何实现随机访问 数组是一种线性表 顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。 连续的内存空间和相同类型的数据 正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。 低效的插入和删除 插入：从最好O(1) 最坏O(n) 平均O(n) 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。作者举例说明 删除：从最好O(1) 最坏O(n) 平均O(n) 多次删除集中在一起，提高删除效率 记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。 支持动态扩容的数组实现 考虑3个问题 主要的操作 扩容的策略 数据迁移策略 package array type Array struct { data []interface{} size int } func CreateArray(cap int) *Array { if cap == 0 { panic(不能创建容量为0的数组！) } return Array{ data: make([]interface{}, cap), size: 0, } } func (a *Array) GetSize() int { return a.size } func (a *Array) GetCap() int { return len(a.data) } func (a *Array) Get(inde…… 阅读全文

摘要：最近一直在学习Go语言，因为工作中并没有用到Go，为了不让学到的知识点很快忘掉，我打算用Go语言来撸一遍基本的算法，巩固一下Go语法，也温习一下算法基础。今天是这个系列的第一篇，我们来谈谈什么是复杂度分析。 其实，只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而且认为复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。 大 O 复杂度表示法 算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？ 这里有段非常简单的代码，求 1,2,3…n 的累加和。现在，我就带你一块来估算一下这段代码的执行时间。 func cal(n int) int { sum := 0 for i := 0; i = n; i++ { sum += i } return sum } 从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？ 第 2 行代码分别需要 1 个 unit_time 的执行时间，第 3、4行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+1)*unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。 按照这个分析思路，我们再来看这段代码。 func cal(n int) int { sum := 0 for i := 0; i = n; i++ { for j := 0; j = n; j++ { sum += i * j } } return sum } 我们依旧假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢？ 第 2 行代码，每行都需要 1 个 unit_time 的执行时间，第 3 行代码循环执行了 n 遍，需要 n * unit_time 的执行时间，第 4、5 行代码循环执行了 n​2​遍， 2n​2​ * unit_time 的执行时间。所以，整段代码总的…… 阅读全文