排序算法(1)-冒泡排序,选择排序,插入排序,希尔排序,快速排序

柔光的暖阳◎ 2022-05-23 09:07 196阅读 0赞

一些基本的排序算法:

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;
    
        }
    
    
    
    }