选择排序：首先找到数组中最小的那个元素，其次将它和数组第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换。
-
插入排序：遍历数组（原址排序），将每一个数插入到之前排序好了的部分数组中的适当的位置，并将从 要插入的位置的右边 到 当前遍历到的位置 之间的数右移一位（参考以下例子）（具体实现是将遍历到的数 与 左边（左边部分数组已经是有序的）的数进行比较 如果不符合顺序就交换，如果符合就到达了适当的位置）
-
具体例子:图表演示
图片.png
-
-
希尔排序(改进的插入排序算法, 将移动间隔增加为一个比较大的数, 用1,4,13,40.... 3n + 1, 中较大的一个数, 然后递减为递增数组中较小的一个数,直至为1)
- 例子(暂无)
-
归并排序
- 自顶向下排序
(加粗表示当前操作的部分)
图片.png - 自下向上排序
加粗表示当前操作部分
图片.png - 归并排序的一些改进建议:
- 对于已经足够小的数组, 用别的排序方法(例如选择排序), 有助于提高算法性能
- 测试数组是否有序, 即测试要归并的两个数组的 前一个数组的最后一个小于后一个数组的最前一个.
- 不将元素复制到辅助数组, 而是通过归并排序到一个新的数组,然后再归并排序回来原来的数组(如此来回切换), 来使得复制数组的花销变小.
- 自顶向下排序
-
快速排序
- 基本思想:
- 先使数组大致有序, 然后对小数组继续递归使用 大致排序 ,直到最后剩下一个元素
- 第一种实现: 从数组往右遍历,如果遇到比要对比的数小或者等于的数, 较小数组index_1+1，遍历数组的index_0暂时不变，然后交换 arr[index_1]、arr[index_0] 。index_0再+1。如果遇到比要对比的数大的数，index_0 + 1, index_1 不变。直到遍历完数组，最后交换arr[0]、arr[index_1]
- 第二种实现：从数组往右遍历，直到遇到比要对比的数大的数停止，当前下标 index_0，然后从右往左遍历数组，直到遇到比要对比的数小的数停止，当前下标index_1，交换arr[index_0]、arr[index_1]。直到index_0>=index_1，最后交换arr[index_1]、arr[0]
- 快速排序的几个注意点
- 原地切分
- 别越界（如果要切分的元素是数组中最大的或者最小的，别让下标跑到数组外面）
- 保存随机性
- 终止循环的确定性
- 处理重复值情况
- 终止递归
- 提高性能的一些常用建议
- 对于小规模数组，使用其他排序方法
- 对于重复元素特别多情况，可以采用三切法，将元素分为小于、等于、大于三部分
- 基本思想:
-
优先队列--基于堆数据结构
- 堆数据结构的特点
* 使用数组实现即可,不使用第一个位置 arr[0], 基于完全二叉树 - 维护堆的特性:
- 上升:一个堆底的元素,上升,直到遇到一个比他大的父元素
- 下沉:一个堆顶的元素,下沉(和较大的子节点交换),直到遇到两个比他小的子节点
- 实现优先队列的两个关键操作
- 插入一个元素: 将新元素放置堆的末尾, 然后使用上升将该元素放置适合的位置
- 删除一个元素: 将堆顶的元素删除,然后将堆末尾的元素放置堆顶, 然后使用下沉, 将该元素放置适合的位置
- 使用堆进行排序--堆排序
- 堆数据结构的特点
-
排序的思考
- 将各种数据排序（通过引用）
- 如何选择排序算法
-
几个注意的地方:
- 多叉堆
- 适当加入调整数组大小的逻辑, 以防止出现下标溢出
- 元素不可变性: 保证元素放入堆后, 无法改变其值
- 通过使用索引(比如Integer类型), 快速对元素进行操作(虽然会花费额外的空间).但是只对索引进行操作,不管插入. 删除. 交换. 等速度会快很多
初级排序算法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 某次二面时，面试官问起Js排序问题，吾绞尽脑汁回答了几种，深感算法有很大的问题，所以总计一下！ 排序算法说明 （1...
- 人丑就得多读书，最近不得不承认，我也得多读书，读书就得多总结，不然会忘。 今天是Christmas Eve(写完估...
