算法(1)二分查找、冒泡排序、选择排序、插入排序

vlambda
2020-04-09

算法(1)二分查找、冒泡排序、选择排序、插入排序

1.二分查找：每次在有序的数组砍一半，时间复杂度为O(log以n为底2的对数)。

2.冒泡排序：从0开始，0和1比较；1和2比较……，排出一个最大数在n-1位置上，再从0到n-2开始排序，时间复杂度为O(n的平方)。

public class Code_00_BubbleSort {
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
for(int end = arr.length - 1; end > 0; end--){
for(int i = 0; i < end; i++) {
if(arr[i] > arr[i+1]) {
swap(arr, i, i + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int top = arr[i];
arr[i] = arr[j];
arr[j] = top;
}
}

3.选择排序：从0开始依次和1、2……n-1比较，挑出一个最小的放在0上；再从1到n-1挑出一个最小的放在1上，时间复杂度为O(n的平方)。

import java.util.Arrays;
public class Code_02_SelectionSort {
public static void selectionSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
for(int i = 0; i < arr.length - 1; i++) {
int minindex = i;
for(int j = i + 1; j < arr.length; j++) {
minindex = arr[j] < arr[minindex] ? j : minindex;
}
swap(arr, i, minindex);
}
}
public static void swap(int[] arr, int i, int j) {
int top = arr[i];
arr[i] = arr[j];
arr[j] = top;
}
}

4.插入排序：就好像抓扑克一样，抓第一张，不排序；抓第二张，排序；抓第三张，把第三张扑克牌插入到前二张中。所以就是从前一个数排序开始，到前二个数排序，一直到前n个数排序。最好时间复杂度（已经排好序的）就是O(n)，最坏时间复杂度就是O(n的平方)。当数据不同从而产生的算法复杂度不同时，一律按最差的估计。