码尚行动

分类

Linux(3) MySQL(11) 数据结构与算法(13) 测试理论(2) 随笔(2) 题解(3)

/ 注册

TA的专栏 14篇文章 1人订阅

走进测开的世界

4篇文章 2665人学习

种下数据库

10篇文章 789人学习

全部文章（共11篇）

基数排序

10.基数排序基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或“箱排序”（bin sort）。它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。基数排序法是属于稳定性的排序，受数据状况的...

排序算法

2021-02-25

0 525

计数排序

9.计数排序计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排...

排序算法

2021-02-25

0 483

桶排序思想

8.桶排序桶排序 (Bucket sort)是一种排序思想。工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(...

排序算法

2021-02-25

0 687

堆排序（拓展：堆、优先队列）

7.堆排序（快，不稳，使用较多）总结时间复杂度O(N*logN)，额外空间复杂度O(1)堆结构非常重要1，堆结构的heapInsert与heapify2，堆结构的增大和减少3，如果只是建立堆的过程，时间复杂度为O(N)4，优先级队列结构，就是堆结构大根堆的插入heapInsert 将一个数加入...

排序算法

2021-02-25

0 746

快排（拓展：partition、荷兰国旗问题）

6.快速排序(量大时特快,不稳定,对基础类型随机快排最常用) 快排的几种写法: (基本快排,随机快排,优化随机快排,双轴快排) 时空分析: 平均时间复杂度:n*logn ;空间复杂度logN （因为要记录断点【放在数组的位置】，用数组记录相等的范围）如果不用随机快排,最坏时间复杂度为N*2,...

排序算法

2021-02-25

0 602

归并排序（拓展：递归、master公式、外排、小和、逆序对）

5.归并排序(较快,稳定,对象排序最常用) 1.归并排序: 1.将数组分为两个数组,将两个数组排序后合并;2.子数组的排序可以递归调用归并排序(也可规模较小时用插入排序) 归并分为 mergeSort()分的过程和merge()合的过程。 mergeSort()分将一个数组均分成左边和右边，左边和...

排序算法

2021-02-25

0 546

希尔排序（插排的优化）

4.希尔排序（相对较快,不稳定）思想：先确定一个间隔，我们从0开始，每经过一个间隔取一个数，把这些数分成一组，把这一组数用插入排序排好。然后将间隔逐渐变小，循环该过程。为什么比插入排序的效率高？因为如果1在比较后面的位置，它要排到最前面必须经过很多次交换。如果用希尔排序，因为有间隔，所以只需...

排序算法

2021-02-25

0 638

插入排序（简单排序中最常用，必掌握）

3.插入排序(小样本,基本有序时最快;稳定) 插入排序在工业和实际中应用比较多,当样本量小于60且基本有序时使用; 使用插入排序,可以保证排序数组的稳定性.经常在归并排序和快排中子数组规模小时使用. 普通插入排序: //插入排序(相对冒泡和选择较好,但时间复杂仍为n**2,空间为1,稳定) //思想...

排序算法

2021-02-25

0 512

选择排序与冒泡排序

选择排序与冒泡排序的使用很少，但依旧经典。 1.选择排序(慢,不稳定) //选择排序(时间复杂度为N**2,空间为1,不稳定) //每次找到最小的放在最前面,每次循环比较n次,换一次 for (int i = 0; i < arr.length - 1; i++) { ...

排序算法

2021-02-25

0 488

排序算法中的通用函数与对数器

0.排序相关辅助函数(重点:对数器) 1.简单排序的交换函数[位运算版] (注意:位运算优先级较低,复合运算的时候需要加上小括号) 位运算一般较快.（但特殊情况自己与自己交换会变为0，如快排和堆排） public static void swap(int[] arr, int i, int j) {...

排序算法算法总结

2021-02-25

1 414