初级排序算法

选择排序：首先找到数组中最小的那个元素，其次将它和数组第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换。

插入排序：遍历数组（原址排序），将每一个数插入到之前排序好了的部分数组中的适当的位置，并将从 要插入的位置的右边 到 当前遍历到的位置 之间的数右移一位（参考以下例子）（具体实现是将遍历到的数 与 左边（左边部分数组已经是有序的）的数进行比较 如果不符合顺序就交换，如果符合就到达了适当的位置）

• 具体例子:图表演示

  
  
  图片.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类型), 快速对元素进行操作(虽然会花费额外的空间).但是只对索引进行操作,不管插入. 删除. 交换. 等速度会快很多