[关闭]
@zero1036 2017-04-10T07:43:00.000000Z 字数 2159 阅读 1577

插入排序分析与Java实现

Java-Base 数据结构与算法


概述

插入排序的3中实现:

  1. 直接插入排序
  2. 二分法插入排序
  3. 希尔排序

直接插入排序

操作:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置,直到全部插入排序完为止。

例如:
array = [1,3,5,7,9,4,8],已排序区块是[1,3,5,7,9],待排序元素是4
41比较,结果不变:[1,3,5,7,9,4]
43比较,结果不变:[1,3,5,7,9,4]
45比较,插入到5位置:[1,3,4,5,7,9]

排序稳定:是。当比较元素相等时,右元素插入到左元素右方,可保持稳定。

二分法插入排序

二分法插入排序 , 即查找插入点的位置, 可以使用 折半查找 .

这样可以 减少比较 的次数, 移动的次数 不变,

时间复杂度仍为

;

JDK实现源码:Binarysort

JDK1.8默认排序方式Timsort,Binary Insertion Sort是Timsort的Run排序方法。Binarysort实现要点:

1、 Binarysort要求首先找出数组(此数组即分区)中从0位开始连续升序区块,及区块下一位元素pivot;

例:[1,3,5,7,9,4,8] 的起始连续升序区块是 [1,3,5,7,9],区块长度为5,即runLen;pivot是4

2、 通过二分法比较pivot与区分元素的升降序关系,计算pivot在区块中的位置;并插入到该位置,组成新的区块;

例:4在区块中[1,3,5,7,9],先比较5 > 4,是降序;再比较3 < 4,是升序,确认位置,通过native方法System.arraycopy()插入到区块中;

3、 再计算新区块与新pivot的位置关系,直到完成排序

4、 注意:以上升序的定义是Comparator.compare(右元素, 左元素) >= 0,反之为降序;非数值上的升降序。

源码:

  1. /**
  2. * 二分法插入排序
  3. * 排序结果为升序,Comparator.compare(右, 左) >= 0
  4. * 例如:假设目标数组a长度为10,数组头3位已经排好升序,所以
  5. * lo = 0
  6. * hi = 9 + 1
  7. * start = 3 (0 1 2位已排序,从第3位开始计算)
  8. * @param a 目标数组
  9. * @param lo 指定排序范围首个元素位置
  10. * @param hi 指定排序范围最后元素位置 + 1
  11. * @param start 从start位置开始计算排序,即lo到start部分不排序
  12. */
  13. private static <T> void binarySort(T[] a, int lo, int hi, int start,
  14. Comparator<? super T> c) {
  15. assert lo <= start && start <= hi;
  16. if (start == lo)
  17. start++;
  18. for ( ; start < hi; start++) {
  19. // 取出起始计算位置的元素,并记录临时对象
  20. T pivot = a[start];
  21. /*
  22. * 设置插入的边界位置(范围)
  23. * 左边界恒定为首个元素位置
  24. * 右边界根据起始位置递增
  25. * 例 [1,2,3,4,5,6....],执行结果依次为:[1,2,3],[1,2,3,4],[1,2,3,4,5]
  26. */
  27. int left = lo;
  28. int right = start;
  29. assert left <= right;
  30. /*
  31. * 通过n/2对折方法,找出起始位置start的元素pivot,在[lo, start)范围中的插入位置left,需要满足以下条件
  32. * pivot >= all in [lo, left).
  33. * pivot < all in [right, start).
  34. * 例:[1,3,5,7,9,4],pivot = 4,运算结果left = 2
  35. */
  36. while (left < right) {
  37. // 二进制右移一位获取中间值,例:1>>>1=0 2>>>1=1 3>>>1=1 4>>>1=2
  38. // 二进制右移方法,比n/2方法处理更简单
  39. int mid = (left + right) >>> 1;
  40. // 右边界起始元素与中间值比较
  41. // 若降序,则右边界为中间值
  42. if (c.compare(pivot, a[mid]) < 0)
  43. right = mid;
  44. // 若升序,则左边界为中间位置 + 1
  45. else
  46. left = mid + 1;
  47. }
  48. assert left == right;
  49. // 取得需要移位元素个数,The number of elements to move
  50. int n = start - left;
  51. // 通过System.arraycopy()置换元素位置
  52. switch (n) {
  53. case 2: a[left + 2] = a[left + 1];
  54. case 1: a[left + 1] = a[left];
  55. break;
  56. default: System.arraycopy(a, left, a, left + 1, n);
  57. }
  58. a[left] = pivot;
  59. }
  60. }

C++实现方法

  1. void BInsertSort(std::deque<int>& L) {
  2. for (std::size_t i=2; i<L.size(); ++i) {
  3. L[0] = L[i];
  4. int low = 1, high = i-1;
  5. //查找L[0]的位置
  6. while (low <= high) {
  7. int m = (low + high)/2;
  8. if (L[0] < L[m]) high = m-1;
  9. else low = m+1;
  10. }
  11. //把较大的向前移动
  12. for (int j=i-1; j>=high+1; --j) L[j+1] = L[j];
  13. L[high+1] = L[0];
  14. }
  15. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注