一、选择排序 Selection Sort
算法思想：比较简单，请看代码理解
复杂度分析：O(N^2)
public static <E> void selectionSort(E[] arr, int n, Compare<E> compare) {
for (int i = 0; i < n - 1; i++) {
int temp = i;
for (int j = i + 1; j < n; j++) {
if(compare.compare(arr[j], arr[temp]) < 0)
temp = j;
}
E exchange = arr[i];
arr[i] = arr[temp];
arr[temp] = exchange;
}
}
二、冒泡排序（+优化）
优化思路：记录最后一次交换元素的位置，当下一此遍历到这里时，后面的内容就可以不用再去遍历比较了；
数组顺序越趋近排序顺序，性能越好（整体比插入排序弱。）
复杂度分析：
- 未优化前：O(N^2)
- 优化之后：最坏O(N^2)；最好O(N)
import java.util.Comparator;
public class BubbleSort {
public static <E> void bubbleSort(E[] arr, Comparator<E> comparator) {
// 记录最后一次交换的位置，初始值为末尾元素
int lastChange = arr.length - 1;
int recordChange = lastChange;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < lastChange; j++) {
if(comparator.compare(arr[j + 1], arr[j]) < 0) {
swap(arr, j, j + 1);
recordChange = j;
}
}
// 提示下一次遍历遍历到此就OK了
lastChange = recordChange;
}
}
public static <E> void swap(E[] arr, int first, int last) {
E exchange = arr[first];
arr[first] = arr[last];
arr[last] = exchange;
}
public static void main(String[] args) {
Integer[] arr = {1,3,7,0,7,5,3,2,8,5,7,0,9,0,3,5,7,8,2,3,};
bubbleSort(arr, (a, b) -> b - a);
for (Integer integer : arr) {
System.out.print(integer + ", ");
}
}
}
三、插入排序 Insertion Sort（+优化）
思想：以升序为例，从第二个位置开始，将当前索引值保留一份，递归式的与前一个进行比较，如果前一个值比当前值大，则将前一个
值复制到当前位置....直到前一个值小于当前的值，此时将保留的值保存到此位置！
复杂度分析：
- 最坏的情况：O(N^2)
- 最好的情况：近乎O(N)
适用场景：数组顺序越趋近排序顺序，性能越好
import java.util.Comparator;
public class InsertionSort {
public static <E> void insertionSort(E[] arr, Comparator<E> comparator) {
for (int i = 0; i < arr.length; i++) {
E exchange = arr[i];
int j = i;
for (; j > 0 && comparator.compare(exchange, arr[j - 1]) < 0 ; j--) {
arr[j] = arr[j - 1];
}
arr[j] = exchange;
}
}
public static void main(String[] args) {
Integer[] arr = {9, 0, 9, 0, 3, 6, 9, 1, 4, 3, 9, 6, 3, 7, 2, 0, 1, 2, 8};
insertionSort(arr, (a, b) -> a - b);
for (Integer integer : arr) {
System.out.print(integer + ", ");
}
}
}
折半查找法,中间位置的索引采用向上取整的方式。
import java.util.Comparator;
public class HalfSort {
public static <E> void halflSort(E[] arr, Comparator<E> comparator) {
// 折半查找法
for (int i = 0; i < arr.length; i++) {
E exchange = arr[i];
int from = findPlace(arr, exchange, 0, i, comparator);
move(arr, exchange, from, i);
}
}
// 利用二分法找到该插入的位置
public static <E> int findPlace(E[] arr, E exchange, int left, int right, Comparator<E> comparator) {
while (true) {
// 终止条件
if(left + 1 == right) {
if(left == 0 && comparator.compare(exchange, arr[0]) < 0)
return left;
return right;
}
// middle就是当前位置,向上取整
int middle = (int)Math.ceil((left + right ) / 2.0);
if(comparator.compare(exchange, arr[middle]) < 0) {
right = middle;
} else if(comparator.compare(exchange, arr[middle]) > 0) {
left = middle;
} else
return middle;
}
}
// 根据当前遍历的位置以及需要插入的位置进行交换。
public static <E> void move(E[] arr, E exchange, int from, int to){
for (int i = to; i > from ; i--) {
arr[i] = arr[i - 1];
}
arr[from] = exchange;
}
public static void main(String[] args) {
Integer[] arr = {0,1,0,7,8,3,1,6,8,3,1,2,0,3,4,6,8,2,1,4,8,9,3,0};
halflSort(arr, (a, b) -> a - b);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ", ");
}
}
}
四、希尔排序
希尔排序是对插入排序的深层次优化,
缩小增量排序,(大致过程自行百度)
整体思想就是让数组逐渐趋近于有序化，
public final class ShellSort {
public static void sort(Comparable[] arr){
int n = arr.length;
// 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) {
// h-sort the array
for (int i = h; i < n; i++) {
// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
Comparable e = arr[i];
int j = i;
for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h)
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
}
}
