Java 理论概念·经典排序算法
经典排序算法
重温排序算法，动画详见：Magicsort
插入排序
插入排序是一种简单的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序算法的运作如下：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描，如果该元素大于新元素，将该元素移到下一位置。
- 重复步骤 2，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后。
- 重复步骤 2~3，直到完成排序。
插入排序平均时间复杂度 O(n^2)，在最好情况下复杂度为 O(n)，在最坏情况下复杂度为 O(n^2)。
经典插入算法
经典插入算法：将数列分为有序区和无序区两部分，在每轮循环中从无序区选择一个最小值并入有序区，新增一位有序区同时减少一位无序区，n – 1 轮排序后全部变为有序区，从而完成排序。
public class InsertSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
insertSort(array);
for (int value : array) {
System.out.print(value + " ");
}
}
/**
* 插入排序
*
* @param array 待排序数组
*/
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 待插入的元素
int needInsert = array[i];
// 开始比较的索引
int index = i - 1;
while (index >= 0 && array[index] > needInsert) {
// 将该位置的元素进行后移
array[index + 1] = array[index];
// 再比较该位置前一个元素
index--;
}
// 当前位置满足条件
array[index + 1] = needInsert;
}
}
}二分插入算法
二分插入算法：查找插入位置时使用二分查找的方式，在插入值之前，先在有序区中找到待插入值需要比较的左边界，在数据长度较大时，可以有效减少每轮排序中的查找插入位置的次数。
public class InsertSort {
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 待插入的元素
int needInsert = array[i];
// 左右边界
int left = 0;
int right = i - 1;
// 找到待插入数据的合适位置
while (left <= right) {
int middle = (left + right) / 2;
if (needInsert < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
// 将右边比待插入数据大的数都右移一位
for (int j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
// 当前位置满足条件
array[left] = needInsert;
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
