数据结构(十):直接插入排序

2018-03-01 11:16:03来源:https://www.jianshu.com/p/d62acb671366作者:林塬人点击

分享



直接插入排序是将未排序的数据插入至已排好序序列的合适位置
直接插入排序例子
流程:
首先比较数组的前两个数据,并排序
比较第三个元素与前两个排好序的数据,并将第三个元素放入适当的位置
  - 比较第四个元素与前三个排好序的数据,并将第四个元素放入适当的位置

举例:数组 int[] arr= { 25,11,45,26,12,78 };
第一趟排序:比较 25 11,位置互换,结果 { 11 25 45 26 12 78 }
第二趟排序:45 大于 11 25,位置不变
第三趟排序:26 大于 11 25,小于 45,将其插入 25 和 45 之间,结果 { 11 25 26 45 12 78 }
...
最终排序:{ 11 12 25 26 45 78 }

直接插入排序代码
int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// 直接插入排序
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j;
for (j = i - 1; j >= 0; j--) {
// 判断是否大于tmp,大于则后移一位
if (arr[j] > tmp) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = tmp;
}

直接插入排序性能
如果排序是随机的,那么根据概率相同原则,直接插入排序时间复杂度为 O(n²),相比冒泡排序和简单选择排序性能要好一些







最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台