Java 中的四种排序算法

import java.text.SimpleDateFormat;
import java.util.Date;

public class TestSortArith {

    // 自定义成员方法实现冒泡排序算法,将参数指定数组中的所有元素从小到大排序
    public static void bubble(int[] brr) {
        // 1.使用外层循环来控制比较的轮数
        for (int i = 1; i < brr.length; i++) {
            // 使用标志位表示数组时候发生了交换
            boolean flag = true;
            // 2.使用内层循环来控制比较的元素下标范围,也就是比较的次数
            for (int j = 0; j < brr.length - i; j++) {
                // 3.若左边的元素大于右边的元素则交换两个元素的位置
                if (brr[j] > brr[j + 1]) {
                    int temp = brr[j];
                    brr[j] = brr[j + 1];
                    brr[j + 1] = temp;
                    flag = false;

                    // 不使用第三者变量实现两个元素的交换
                    int a = 2;
                    int b = 3;
                    a = a + b; // a=5
                    b = a - b; // b=2
                    a = a - b; // a=3

                    // 使用抑或运算符
                    a = a ^ b;
                    b = a ^ b;
                    a = a ^ b;

                }
            }
            // 根据 flag 判断整个循环时候发生交换
            if (flag) {
                System.out.println(brr);
            }

        }
    }

    // 插入排序算法
    public static void insertSort(int[] irr) {
        int j;
        for (int i = 1; i < irr.length; i++) {
            int temp = irr[i];
            for (j = i - 1; j >= 0 && irr[j] > temp; j--) {
                irr[j + 1] = irr[j];
            }
            irr[j + 1] = temp;
        }
    }

    // 选择排序算法
    public static void selectSort(int[] srr) {
        int min = 0;
        for (int i = 0; i < srr.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < srr.length; j++) {
                if (srr[min] > srr[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = srr[i];
                srr[i] = srr[min];
                srr[min] = temp;
            }
        }
    }

    // 快速排序算法
    public static void fastSort(int[] frr, int left, int right) {
        int p = (left + right) / 2;
        int pivot = frr[p];
        // 2.分别使用左右两边的元素依次与基准值比较大小,将所有比基准值小的元素放在左边,将所有比基准值大的或者相等的元素放在右边
        int i = left;
        int j = right;
        for (; i < j;) {
            // 先使用左边的元素与基准值比较,若左边的元素小于基准值并且确实在左边,则使用下一个左边的元素继续与基准值大或者相等的元素放在右边
            while (frr[i] < pivot && i < p) {
                i++;
            }
            // 直到左边有元素并且左边元素不在小于基准值,此时将左边元素移动到 p 指向的位置,p 指向该元素原来的位置
            if (i < p) {
                frr[p] = frr[i];
                p = i;
            }
            // 再使用右边的元素与基准值比较,若右边的元素大于基准值并且确实在右边,则使用下一个右边的元素继续与基准值大或者相等的元素放在左边
            while (frr[j] >= pivot && j > p) {
                j--;
            }
            // 直到右边有元素并且右边元素不在大于基准值,此时将右边元素移动到 p 指向的位置,p 指向该元素原来的位置
            if (j > p) {
                frr[p] = frr[j]; 
                p = j;
            }
        }
        // 当左边元素的下标等于右边元素的下标时,把取出来的中间值重新赋值回去
        frr[p] = pivot;
        if ((p - left) > 1) {
            fastSort(frr, left, p - 1);
        }
        if ((right - p) > 1) {
            fastSort(frr, p + 1, right);
        }

    }

    public static void main(String[] args) {
        int[] brr = { 20, 10, 15, 5, 25, 30, 1, 8, 11, 26, 20, 3, 1 };
        int len = brr.length - 1;
        // System.out.println(len);
        Date time = new Date();
        SimpleDateFormat stFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("开始运行时间:" + stFormat.format(time));

        // 冒泡排序算法
        // TestSortArith.bubble(brr);
        // 插入排序算法
        // TestSortArith.insertSort(brr);
        // 选择排序算法
        // TestSortArith.selectSort(brr);
        TestSortArith.fastSort(brr, 0, len);
        System.out.print("排序后的数组是:");
        for (int i = 0; i < brr.length; i++) {
            System.out.print(brr[i] + " ");
        }

        Date time3 = new Date();
        long time2 = time.getTime();
        long time4 = time3.getTime();
        long res = time4 - time2;
        System.out.println("\n 一共运行的时间是:" + res + "毫秒");
    }

}
Copyright © cnkj.site 2021 all right reserved,powered by Gitbook该文件修订时间: 2021-06-01 11:23:39

results matching ""

    No results matching ""