基本排序算法 - java

• Z时代
• 2024-01-10
• 分类：综合

一，概览

public interface Sort {
    default boolean less(int[] a,int i ,int j){
        return a[i] < a[j];
    }
    default boolean more(int[] a,int i ,int j){
        return a[i] > a[j];
    }
    default void exch(int[] a,int i ,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    void sort(int[] a);
}

1、插入排序

基本原理：在一个有序序列中，插入一个新的元素，使插入后的数据依旧有序。

即，a[0..i-1] 有序，将a[i] 插入适当的位置，使 a[0..i] 有序。

public class InsertSort implements Sort {
    @Override
    public void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j >= 1 && less(a, j, j - 1); j--) {
                exch(a, j, j - 1);
            }
        }
    }
}

2、希尔排序

基本原理：是插入排序的改进算法，通过增加交换元素之间的步长，来减少交换次数。

public class ShellSort implements Sort {
    @Override
    public void sort(int[] a) {
        int h = 1;
        while (h * 3 + 1 < a.length) {
            h = h * 3 + 1;
        }
        while (h>=1){
            for (int i = h; i < a.length; i += h) {
                for (int j = i; j >= h && less(a, j, j - h); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}

3、归并排序

基本原理：将两个有序数组合并，使合并的数组依旧有序。

public class MergeSort implements Sort {
    @Override
    public void sort(int[] a) {
        int[] aux = new int[a.length];
        sort(a, 0, a.length - 1, aux);
    }
    public void sort(int[] a, int lo, int hi, int[] aux) {
        if (lo >= hi) {
            return;
        }
        int mid = (hi - lo) / 2 + lo;
        sort(a, lo, mid, aux);
        sort(a, mid + 1, hi, aux);
        merge(a, lo, mid, hi, aux);
    }
    public void merge(int[] a, int lo, int mid, int hi, int[] aux) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = a[i];
        }
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                a[k] = aux[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(aux, i, j))
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
    }
}

源码地址

参考资料：算法4

以上是 基本排序算法 - java 的全部内容， 来源链接： utcz.com/z/395017.html