插入排序算法思想
将第N个数插入到有序的[0...N-1]里,因为[0...N-1]已经有序,从第N个元素开始依次相互比较,发现后者比前者大就交换。
插入排序算法实现
public static void main(String[] args) {
int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
int[] insertSort = insertSort(arr);
for (int i : insertSort) {
System.out.print(i + " ");
}
System.out.println();
int[] insertSortByChange = insertSortByChange(arr);
for (int i : insertSortByChange) {
System.out.print(i + " ");
}
}
/**
* 插入排序
*
* @param arr
* @return
*/
private static int[] insertSort(int[] arr) {
if (arr.length == 0) return null;
if (arr.length == 1) return arr;
int N = arr.length;
for (int i = 1; i < N; i++) {
int j;
//这个是我的实现思路:主要是用第i个和前面i-1个比较发现比自己大的就把该元素向右移动一个位置,
// 直到没有比自己大就跳出,然后把自己放入当前位置+1里
int temp = arr[i];
for (j = i - 1; j >= 0; j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = temp;
}
return arr;
}
/**
* 通过交换的方式 推荐使用
*
* @param arr
* @return
*/
private static int[] insertSortByChange(int[] arr) {
if (arr.length == 0) return null;
if (arr.length == 1) return arr;
int N = arr.length;
for (int i = 1; i < N; i++) {
int j;
// 算法关键:第i个和前面i-1个比较,发现比自己大就交换,
// i-1和i-2比较发现比自己大就交换.........否则就退出
for (j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
} else {
break;
}
}
}
return arr;
}
算法复杂度
- 平均时间算法复杂度为O(N^2)
- 最坏时间复杂度为O(N^2)
- 最好时间复杂度为O(N)
- 空间复杂度为O(1) 不需要额外空间
算法稳定性
1.这个算法是稳定的,不会因为移动影响两个相同元素的位置
想看更多完整版请点击:插入排序