选择排序、冒泡排序、插入排序、归并排序、快速排序的Java实现以及优化

- 日理万妓 2022-03-22 14:13 155阅读 0赞

### 选择排序、冒泡排序、插入排序、归并排序、快速排序的Java实现以及优化 ###

选择排序、冒泡排序、插入排序、归并排序、快速排序的Java实现以及优化。话不多说，原理以及估算方法时间均在注释中写明。

package com.yayiyo.data.algorithms.sort;
    
    import com.sun.org.apache.xpath.internal.functions.FuncBoolean;
    import com.yayiyo.data.com.yayiyo.data.common.ArrayGeneratorUtils;
    import com.yayiyo.data.com.yayiyo.data.common.FunctionTime;
    import org.junit.Test;
    /* * 排序类 * @Author yayiyo */
    public class SortTest extends FunctionTime { 
    
        /** * 数组长度 */
        public static final int LENGTH = 100000;
    
        /** * 无效code */
        public static final int NOT_FOUND = -1;
    
        /** * 经测试归并排序和快速排序的排序效果有很大提升，尤其快速排序。 */
        @Test
        public void test() { 
            long[] arr = ArrayGeneratorUtils.getArrayByLength(LENGTH);
            // 10 100 1,000 10,000 100,000 1,000,000 10,000,000 100,000,000
            //selectionSort(arr); // 1ms 1ms 7ms 211ms 33814ms
            //selectionSortOptimize(arr); // 1ms 1ms 6ms 111ms 9915ms
            //buubleSort(arr); // 0ms 1ms 8ms 203ms 25402ms
            //buubleSortOptimize(arr); // 1ms 2ms 7ms 233ms 27408ms
            //insertionSort(arr); // 1ms 1ms 7ms 98ms 9128ms 994299ms
            //insertionSortOptimize(arr); // 1ms 1ms 6ms 82ms 6667ms 688153ms
            //mergeSort(arr); // 0ms 0ms 3ms 8ms 53ms 385ms 3942ms 42891ms
            //quickSort(arr, 0, arr.length - 1); // 0ms 0ms 0ms 16ms 62ms 316ms 2570ms 27352ms
            checkSort(arr);
            //printArr(arr);
        }
    
        /** * 选择排序 * 原理：从第一个元素（i = 0）起，I + 1 ~ n分别与i进行判断，当小于i时，交换元素，保证外循环每次遍历后第i个元素是i ~ n中最小的。 * 上限：O（n^2）,交换次数：O(n^2) */
        public void selectionSort(long[] arr) { 
            int length = arr.length;
            for (int i = 0; i < length - 1; i++) { 
                for (int j = i + 1; j < length; j++) { 
                    if (arr[j] < arr[i]) { 
                        swap(arr, i, j);
                    }
                }
            }
        }
    
        /** * 优化选择排序 * 上限：O（n^2）,交换次数：O(n) * 优化方式：i+1 ~ n 分别与 i进行比较，当发现有比i小的值之后，先记录位置，等遍历完再替换。 * 优化结果：明显。相比普通选择排序，减少swap交换次数。 */
        public void selectionSortOptimize(long[] arr) { 
            int length = arr.length;
            int min = 0;
            boolean isSwap = false;
            for (int i = 0; i < length - 1; i++) { 
                isSwap = false;
                for (int j = i + 1; j < length; j++) { 
                    if (arr[j] < arr[i]) { 
                        min = j;
                        isSwap = true;
                    }
                }
                if (isSwap) { 
                    swap(arr, i ,min);
                }
            }
        }
    
        /** * 冒泡排序 * 原理：内循环遍历时，当第i个元素比第i + 1大时，交换元素。保证每次外循环遍历后，第 n - i的元素是 0 ~ n - i中最大的。 * 上限：O（n ^ 2） 交换次数：O(n ^ 2) */
        public void buubleSort(long[] arr) { 
            int length = arr.length;
            for (int i = 0; i < length - 1; i++) { 
                for (int j = 0; j < length - i - 1; j++) { 
                    if (arr[j] > arr[j + 1]) { 
                        swap(arr, j, j + 1);
                    }
                }
            }
        }
    
        /** * 冒泡排序优化 * 优化方式：当外循环第i次遍历后，内循环遍历不在交换元素，意味元素已排序完毕，可以直接结束循环。 * 优化效果：不明显 */
        public void buubleSortOptimize(long[] arr) { 
            int length = arr.length;
            boolean isSwap = false;
            for (int i = 0; i < length - 1; i++) { 
                isSwap = false;
                for (int j = 0; j < length - i - 1; j++) { 
                    if (arr[j] > arr[j + 1]) { 
                        swap(arr, j, j + 1);
                        isSwap = true;
                    }
                }
                if (!isSwap) { 
                    return;
                }
            }
        }
    
        /** * 插入排序 * 原理：把第i个元素与前i - 1（有序）个元素进行比较，把i插到正确位置，保证每次外循环遍历后，前i个元素是有序的。 * 上限：O(n ^ 2) ,交换次数： O(n ^ 2) * @param arr */
        public void insertionSort(long[] arr) { 
            int length = arr.length;
            for (int i = 1; i < length; i++) { 
                for (int j = i; j > 0; j--) { 
                    if (arr[j - 1] > arr[j]) { 
                        swap(arr, j, j-1);
                    }
                }
            }
        }
    
        /** * 优化插入排序（二分查找） * 优化方式：先使用二分法查找i - 1元素中第i个元素的所在位置，然后插入该元素。 * 优化结果：相对插入排序明显，但是交换次数没有明显改观，所以实际上排序时间：查询时间是O (n log n)有提升，但是总体效果仍接近O(n ^ 2) * 上限：O(n log n),交换次数：O（n ^ 2） */
        public void insertionSortOptimize(long[] arr) { 
            int length = arr.length;
            for (int i = 1; i < length; i++) { 
                int insertIndex = binarySearchForInsertionSort(arr, arr[i], 0, i-1);
                for (int j = i; j > insertIndex; j--) { 
                    swap(arr, j, j - 1);
                }
            }
        }
    
        /** * 归并排序 * 原理：先使用2分法把数组分为一个个数字，然后每两个进行比较。排序结构二叉树类似。从下往上进行排序 * 分解：二分法 * 递归：使用递归一层层分解数组 * 合并：从下往上合并数组。左右两个数组排序。可参考两个栈内存，比较栈顶元素，取出小的那个进行排序。 * 上限：O(n log n) * 注意事项：排序时不是原址的，会创建大概数组2n - 1个数组。很占用内存（多次涉及到数组深拷贝，O(n log n)的常量很大） */
        public void mergeSort(long[] arr) { 
            int length = arr.length;
            if (length == 1) { 
                return;
            }
            /* * 1,分解 */
            int middle = (length) / 2;
            long[] left = new long[middle];
            long[] right = new long[length - middle];
            for (int i = 0, leftIndex = 0; i < middle;) { 
                left[leftIndex++] = arr[i++];
            }
            for (int i = middle, rightIndex = 0; i < length;) { 
                right[rightIndex++] = arr[i++];
            }
            /* * 2， 递归 */
            mergeSort(left);
            mergeSort(right);
    
            /* * 3,合并 */
            for (int i = 0, j = 0, l = 0; i < left.length || j < right.length;) { 
                if (i == left.length) { 
                    arr[l++] = right[j++];
                    continue;
                }
                if (j == right.length) { 
                    arr[l++] = left[i++];
                    continue;
                }
                if (left[i] <= right[j]) { 
                    arr[l++] = left[i++];
                    continue;
                }
                if (left[i] > right[j]) { 
                    arr[l++] = right[j++];
                }
            }
    
        }
    
        /** * 快速排序 * 原理：取出第n个元素前n个进行比较，比较结束后前i个元素小于等于n元素，i +1 到 n个均大于等于n元素。 交换i与n。 * 然后递归比较o ~ i - 1， i + 1到n。 * 上限：O(n ^ 2), 下限： Ω(n log n) * 排序效果最为明显。 */
        public void quickSort(long[] arr, int start, int end) { 
            if (start >= end) { 
                return;
            }
            long right = arr[end];
            int p = start, q = end;
            while (p != q) { 
                while(arr[p] <= right && p < q)
                    p++;
                while(arr[q] >= right && p < q)
                    q--;
                if (p < q)
                { 
                   swap(arr, p, q);
                }
                if (p == q ) { 
                    if ( arr[p] < right) { 
                        swap(arr, p+1, end);
                    }
                    if (arr[q] > right) { 
                        swap(arr, q, end);
                    }
                }
            }
            quickSort(arr, start, p-1);
            quickSort(arr, p+1, end);
    
        }
    
        /** * 二分查找（插入排序） * @param arr * @param x * @param start * @param end * @return */
        public int binarySearchForInsertionSort(long[] arr, long x, int start, int end) { 
            if (start > end) { 
                return start;
            }
            int middle = (start + end) / 2;
            if (arr[middle] > x) { 
                return binarySearchForInsertionSort(arr, x, start, middle - 1);
            }
            if (arr[middle] < x ) { 
                return binarySearchForInsertionSort(arr, x, middle + 1, end);
            }
            return middle;
        }
    
        public int binarySearch(long[] arr, long x, int start, int end) { 
            if (start > end) { 
                return NOT_FOUND;
            }
            int middle = (start + end) / 2;
            if (arr[middle] > x) { 
                return binarySearch(arr, x, middle + 1, end);
            }
            if (arr[middle] < x) { 
                return binarySearch(arr, x, start, middle - 1);
            }
            return middle;
        }
    
    
        public void swap(long[] arr, int p, int q) { 
            arr[p] = arr[p] ^ arr[q];
            arr[q] = arr[p] ^ arr[q];
            arr[p] = arr[p] ^ arr[q];
        }
    
        public void printArr(long[] arr) { 
            for (int i = 0; i < arr.length; i++) { 
                System.out.println(arr[i]);
            }
        }
    
        public boolean checkSort(long[] arr) { 
            for (int i = 0; i < arr.length - 1; i++) { 
                if (arr[i] > arr[i + 1]) { 
                    System.out.println("排序方法错误");
                    return false;
                }
            }
            System.out.println("正确排序");
            return true;
        }
    
    }
    
    package com.yayiyo.data.com.yayiyo.data.common;
    
    import org.junit.After;
    import org.junit.Before;
    
    /** * @Author yayiyo * 方法时间计算类 * 使用代理模式，可以计算方法的执行时间 * 针对junit使用，继承即可 */
    public class FunctionTime { 
        /** * 开始时间 */
        public static long startTime = 0;
    
        /** * 结束时间 */
        public static long endTime = 0;
    
        @Before
        public void start() { 
            this.startTime = System.currentTimeMillis();
        }
    
        public static long sum(long i) { 
            long sum = 0;
            for (int j = 0; j < i; j++) { 
                sum += j * j * j;
            }
            return sum;
        }
    
        @After
        public void end() { 
            this.endTime = System.currentTimeMillis();
            long time = endTime - startTime;
            System.out.println("方法运行时间为:" + time + "ms");
        }
    }
    
    
    package com.yayiyo.data.com.yayiyo.data.common;
    
    import java.util.Random;
    
    /** * @Author yayiyo * 数组生成类 */
    public class ArrayGeneratorUtils { 
        public static long[] getArrayByLength(int length) { 
            long[] array = new long[length];
            for (int i = 0; i < length; i++) { 
                Random random = new Random();
                array[i] = random.nextLong();
            }
            return array;
        }
    }