企业网站本身应该就是企业( )的一部分,公司网站做优化,深圳注册公司在哪里注册,企业软件定制开发报价内容目录
1. 选择类排序 1.1 直接选择排序1.2 堆排序 2. 交换类排序 2.1 冒泡排序2.2 快速排序 3. 插入类排序 3.1 直接插入排序3.2 希尔排序 4. 其它排序 4.1 归并排序4.2 基数排序/桶排序
排序 1. 选择类排序 选择类排序的特征是每次从待排序集合中选择出一个最大值或者最…内容目录
1. 选择类排序 1.1 直接选择排序1.2 堆排序 2. 交换类排序 2.1 冒泡排序2.2 快速排序 3. 插入类排序 3.1 直接插入排序3.2 希尔排序 4. 其它排序 4.1 归并排序4.2 基数排序/桶排序
排序 1. 选择类排序 选择类排序的特征是每次从待排序集合中选择出一个最大值或者最小值。 1.1 直接选择排序
原理两层循环外层循环标记从哪开始遍历待排序数组内层循环标记当前正在比较的元素。每次内层循环选出一个最小值/最大值。
ADL代码 复杂度
1.2 堆排序
原理堆排序在逻辑上使用完全二叉树的结构分为大顶堆和小顶堆两类即根结点为最大值的二叉树和根节点为最小值的二叉树。在物理结构上一般使用数组来实现完全二叉树。以大顶堆为例对待排序数组进行排序主要需要完成两个操作
在待排序数组上构造大顶堆。从堆中取出最大值并调整堆使其根节点仍然存储最大值。
可见使用堆排序也是每次从待排序集合中选择一个最大或者最小值因此其属于选择排序。 那么该如何实现堆排序的这两个操作呢
答案是需要一个Restore操作负责在其左右子树均已经为合法的堆的情况下将以R为根的二叉树重建为堆。
有了Restore操作之后就可以完成初始化整个堆和从堆中选择最大值或者最小值的操作了
初始化整个堆 从结点floor(n/2)开始直到结点1依次遍历对以每个结点为根的子树执行Restore操作。从堆中选出一个最大值将结点1与最后一个结点交换堆的大小减一对新的结点1执行Restore操作。
ADL代码
算法Restore(R, f, e. R)
/*R是存储完全二叉树的数组索引从1开始f是子树根节点索引e是R中元素数量*/
R1.[初始化当前需要对比的子树的根]i - f.
R2.[与左右子结点对比]// R[i]的右子结点就是R[2 * i 1]// 左子节点就是R[2 * i]WHILE i e / 2 DO(IF 2 * i 1 e AND R[2 * i 1] R[2 * i]child - 2 * i 1.ELSE child - 2 * i.IF R[child] R[i] THEN(R[child] - R[i].i - child.)ELSE(BREAK.))|算法HeapSort(R, n. R)
/**/
H1.[初始化堆]FOR i n/2 TO 1 STEP -1 DO(Restore(R, i, n. R).)
H2.[堆排序]e - n.FOR j n TO 2 STEP -1 DO(R[1] - R[j].e - e - 1.Restore(R, 1, e. R).)|复杂度时间复杂度O(nlogn)。空间复杂度O(1)。不稳定。
2. 交换类排序
2.1 冒泡排序
原理两层循环外层循环标记待排序数组的最后一个元素下标e内层循环负责比较当前元素i与其下一个元素j
如果i j交换ij。如果i j什么都不做。
这样内层循环遍历到e此时e一定存储的是从1到e中的最大元素。
ADL代码 扩展看一下对冒泡排序的改进p237。改变了最好情况下的时间复杂度。
复杂度O(n2)。O(1)。稳定。
2.2 快速排序
原理快速排序基于一种自顶向下分治的思想步骤如下
如果待排序数组为空或者只剩下一个元素直接返回从待排序数组中任意选取一个元素将比这个元素小的元素交换到数组的左边比这个元素大的元素交换到数组的右边这样就得到了两个子数组。分别对两个子数组进行以上操作。
可以看到这个算法适合使用递归来实现。
算法的关键问题和步骤在于如何高效的把小的元素交换到右边把大的元素交换到左边
决定算法时间复杂度的步骤是如何从待排序数组中选择一个元素使其尽量把原数组划分为等长的子数组
扩展看一下对快速排序的改进p244使用随机数算法选取基准元素。
ADL代码
算法Partition(R, m, n. j)
/*负责从子数组[Rm, Rn]中选择一个基准元素并把比它小的元素交换到数组的右边比它大的元素交换到数组的左边。*返回值j是基准元素的下标。*/
P1.[选取一个基准元素]base - R[m].
P2.[交换]left - m 1. right - n.WHILE left right DO(IF (R[left] base R[right] base) THEN(R[left] - R[right].left - left 1.right - right - 1.) ELSE IF R[left] base THENleft - left 1.ELSEright - right - 1.)
P3. [返回基准元素]IF R[left] base(R[left - 1] - R[m].j - left - 1.)ELSE(R[left] - R[m].j - left.)|算法QSort(R, m, n. R)
Q1. [递归出口]
IF (m n || m n) RETURN.
Q2. [划分数组]Partition(R, m, n. j).
Q3. [递归]QSort(R, m, j - 1. R).Qsort(R, j 1, n. R).|复杂度
3. 插入类排序
3.1 直接插入排序
原理两层循环第一层循环标记前k个已经排好序的元素的下一个元素i第二层循环将i插入到前k个元素中使前k1个元素有序。
ADL代码 复杂度复杂O(n2)最好情况下下O(n)。空间O(1)
3.2 希尔排序
原理直接插入排序的性能与待排序数组本身的**”有序度“高度相关原数组越有序时间复杂度就越接近O(n)原数组越无序时间复杂度越接近O(n2)。特别是远距离的逆序对比近距离的逆序对会显著增加比较次数**。
例如下面这个数组(2, 1)这个逆序对需要比较101次才能调整有序
[..., 0, 2, ...100个元素..., 1, ...]而下面这个数组(2, 1)这个逆序对只需要比较11次。
[..., 0, 2, ...10个元素..., 1, ...]那么为了尽量减少原数组中远距离的逆序对需要直接在大的步长的子数组中进行排序
例如假设原数组有1000个元素那么可以先选取步长为100将如下子数组单独进行直接插入排序
// 这里 子数组中的数字是下标而非元素的值
[1, 101, 201, ..., 901],
[2, 102, 202, ..., 902],
[3, 103, 203, ..., 903],
...
[100, 200, 300, ..., 1000]之后逐步减少步长然后进行排序直到最后步长为1
[1, 2, 3, ..., 1000] // 退化为原始的直接插入排序这样最后原数组会完全有序。
ADL代码 4. 其它排序
4.1 归并排序
原理类似快速排序归并排序也利用了分而治之的思想但是它是自底向上分治。步骤如下
如果待排序的数组为空或者大小为1直接返回将数组从中间分开对两个子数组分别进行以上操作这时两个子数组已经有序对两个子数组进行归并然后返回
ADL代码
算法Merge(R, t, m, n. X)
/**/建立X。算法MSort(R, m, n. R)
/**/
M1.[递归出口]IF m n OR m n THENRETURN.
M2.[划分数组]mid - (m n) / 2.MSort(R, m, mid. R).Msort(R, mid 1, n. R).
M3.[归并]Merge(R, m, mid, n. R).|
时间复杂度Onlogn
4.2 基数排序/桶排序
不常考了解即可。可能考简答题。
