插入排序
原理
将给定的数组从第一位开始,遍历,每取一位都和她前面的元素比较,前面的大,就把他放到当前元素后边,不断向前,知道前面的元素比后面小。
时间复杂度
O(nn)
最好情况On
最坏情况O(nn)
空间复杂度
O(1)
代码
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int t;
for (int j = i; j >= 0; j--) {
if (j > 0 && arr[j - 1] > tmp) {
t = arr[j];
arr[j] = arr[j-1];
arr[j-1] = t;
} else {
arr[j] = tmp;
break;
}
}
}
System.out.println(Arrays.toString(arr));
}
可以化简为如下代码,不用特意进行交换,因为他每次往前飞,如果前面的都会覆盖当前的,每移动一次,覆盖一次,直到找到前面的元素比tmp小,则把那个元素赋值给tmp,这里可以用打断点追踪一下,很清晰,很巧妙!!!,思路起源于这篇博客,点击访问
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int t;
for (int j = i; j >= 0; j--) {
if (j > 0 && arr[j - 1] > tmp) {
arr[j] = arr[j-1];
} else {
arr[j] = tmp;
break;
}
}
}
System.out.println(Arrays.toString(arr));
}
或者,条件变一下, 原理大同小异,下面的其实把条件从if里面移动到while里了
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int insert = i;
while (insert>0 && tmp<arr[insert-1]){
arr[insert] = arr[insert-1];
insert--;
}
arr[insert] = tmp;
}
System.out.println(Arrays.toString(arr));
}
希尔排序
原理
直接插入排序其实是希尔排序gap步长为1的特例
时间复杂度
O(nlog n)
最好情况O(nlog n)
最坏情况O(n*log^2 n)
空间复杂度
O(1)
代码
public static void shellSort(int[] arr){
for (int gap = arr.length/2; gap >0 ; gap/=2) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
for (int j = i; j >= 0; j-=gap) {
if (j-gap >= 0 && tmp < arr[j - gap]) {
arr[j] = arr[j - gap];
} else {
arr[j] = tmp;
break;
}
}
}
}
}
或者
public static void shellSort(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int insert = i;
while (insert - gap >= 0 && tmp < arr[insert - gap]) {
arr[insert] = arr[insert - gap];
insert -= gap;
}
arr[insert] = tmp;
}
}
}
或者
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始的间隔取 n/2,然后每次减半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 使用插入排序对每个分组进行排序
for (int i = gap; i < n; i++) {
int tmp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
System.out.println(Arrays.toString(arr));
}