[数据结构与算法]Java排序算法

一、归并排序

public class MergeAlgorithm {

    public int[] sort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            sort(a, low, mid);
            sort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
        return a;
    }

    private void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= high) {
            temp[k++] = a[j++];
        }
        for (int x = 0; x < temp.length; x++) {
            a[x + low] = temp[x];
        }
    }
}

二、堆排序

public class HeapAlgorithm {

    public static void myHeapSort(int[] arr) {
        int i;
        int len = arr.length;
        for (i = len / 2 - 1; i >= 0; i--) {
            adjustment(arr, i, len);
        }
        for (i = len - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjustment(arr, 0, i);
        }
    }

    private static void adjustment(int[] arr, int pos, int len) {
        int child = 2 * pos + 1;
        if (child + 1 < len && arr[child] > arr[child + 1]) {
            child++;
        }
        if (child < len && arr[pos] > arr[child]) {
            int temp = arr[pos];
            arr[pos] = arr[child];
            arr[child] = temp;
            adjustment(arr, child, len);
        }
    }
}

三、基数排序

public class BasicSortAlgorithm {

    public void basicSort(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        int times = 0;
        while (max > 0) {
            max = max / 10;
            times++;
        }
        List<ArrayList> queen = new ArrayList<>();
        for (int i = 0; i < 1; i++) {
            ArrayList q = new ArrayList();
            queen.add(q);
        }
        for (int i = 0; i < times; i++) {
            for (int j = 0; j < a.length; j++) {
                int x = a[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList q = queen.get(x);
                q.add(a[j]);
            }
            int count = 0;
            for (int z = 0; z < 10; z++) {
                while (queen.get(z).size() > 0) {
                    ArrayList<Integer> c = queen.get(z);
                    a[count] = c.get(0);
                    c.remove(0);
                    count++;
                }
            }
        }
    }
}

四、冒泡排序

public class BubbleSortAlgorithm {
    public void bubbleSort(int[] array) {
        int t = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                }
            }
        }
    }
}

五、希尔排序

public class ShellAlgorithm {
    public void shellSort(int[] arr) {
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    arr[j + step] = arr[j];
                }
                arr[j + step] = arr[j];
            }
        }
    }
}