Java 中的四种排序算法

冒泡排序

// 自定义成员方法实现冒泡排序算法，将参数指定数组中的所有元素从小到大排序
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);
    }

}

main

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 + "毫秒");
}