工程排序总结(通用5篇)

工程排序总结 第1篇

简单选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

实现代码为：

对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况

堆排序首先就是建堆，然后再是调整。对于二叉树(数组表示)，我们从下往上进行调整，从第一个非叶子节点开始向前调整，对于调整的规则如下：

建堆是一个O(n)的时间复杂度过程，建堆完成后就需要进行删除头排序。给定数组建堆(creatHeap)

①从第一个非叶子节点开始判断交换下移(shiftDown)，使得当前节点和子孩子能够保持堆的性质

②但是普通节点替换可能没问题，对如果交换打破子孩子堆结构性质，那么就要重新下移(shiftDown)被交换的节点一直到停止。

堆构造完成，取第一个堆顶元素为最小(最大)，剩下左右孩子依然满足堆的性值，但是缺个堆顶元素，如果给孩子调上来，可能会调动太多并且可能破坏堆结构。

①所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown）,不过需要注意此时整个堆的大小已经发生了变化，我们在逻辑上不会使用被抛弃的位置，所以在设计函数的时候需要附带一个堆大小的参数。

②重复以上操作，一直堆中所有元素都被取得停止。

而堆算法复杂度的分析上，之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换，每个个数最坏为logn个。这样复杂度就为O(nlogn)xxx的时间复杂度为O(n)+O(nlogn)=O(nlogn).

实现代码为：

工程排序总结 第2篇

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 源于优先级序列：第一阶段，add操作整体时间复杂度为O(nlog n)；若第一阶段采用自底而上构建堆，时间复杂度为O(n)；第二阶段remove_min操作整体时间复杂度为O(nlog n)，总体时间复杂度为O(nlog n)

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。

不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

时间复杂度：非常稳定

空间复杂度：O(1)

工程排序总结 第3篇

基数排序也是非比较的排序算法，又称卡片排序；

对每一位进行排序，从最低位开始排序，复杂度为O(kn), n为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序基于分别排序，分别收集，所以是稳定的。

MSD ：从高位开始进行排序 LSD ：从低位开始进行排序

排序方式：out-place

时间复杂度：

空间复杂度：O(n + k)

这三种排序算法都利用了桶的概念，

对桶的使用方法上有明显差异：

工程排序总结 第4篇

常见的综合排序：----------------------------------------------------------------------------Ⅰ 若数组长度很长，则在工程上：* 首先进行判断：是基本类型还是自定义类型** 如果为基础类型：则使用快速排序，因为不需要考虑数据稳定性** 如果为自定义类型，则使用的是归并排序，因为需要考虑数据稳定性----------------------------------------------------------------------------Ⅱ 若数组长度短，则直接使用插入排序，不管是基本数据类型还是自定义类型虽然插入排序时间复杂度为：O(N2)，但是在数据量很小的情况下，劣势不会有很大表现----------------------------------------------------------------------------数组长度小于60时，直接使用插入排序此时联系：快排和归并在数据量小的时候的优化

面试：为什么在综合排序中数据量小的部分选择使用插入排序答：虽然复杂度高，但是常数项很低，在数据量很小的情况下，劣势不会有很大表现只有在数据量很大的时候，常数项才可以被忽略，插入排序的劣势才表现出来

面试：为什么基本类型选择使用快排，而自定义类型选择归并答：考虑到的是数据稳定性问题，快排因为partition数据稳定性得不到保证而归并排序是可以设计为排序稳定性的

面试：数组中：将数组中奇数放左边，偶数放右边，要求原始数组相对次序不变，且时间复杂度为O(N)，空间复杂度为O(1)答：不能，因为此时奇数偶数也是一个0/1问题，对于快速排序中也是0/1标准，而快速排序的时间复杂度为O(NlogN)

0/1 stable sort很难

认识比较器的作用(stus,new IdAscendingComparator());Arrays方法可以传入一个数组和自定义的比较器

利用到比较器的集合：PriorityQueue TreeMap

工程排序总结 第5篇

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot），即枢纽元；

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），在这个分区退出之后，该基准就处于数列的中间位置，称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

排序方式：in-place

时间复杂度：

空间复杂度：