本文共 10833 字，大约阅读时间需要 36 分钟。

一些基本的排序算法:

package tenSortingMethods;/** * @author zhangdi * @description 排序算法 * @Date 20180531 */public class Sort {
       public static void main(String[] args) {        int[] arr = {
  6,1,2,7,9,3,4,5,10,8};//{ 26, 88, 45, 57, 12, 31, 12, 2, 64, 32, 20, 99, 1 };        int[] arr1 = { 2, 1, 3, 5, 4 };// {6,1,2,7,9,3,4,5,10,8};        // System.out.println(arr.getClass());        System.out.println(" arr before sorting: " + IntArrtoString(arr));        // BubbleSort(arr);        // BubbleSort2(arr);        // BubbleSort1_better(arr);        // SelectSort(arr);        // InsertionSort(arr);        // ShellSort(arr);        // ShellSort2(arr);        // int[] quickSort = new Sort().QuickSort(arr, 0, arr.length - 1);        // System.out.println(" quickSort after sorting: " +        // IntArrtoString(quickSort));         int[] quickSort2 = new Sort().QuickSort2(arr, 0, 9);        // System.out.println(" quickSort2 after sorting: " +        // IntArrtoString(quickSort2));         System.out.println(" arr after sorting: " + IntArrtoString(arr));    }    /**     * @description 冒泡排序     * @param arr     * @description : 两两比较,大的往后放; 每一次比较完成之后,下一次就少比较一个元素     *              第一次比较有0个元素不比较;第二次有一个元素不需要比较;第三次有两个元素不需要比较;     *              共需要比较arr.length-1次     */    public static void BubbleSort(int[] arr) {        int temp;// 临时变量        if (arr == null || arr.length == 0)            return;        for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。            for (int j = arr.length - 1; j > i; j--) {                if (arr[j] < arr[j - 1]) {                    temp = arr[j];                    arr[j] = arr[j - 1];                    arr[j - 1] = temp;                }            }        }    }    /**     * @description 冒泡排序-2     * @param arr     *      */    public static void BubbleSort2(int[] arr) {        int temp;// 临时变量        if (arr == null || arr.length == 0)            return;        for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {                    temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }        }    }    /**     * @description 冒泡排序-1-优化     * @param arr     *            * 针对问题:数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。     *            方案: 设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。     *            这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。     *      */    public static void BubbleSort1_better(int[] arr) {        int temp;// 临时变量        boolean flag;        if (arr == null || arr.length == 0)            return;        for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。            flag = false;            for (int j = arr.length - 1; j > i; j--) {                if (arr[j] < arr[j - 1]) {                    temp = arr[j];                    arr[j] = arr[j - 1];                    arr[j - 1] = temp;                }            }            if (!flag)                break;        }    }    /**     * @description 选择排序     * @param arr     *            在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；     *            第二次遍历n-2个数，找到最小的数值与第二个元素交换； 。。。     *            第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。     */    public static void SelectSort(int[] arr) {        int len = arr.length;        int temp;// 临时变量        if (arr == null || len == 0)            return;        for (int i = 0; i < len - 1; i++) {            int minIndex = i;// 假定此时i位置元素为最小数值            for (int j = i + 1; j < arr.length; j++) {                if (arr[j] < arr[minIndex]) {                    // 如果i+1后的元素值小于i位置的元素,那么改变minIndex值.当内层循环走完,此时数组最小值得小标就确定了                    minIndex = j;                }            }            if (minIndex != i) {                // 最小值下标改变,交换元素                temp = arr[i];                arr[i] = arr[minIndex];                arr[minIndex] = temp;            }        }    }    /**     * @description 插入排序     * @param arr     * @description : 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。     *              如此反复循环，直到全部排好顺序。 位于表中后面的元素依次与表中前面的元素比较，若比之小，则还需继续和更前面的元素比较，     *              直至遇到一个比它大的元素或者比较到第一个元素(哨兵)了。     */    public static void InsertionSort(int[] arr) {        int len = arr.length;        int temp;// 临时变量        if (arr == null || len == 0)            return;        for (int i = 0; i < len - 1; i++) {
  // 趟数n-1趟            for (int j = i + 1; j > 0; j--) {                if (arr[j] < arr[j - 1]) {                    temp = arr[j];                    arr[j] = arr[j - 1];                    arr[j - 1] = temp;                } else {                    break;                }            }        }    }    /**     * @description 希尔排序 (最小增量排序)     * @param arr     * @description: 我们选择增量gap=length/2，缩小增量继续以gap =     *               gap/2的方式，这种增量选择我们可以用一个序列来表示，{n /2,(n/2)/2...1}，称为增量序列。     *               希尔排序的增量序列的选择与证明是个数学难题， 我们选择的这个增量序列是比较常用的，也是希尔建议的增量，     *               称为希尔增量，但其实这个增量序列不是最优的。 此处我们做示例使用希尔增量。     *               比如原始数组8917235460,初始增量为gap =length/5;即数组被分为五组     *               [8,3],[9,5],[1,4],[7,6],[2,0] ,对五组分别进行插入排序;第一次排序后:     *               3514089472,缩小增量为gap =gap/2 =     *               2;分为两组[3,5,1,4,0],[8,9,4,7,2],插入排序 -->[0214357698],     *               再缩小增量gap = gap/ = 1,[0214357698] -->插入排序.     *      *      */    public static void ShellSort(int[] array) {        int temp = 0;        int incre = array.length;        while (true) {            incre = incre / 2;            for (int k = 0; k < incre; k++) { // 根据增量分为若干子序列                for (int i = k + incre; i < array.length; i += incre) {                    for (int j = i; j > k; j -= incre) {                        if (array[j] < array[j - incre]) {                            temp = array[j - incre];                            array[j - incre] = array[j];                            array[j] = temp;                        } else {                            break;                        }                    }                }            }            if (incre == 1) {                break;            }        }    }    /**     * @description 希尔排序 (最小增量排序)     * @param arr     *            在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中，     *            我们可以不用这么按部就班地处理完一组再调转回来处理下一组（ 这样还得加个for循环去处理分组）比如[5,4,3,2,1,0]     *            ，首次增量设gap=length/2=3,则为3组[5,2] [4,1]     *            [3,0]，实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时，     *            可以采用元素交换法寻找最终位置， 也可以采用数组元素移动法寻觅。     *      */    /**     * 希尔排序 针对有序序列在插入时采用交换法 见图     *      * @param arr     */    public static void ShellSort2(int[] arr) {        System.out.println("ShellSort2 start.........");        // 增量gap，并逐步缩小增量        for (int gap = arr.length / 2; gap > 0; gap /= 2) {            // 从第gap个元素，逐个对其所在组进行直接插入排序操作            System.out.println("1 gap:" + gap + "  arr:" + IntArrtoString(arr));            for (int i = gap; i < arr.length; i++) {                int j = i;                while (j - gap >= 0 && arr[j] < arr[j - gap]) {                    // 插入排序采用交换法                    swap(arr, j, j - gap);                    j -= gap;                }                System.out.println("2 gap:" + gap + " i:" + i + " arr:" + IntArrtoString(arr));            }        }        System.out.println("ShellSort2 end...........");    }    /**     * 希尔排序 针对有序序列在插入时采用移动法。     *      * @param arr     */    public static void ShellSort3(int[] arr) {        // 增量gap，并逐步缩小增量        for (int gap = arr.length / 2; gap > 0; gap /= 2) {            // 从第gap个元素，逐个对其所在组进行直接插入排序操作            for (int i = gap; i < arr.length; i++) {                int j = i;                int temp = arr[j];                if (arr[j] < arr[j - gap]) {                    while (j - gap >= 0 && temp < arr[j - gap]) {                        // 移动法                        arr[j] = arr[j - gap];                        j -= gap;                    }                    arr[j] = temp;                }            }        }    }    /**     * 交换数组元素     *      * @param arr     * @param a     * @param b     */    public static void swap(int[] arr, int a, int b) {        arr[a] = arr[a] + arr[b];        arr[b] = arr[a] - arr[b];        arr[a] = arr[a] - arr[b];    }    /**     * @param arr     * @description 快速排序 基本思想：（分治） 先从数列中取出一个数作为key值；     *              将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边； 对左右两个小数列重复第二步，直至各区间只有1个数。     * @ses http://developer.51cto.com/art/201403/430986.htm     *      https://blog.csdn.net/morewindows/article/details/6684558     */    // 快速排序    public int[] QuickSort(int[] a, int l, int r) {        if (l < r) {            int i = l, j = r, v = a[l];// i:左边开始活动坐标，j:右边开始活动坐标，v：基数，用于对比的值，一般取第一个            while (i < j) {
  // 只要左边游标和游标不重叠的话那么就继续遍历                System.out.println("i:" + i + " j:" + j + " arr:" + IntArrtoString(a));                // 每一轮遍历的时候只进行一轮，把右边的一个比基数小的数移动到左边，把左边比基数大的数移动到右边                while (i < j && a[j] > v)                    // 找出右边比左边小的坐标                    j--;                if (i < j)                    a[i++] = a[j];// 进行移动，左边坐标移动一个数                System.out.println("i:" + i + " j:" + j + " arr:" + IntArrtoString(a));                while (i < j && a[i] < v)                    // 找出左边比右边大的坐标                    i++;                if (i < j)                    a[j--] = a[i];// 进行移动，右边坐标移动一个数                System.out.println("i:" + i + " j:" + j + " arr:" + IntArrtoString(a));            }            a[i] = v;// 当游标重叠时填入基数            this.QuickSort(a, l, i - 1);            this.QuickSort(a, i + 1, r);            return a;        }        return a;    }    /**     * @param a     * @param left     * @param right     * @return  QuickSort2在一轮对比基准数的过程中不移动基准数,减少移动次数     */    public int[] QuickSort2(int[] a, int left, int right) {        //校验要初始化变量之前;不校验易报错:java.lang.ArrayIndexOutOfBoundsException        if (left>right ) {            return a;        }        int i = left, j = right, s = a[left];        int temp;        while (i < j) {            //System.out.println("1--------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));            while (a[j] >= s && j > i) {                j--;                //System.out.println("2--------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));            }            while (a[i] <= s && j > i) {                i++;                //System.out.println("3--------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));            }            if (i < j) {                temp = a[j];                a[j] = a[i];                a[i] = temp;                //System.out.println("4---------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));            }        }        a[left] = a[i];        a[i] = s;        QuickSort2(a, left, i - 1);        QuickSort2(a, i + 1, right);        return a;    }}