基于 Java 8 实现的代码片段集合,可以在较短的时间内理解这些算法代码片段。每种算法都有简短且全面的分析助于理解。GitHub 项目地址:https://github.com/lxiaocode/TheAlgorithms

排序算法 - Sort

排序算法辅助方法

// a 小于 b ?
private static boolean less(Comparable a, Comparable b){
return a.compareTo(b) < 0;
}
// 交换 array[a] 和 array[b]
private static void exch(Comparable[] array, int a, int b){
Comparable tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
// 数组 array 是否已排序?
private static boolean isSort(Comparable[] array){
return isSort(array, 0, array.length);
}
// 数组 array 中 array[lo] 到 array[hi] 是否已排序?
private static boolean isSort(Comparable[] array, int lo, int hi){
for (int i = lo + 1; i <= hi; i++){
if (less(array[i], array[i - 1])) return false;
}
return true;
}
// 打印数组
private static void show(Comparable[] array){
Arrays.stream(array).forEach(System.out::println);
}

选择排序

/**
* 选择排序:
* 每次都会选定当前最小的元素,将其排序到左边。
*
* 算法分析:
* 交换次数 N
* 比较次数 (N-1)+(N-2)+(N-3)+...+2+1 = N(N-1)/2
*
* 特点:
* 运行时间和输入无关,为了找到当前最小元素需要扫描数组。
* 交换元素次数最少,每次交换都会确定一个元素,总共交换 N 次。
*
* @author lixiaofeng
* @blog http://www.lxiaocode.com/
*/
public static <T extends Comparable<T>> void sort(T[] array){
for (int i = 0; i < array.length - 1; i++){
int min = i;
for (int j = i + 1; j < array.length; j++){
if (less(array[j], array[min])) min = j;
}
exch(array, i, min);
assert isSort(array, 0, i);
}
assert isSort(array);
}
// less()、exch()、isSort() 见 “排序算法辅助方法”

插入排序

/**
* 插入排序:
* 假设左边的元素是已排序的,然后将右边的元素插入左边元素中适合的位置。
*
* 算法分析:
* 交换次数,最坏的情况 1+2+3+...+(N-1) = N(N-1)/2; 最好的情况(已排序) 0 不需要交换; 平均的情况 N(N-1)/4
* 比较次数,最坏的情况 1+2+3+...+(N-1) = N(N-1)/2; 最好的情况(已排序) N-1; 平均的情况 N(N-1)/4
*
* 特点:
* 插入排序对于有序(或部分有序)数组效率很高; 对于存在很多相同元素的数组也很有效; 也很适合小规模数组。
* 由此看出,插入排序的运行时间与输入有关。
*
* 倒置元素:
* 倒置指的是数组中两个顺序颠倒的元素,如[2,4,3,1] 2-1、4-3、4-1、3-1
* 插入排序中每一次交换都会消除一组倒置元素,当倒置元素为 0 这排序完成。
* 所以插入排序的交换次数 = 倒置元素数量;
* 倒置元素数量 <= 比较次数 <= 倒置元素数量 + 数组大小 + 1 (每次交换都会对应一次比较,还可能需要一次额外的比较)
*
* 优化:
* 插入有许多优化空间,如希尔排序就是基于插入排序实现的。
* 一种简单的优化就是,内循环中将较大的元素都向右移动而不总是交换两个元素(这样访问数组的次数就能减半)。
*
* @author lixiaofeng
* @blog http://www.lxiaocode.com/
*/
public static <T extends Comparable<T>> void sort(T[] array){
for (int i = 1; i < array.length; i++){
for (int j = i; j > 0 && less(array[j], array[j-1]); j--){
exch(array, j, j-1);
}
assert isSort(array, 0, i);
}
assert isSort(array);
}
// less()、exch()、isSort() 见 “排序算法辅助方法”

希尔排序

/**
* 希尔排序:
* 希尔排序基于插入排序的快速排序算法。
* 由于插入排序对于规模小的、接近有序的数组效率更高。
* 所以希尔排序将数组分成多个规模较小的数组使用插入排序,然后数组逐渐有序,最后使用插入排序进行排序。
*
* 算法分析:
* 希尔排序的算法分析非常复杂,但是可以确定的是算法性能取决于 h。
*
* 特点:
* 希尔排序将数组以 h 的间隔分为多个子数组,然后使用插入排序将 h 个子数组独立地排序。
* 在排序之初,各个子数组都很短,排序之后子数组都是部分有序的,这两种情况都很适合插入排序。
* 子数组的有序程度取决于 h 的递增序列,所以算法的性能取决于 h。
* 但是有很多论文研究都无法证明某个 h 递增序列是 “最好的”。
* 在实际应用中,代码中的递增序列(1, 4, 13, 40, 121, 364, 1093, ...)基本就足够.
*
* h 有序数组:
* 希尔排序的思想就是使数组中任意间隔 h 的元素是有序的,这样的数组称为 h 有序数组。
*
* @author lixiaofeng
* @blog http://www.lxiaocode.com/
*/
public static <T extends Comparable<T>> void sort(T[] array){
int n = array.length;
int h = 1;
while (h < n/3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093
while (h >= 1){
for (int i = h; i < n; i++){
for (int j = i; j >= h && less(array[j], array[j-h]); j -= h ){
exch(array, j, j-h);
}
}
h /= 3;
}
assert isSort(array);
}
// less()、exch()、isSort() 见 “排序算法辅助方法”

评论