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

选择排序、冒泡排序、插入排序、归并排序、快速排序的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;
    }
}