经典排序算法及其 Java 实现

摘要：冒泡排序插入排序选择排序堆排序父节点索引尾节点索引归并排序快速排序附录交换方法基于策略模式的主程序实现定义一个数组构造函数初始化数组遍历数组中每一个元素展示

「博客搬家」  原地址: 简书  原发表时间: 2017-08-17

网上有很多排序算法的总结，不过有很多缺点，比如有些根本就是错的，无法通过测试用例，有些过于冗长。所以我总结了一套短小精悍的 Java 实现，经测试，该套实现可通过牛客网的关于此的所有测试用例。

public class BubbleSort implements KySort {
    public void kySort(int[] a, int size) {
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }
}

public class InsertSort implements KySort {
    public void kySort(int[] a, int size) {
        for (int i = 1; i < size; i++) {
            int temp = a[i];
            int j = i;
            while (j > 0 && a[j - 1] > temp) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
        }
    }
}

public class SelectSort implements KySort {
    public void kySort(int[] a, int size) {
        for (int i = 0; i < size - 1; i++) {
            int min = i;
            for (int j = i + 1; j < size; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            if (i != min) {
                swap(a, i, min);
            }
        }
    }
}

public class HeapSort implements KySort {
    public void kySort(int[] a, int n) {
        for (int i = n / 2; i >= 0; i--) {
            heapAdjust(a, i, n - 1);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(a, 0, i);
            heapAdjust(a, 0, i - 1);
        }
    }

    /**
     * @param index 父节点索引
     * @param n     尾节点索引
     */
    private void heapAdjust(int[] a, int index, int n) {
        int temp = a[index];
        for (int child = index * 2 + 1; child <= n; child = index * 2 + 1) {
            if (child < n && a[child] < a[child + 1]) {
                child++;
            }
            if (temp > a[child]) break;
            a[index] = a[child];
            index = child;
        }
        a[index] = temp;
    }
}

public class MergeSort implements KySort {
    public void kySort(int[] a, int size) {
        sort(a, 0, size - 1, new int[a.length]);
    }

    private void sort(int[] a, int left, int right, int[] temp) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        sort(a, left, mid, temp);
        sort(a, mid + 1, right, temp);
        merge(a, left, mid, right, temp);
    }

    private void merge(int[] a, int left, int mid, int right, int[] temp) {
        int k = left;
        int i = left;
        int j = mid + 1;

        while (i <= mid && j <= right) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }

        while (left <= right) {
            a[left] = temp[left];
            left++;
        }
    }
}

public class QuickSort implements KySort {
    @Override
    public void kySort(int[] a, int size) {
        quickSort(a, 0, size - 1);
    }

    private void quickSort(int[] a, int left, int right) {
        if (right - left < 2) {
            if (a[left] > a[right])
                swap(a, left, right);
            return;
        }
        int p = middleBy3(a, left, right);

        quickSort(a, left, p - 1);
        quickSort(a, p + 1, right);
    }

    private int middleBy3(int[] a, int left, int right) {
        int p = (left + right) / 2;
        int end = right;

        if (a[left] > a[p]) swap(a, left, p);
        if (a[left] > a[right]) swap(a, left, right);
        if (a[p] > a[right]) swap(a, p, right);

        int temp = a[p];
        swap(a, p, right);

        while (true) {
            while (a[++left] < temp) ;
            while (a[--right] > temp) ;
            if (left >= right) break;
            else swap(a, left, right);
        }
        swap(a, left, end);
        return left;
    }
}

public class Util {
    public static void swap(int[] a, int i, int j) {
        int k = a[i];
        a[i] = a[j];
        a[j] = k;
    }
}

public class SortMain {
    private static KySort sorter;
    private int[] a;//定义一个数组

    private SortMain(int... values) {   //构造函数
        a = values;
    }

    public static void main(String[] args) {
        setSorter(new QuickSort());
        SortMain arr;
        arr = new SortMain(5, 4, 3, 2, 1, 0);
        arr.display();
        arr.kySort();
        arr.display();
        System.out.println("--------");
        arr = new SortMain(54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28);
        arr.display();
        arr.kySort();
        arr.display();
        System.out.println("--------");
        arr = new SortMain(32, 103, 24, 88, 95, 70, 97, 15, 102, 6, 79, 46, 51, 37, 93, 108, 9, 58, 53, 58, 79, 36, 58, 91, 78, 58, 61, 81);    //初始化数组
        arr.display();
        arr.kySort();
        arr.display();
    }

    private static void setSorter(KySort sorter) {
        SortMain.sorter = sorter;
    }

    private void display() {
        for (int i : a) {   //遍历数组中每一个元素
            System.out.print(i + " ");   //展示
        }
        System.out.println();
    }

    private void kySort() {
        sorter.kySort(a, a.length);
    }
}