思路

  1. 依序排序大小
  2. 如果相鄰兩個數字大小相反,就交換位置
  3. 最大在右邊,最小在左邊

實作

測試方法

public static void main(String[] args) {
    int[] nums = new int[]{8, 2, 6, 10, 4}; // 依序排序
    Sort_Bubble3.bubble_sort(nums); // 預期結果:[2, 4, 6, 8, 10]

    System.out.println();
}

具體

public static void bubble_sort(int[] nums){
    for (int round = 0; round < nums.length; round++) { // 從頭開始跑
        int len = nums.length; // 總長度
        for (int i_run = 1; i_run < len; i_run++) {
            // nums[0] > nums[1]
            // nums[1] > nums[2]
            if (nums[i_run - 1] > nums[i_run]) {
                swap(nums, i_run - 1, i_run); // 交換
            }
        }
    }
}

private static void swap(int[] nums, int i_left, int i_right) {
    int tmp = nums[i_left]; // set temp variable
    nums[i_left] = nums[i_right]; // 把 right 放到 left
    nums[i_right] = tmp; // 把 left 放到 right
}

優化

public static void bubble_sort(int[] nums){
    for (int round = 0; round < nums.length; round++) { // 從頭開始跑
        int len = nums.length - round; // 5 - round<1> = 4
        for (int i_run = 1; i_run < len; i_run++) { // 這邊就可以少跑一次迴圈,在右邊排序好的部分不需要再進入迴圈
            if (nums[i_run - 1] > nums[i_run]) {
                swap(nums, i_run - 1, i_run); // 交換
            }
        }
    }
}

實作 by recursion

測試方法

public static void main(String[] args) {
    nums = new int[]{8, 2, 6, 10, 4};
    Sort_Bubble3.bubble_sort_recursion(nums);

    System.out.println();
}

具體

public static void bubble_sort_recursion(int[] nums) {
    int round = 0; // 第幾輪,隨時間增加
    bubble_sort_recursion_help01(nums, round);
}

private static void bubble_sort_recursion_help01(int[] nums, int round) {
    if (round >= nums.length) { //數量執行完
        return;
    }

    int len = nums.length - round; //優化迴圈部分
    int i_run = 1;
    bubble_sort_recursion_help02(nums, len, i_run);

    // calling self, 逐次+1達到迴圈效果
    bubble_sort_recursion_help01(nums, round + 1);
}

private static void bubble_sort_recursion_help02(int[] nums, int len, int i_run) {
    /** end condition **/
    if (i_run >= len) { // 如果執行完結束
        return;
    }

    /** main logic **/
    if (nums[i_run - 1] > nums[i_run]) {
        swap(nums, i_run - 1, i_run);
    }

    /** data flow **/
    bubble_sort_recursion_help02(nums, len, i_run + 1);
}

private static void swap(int[] nums, int i_left, int i_right) {
    int tmp = nums[i_left]; // set temp variable
    nums[i_left] = nums[i_right]; // 把 right 放到 left
    nums[i_right] = tmp; // 把 left 放到 right
}