学什么专业可以做网站,一个网站建立团队大概要多少钱,中国教育建设协会网站,网页制作重庆列举几种基本的排序算法和排序思想
排序就是将一组对象按照某种逻辑顺序重新排列的过程。 一、选择排序
1、基本原理
最基本的排序#xff0c;每次都从原有数据中选择最小或最大的数组放入新数据集中
2、步骤(以从小到大为例)
首先#xff0c; 找到数组中最小的那个元素…列举几种基本的排序算法和排序思想
排序就是将一组对象按照某种逻辑顺序重新排列的过程。 一、选择排序
1、基本原理
最基本的排序每次都从原有数据中选择最小或最大的数组放入新数据集中
2、步骤(以从小到大为例)
首先 找到数组中最小的那个元素
其次 将它和数组的第一个元素交换位置 如果第一个元素就是最小元素那么它就和自己交换 。
再次 在剩下的元素中找到最小的元素 将它与数组的第二个元素交换位置。 如此往复 直到将整个数组排序。
这种方法叫做选择排序 因为它在不断地选择剩余元素之中的最小者
3、特点
复杂度 O(n2)
运行时间和输入无关
数据移动是最少的 二、插入排序
1、基本原理
为了给要插入的元素腾出空间 我们需要将其余所有元素在插入之前都向右移动一位。 这种算法叫做插入排序
2、特点
插入排序所需的时间取决于输入中元素的初始顺序
插入排序对于实际应用中常见的某些类型的非随机数组很有效
3、几种典型的部分有序的数组 1数组中每个元素距离它的最终位置都不远 2一个有序的大数组接一个小数组 3 数组中只有几个元素的位置不正确。 插入排序对这样的数组很有效 而选择排序则不然
4、提升方法
要大幅提高插入排序的速度并不难 只需要在内循环中将较大的元素都向右移动而不总是交换 两个元素 这样访问数组的次数就能减半 三、希尔排序
1、基本原理
希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。
这样的数组被称为 h 有序数组。
2、h有序数组 一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组 。
在进行排序时如果 h 很大 我们就能将元素移动到很远的地方为实现更小的 h 有序创造方便。
用这种方式对于任意以 1 结尾的 h 序列都能够将数组排序。
3、实现方法
对于每个 h 用插入排序将 h 个子数组独立地排序。
但因为子数组是相互独立的 一个更简单的方法是在 h- 子数组中将每个元素交换到比它大的元素之前去 将比它大的元素向右移动一格 。
只需要在插入排序的代码中将移动元素的距离由 1 改为 h 即可。
这样 希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。 四、归并排序
1、基本原理
两个有序的数组归并成一个更大的有序数组。
2、基本方法
要将一个数组排序可以先递归地将它分成两半分别排序然后将结果归并起来。
实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中
3、特点
它能够保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比
它的主要缺点则是它所需的额外空间和 N 成正比
4、几种方法
原地归并
是将两个不同的有序数组归并到第三个数组中
自顶向下
基于分支思想如果能将两个子数组排序就能够通过归并两个子数组来将整个数组排序
自底向上
先归并那些微型数组然后再成对归并得到的子数组直到将整个数组归并在一起。这种实现方法比标准递归方法 所需要的代码量更少
5、局限性 1 归并排序的空间复杂度不是最优的 2在实践中不一定会遇到最坏情况 3除了比较算法的其他操作例如访问数组也可能很重要 4不进行比较也能将某些数据排序。 五、快速排序
1、基本原理
快速排序是一种常用的排序算法比选择排序快得多。
快速排序使用了DC。
2、基本步骤
首先从数组中选择一个元素这个元素被称为基准值pivot。
接下来找出比基准值小的元素以及比基准值大的元素被称为分区 partitioning
得到
1一个由所有小于基准值的数字组成的子数组
2基准值 3一个由所有大于基准值的数组组成的子数组
如果子数组是有序的就可以合并得到一个有序的数组左边的数组 基准值 右边的数组 对于包含两个元素的数组左边的子数组以及空数组右边的子数组只要对这两个子数组进行快速排序再合并结果就能得到有序数组 总结得到基本步骤
(1) 选择基准值。 (2) 将数组分成两个子数组小于基准值的元素和大于基准值的元素。 (3) 对这两个子数组进行快速排序
3、特点
快速排序的独特之处在于其速度取决于选择的基准值
在最糟情况下其运行时间为O(n2)。
平均情况下快速排序的运行时间为O(nlogn)
最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值快速排序的平均运行时间就将为O(nlogn)。快速排序是最快的排序算法之一也是DC典范。 六、优先队列
1、数据结构
一个合适的数据结构应该支持两种操作 删除最大元素和插入元素。这种数据类型叫做优先队列。
优先队列的使用和队列删除最老的元素以及栈删除最新的元素类似
2、排序方法
通过插入一列元素然后一个个地删掉其中最小的元素我们可以用优先队列实现排序算法。
堆排序就是基于堆的优先队列的实现。
3、二叉堆
数据结构二叉堆能够很好地实现优先队列的基本操作。
在二叉堆的数组中每个元素都要保证大于等于另两个特定位置的元素。
相应地这些位置的元素又至少要大于等于数组中的另两个元素以此类推
当一棵二叉树的每个结点都大于等于它的两个子结点时它被称为堆有序
4、优先队列排序
我们可以把任意优先队列变成一种排序方法。
将所有元素插入一个查找最小元素的优先队列然后再重复调用删除最小元素的操作来将它们按顺序删去。
用无序数组实现的优先队列这么做相当于进行一次选择排序
5、堆排序
堆排序可以分为两个阶段。
在堆的构造阶段中我们将原始数组重新组织安排进一个堆中
然后在下沉排序阶段我们从堆中按递减顺序取出所有元素并得到排序结果。
