排序算法总结

超、凢脫俗 2021-11-19 14:54 257阅读 0赞

2019-07-20

import java.net.Socket;
    import java.util.Arrays;
    import java.util.ConcurrentModificationException;
    
    /**
     * @ClassName SortDemo
     * @Author wangyudi
     * @Date 2019/7/20 14:44
     * @Version 1.0
     * @Description
     */
    public class SortDemo {
        /**
         * 选择排序:每次选择排列一个位置
         * 注意点：数组最后一个位置不需要选择
         * 每次和最小值进行比较
         *
         * @param a
         */
        public void selectSort(Comparable[] a) {
            if (a == null) return;
            int length = a.length;
            if (a.length == 0 || a.length == 1) return;
    
            int min = 0;//每次选择排序中，最小数的索引值
            for (int i = 0; i < length - 1; i++) {
                min = i;//用于记录最小值所在的索引
                for (int j = i + 1; j < length; j++) {
                    if (less(a[j], a[min])) min = j; //注意
                }
                exch(a, i, min);
            }
        }
    
        ;
    
        /**
         * 插入排序：将当前指针所指的元素插入到前面的排序数组中
         * 注意点：插入排序从索引为1 的元素开始插入排序
         *
         * @param arr
         */
        public void insertSort(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            for (int i = 1; i < length; i++) {
                for (int j = i; j > 0 && less(arr[j], arr[j - 1]); --j) {
                    exch(arr, j, j - 1);
                }
            }
        }
    
        /**
         * 希尔排序：将数组以h为间隔分为若干个数组；解决了插入排序中，交换次数过多的情况
         * 注意点：最后一次希尔排序h为1；
         *
         * @param arr
         */
        public void hillSort(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            int h = 1;
            while (h < length / 3) h *= 3;
            while (h >= 1) {
                for (int i = h; i < length; i++) {
                    for (int j = i; j > h - 1 && less(arr[j], arr[j - h]); j -= h) {
                        exch(arr, j, j - h);
                    }
                }
                h = h / 3;
            }
        }
    
        /**
         * 归并排序（递归）：将数组不断地等分，然后归并；
         * 归并：将两个有序的数组归并后任然是有序数组
         * 这里使用的是非原地归并，为了避免在归并排序中平频繁地创建数组，这里初始时创建了和输入数组一样大的数组
         *
         * @param arr
         */
        public void mergeSort(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            Comparable[] temp = new Comparable[length]; //用于归并的辅助数组
            mergeSortCore(arr, 0, length - 1, temp);
        }
    
        private void mergeSortCore(Comparable[] arr, int lo, int hi, Comparable[] temp) {
            if (lo >= hi) return;
            int mid = lo + (hi - lo) / 2;
            mergeSortCore(arr, lo, mid, temp);
            mergeSortCore(arr, mid + 1, hi, temp);
            merge(arr, lo, mid, hi, temp);
        }
    
        private void merge(Comparable[] arr, int lo, int mid, int hi, Comparable[] temp) {
            for (int i = lo; i <= hi; i++) {
                temp[i] = arr[i];
            }
            int p = lo;
            int q = mid + 1;
            for (int i = lo; i <= hi; i++) {
                if (p > mid) arr[i] = temp[q++];
                else if (q > hi) arr[i] = temp[p++];
                else if (less(arr[p], arr[q])) arr[i] = temp[p];
                else arr[i] = temp[q];
            }
        }
    
        /**
         * 归并排序（自下而上）：从11 22 44合并数组
         */
    
        public void mergeSort2(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            Comparable[] temp = new Comparable[length];
            for (int size = 1; size < length; size *= 2) { //遍历所有长度的子数组 1，2，4，8……
                for (int i = 0; i < length - size; i = i + 2 * size) {
        //遍历所有需要遍历的两个子数组
                    merge2(arr, i, i + size - 1, min(i + 2 * size - 1, length - 1), temp);
                }
            }
        }
    
        private int min(int a, int b) {
            return a < b ? a : b;
        }
    
        private void merge2(Comparable[] arr, int lo, int mid, int hi, Comparable[] temp) {
            for (int i = lo; i <= hi; i++) {
                temp[i] = arr[i];
            }
            int p = lo;
            int q = mid + 1;
            for (int i = lo; i <= hi; i++) {
                if (p > mid) arr[i] = temp[q++];
                else if (q > hi) arr[i] = temp[p++];
                else if (less(arr[p], arr[q])) arr[i] = temp[p];
                else arr[i] = temp[q];
            }
        }
    
        /**
         * 快速排序：选择排序数组中的一个数，然后对其进行分割
         */
        public void quickSort(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            quickSortCore(arr, 0, length - 1);
        }
    
        public void quickSortCore(Comparable[] arr, int lo, int hi) {
            if (lo >= hi) return;
            int mid = partition(arr, lo, hi);
            quickSortCore(arr, lo, mid - 1);
            quickSortCore(arr, mid + 1, hi);
        }
    
        /**
         * 将数组切分，并返回切分比较值所在的索引
         *
         * @param arr
         * @param lo
         * @param hi
         * @return
         */
        private int partition(Comparable[] arr, int lo, int hi) {
            Comparable v = arr[lo];
            int i = lo;
            int j = hi + 1;
            while (true) {
                //i指向数组范围内比基准数大的值，或者数组最后一个元素
                //j指向数组范围内比基准数小的值，或者数组第一个元素
                while (arr[++i].compareTo(v) <= 0) if (i == hi) break;
                while (arr[--j].compareTo(v) >= 0) if (j == lo) break;
                if (i >= j) break;
                exch(arr, i, j);
            }
            exch(arr, lo, j);
            return j;
        }
    
    
        /**
         * 三向切分 快速排序方法：适用于数组中有大量相同元素的排序算法
         * 将数组分为 小于 等于 大于三部分
         * partition3Way 需要两个指针和遍历指针
         */
        public void quickSort3Way(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            quickSort3WayCore(arr, 0, length - 1);
        }
    
        private void quickSort3WayCore(Comparable[] arr, int lo, int hi) {
            if (lo >= hi) return;
            int[] result = partition3Way(arr, lo, hi);
            quickSort3WayCore(arr, lo, result[0] - 1);
            quickSort3WayCore(arr, result[1] + 1, hi);
    
        }
    
        private int[] partition3Way(Comparable[] arr, int lo, int hi) {
            int lp = lo;//指向小于部分尾部
            int gp = hi;//指向大于部分头部
            Comparable value = arr[lo];
            int i=lo+1;
            while(i<=gp) { //i是用于遍历数组来切分的指针变量
                int cmp = arr[i].compareTo(value);
                if (cmp > 0) {
        //arr[i]比较大
                    exch(arr, i, gp--);
                } else if (cmp < 0) {
                    exch(arr, lp++, i++); //注意，这里会调节数组
                } else{
         
    　　　　　　　　　 i++;
    　　　　　　　}
            }
            int[] result = new int[]{lp, gp};
            return result;
        }
    
        /**
         * 堆排序：用一个数组实现最大堆（最大优先队列）
         * 注意点：保存数据的第一个索引没有使用
         * 这里实现的堆排序中，使用了数组的第一个元素 k 2k+1 2k+2
         *
         * @param arr
         */
        public void heapSort(Comparable[] arr) {
            if (arr == null) return;
            int length = arr.length;
            if (arr.length == 0 || arr.length == 1) return;
            //堆有序化， 从倒数第二排开始 sink
            for (int i = (length - 1) / 2; i >= 0; i--) {
                sink(arr, i, length - 1);
            }
            //排序，将堆顶最大的数交换到数组的末尾，然后堆顶数据sink
            int last = length - 1;
            while(last!=0){
                exch(arr,0,last--);
                sink(arr,0,last);
            }
        }
    
        private void sink(Comparable[] arr, int k, int last) {
            while ((2 * k + 1) <= last) { //有子节点
                int j = 2 * k + 1;
                if ((j + 1) <= last) if (arr[j].compareTo(arr[j + 1]) < 0) j += 1; //去子节点中的较大者
                if (arr[k].compareTo(arr[j]) >= 0) break;
                exch(arr, k, j);
                k = j; //替换比较对象索引
            }
        }
    
        /**
         * 交换
         *
         * @param a
         * @param i
         * @param j
         */
        public static void exch(Comparable[] a, int i, int j) {
            Comparable temp;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    
        /**
         * 比较
         *
         * @param a
         * @param b
         * @return
         */
        public static boolean less(Comparable a, Comparable b) {
            return a.compareTo(b) < 0;
        }
    
        /**
         * 显示当前数组
         *
         * @param a
         */
        public static void show(Comparable[] a) {
            System.out.println(Arrays.toString(a));
        }
    
        /**
         * 判断数组是否有序
         *
         * @param a
         * @return
         */
        public static boolean isSorted(Comparable[] a) {
            for (int i = 0; i < a.length - 1; i++) {
                if (a[i].compareTo(a[i + 1]) > 0) {
                    System.out.println("false");
                    return false;
                }
            }
            System.out.println("true");
            return true;
        }
    }
    
    
    class TestCase {
        public static void main(String[] args) {
            SortDemo sortDemo = new SortDemo();
            Integer[] a = new Integer[]{34, 2, 5, 4, 45, 6, 22};
    //        sortDemo.selectSort(a);
    //        SortDemo.isSorted(a);
    
    //        sortDemo.insertSort(a);
    //        SortDemo.isSorted(a);
    
    //        sortDemo.mergeSort(a);
    //        SortDemo.isSorted(a);
    
    //        sortDemo.mergeSort2(a);
    //        SortDemo.isSorted(a);
    
    //        sortDemo.quickSort(a);
    //        SortDemo.isSorted(a);
    
    //        sortDemo.quickSort3Way(a);
    //        SortDemo.isSorted(a);
    
    //        sortDemo.heapSort(a);
    //        SortDemo.isSorted(a);
        }
    }

转载于:https://www.cnblogs.com/youzoulalala/p/11218540.html