Basic Sorting in Java

Main.java

package org.qianq.examples;

import java.util.ArrayList;

class BubbleSort {
    /**
     * 冒泡排序
     * @param list 要排序的数组
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> list) {
        ArrayList<Integer> sorted = new ArrayList<>(list); // 复制一份原数组，不改变原数组

        boolean swapped; // 是否发生过交换
        do {
            swapped = false; // 每次开始排序前，假设没有发生过交换
            for (int i = 0; i < sorted.size() - 1; i++) { // 遍历数组，只遍历到倒数第二个元素（因为最后一个元素后面没有元素与之比较）
                if (sorted.get(i) > sorted.get(i + 1)) { // 如果当前元素比后一个元素大
                    // 交换两个元素
                    int tmp = sorted.get(i);
                    sorted.set(i, sorted.get(i + 1));
                    sorted.set(i + 1, tmp);
                    // 交换过元素后，将swapped设为true
                    swapped = true;
                }
            }
        } while (swapped); // 如果发生过交换，继续排序，否则代表排序已经完成，退出循环

        return sorted;
    }
}

class SelectionSort {
    /**
     * 选择排序
     * @param list 要排序的数组
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> list) {
        ArrayList<Integer> sorted = new ArrayList<>(list); // 复制一份原数组，不改变原数组

        int min, minIndex; // 最小值和最小值的索引

        for (int i = 0; i < sorted.size() - 1; i++) { // 遍历数组，只遍历到倒数第二个元素（因为最后一个元素后面没有元素与之比较）
            min = sorted.get(i); // 假设当前元素是最小值
            minIndex = i; // 假设当前元素的索引是最小值的索引

            for (int j = i + 1; j < sorted.size(); j++) { // 遍历当前元素之后的所有元素
                if (min > sorted.get(j)) { // 如果有比当前元素更小的元素
                    min = sorted.get(j); // 更新最小值
                    minIndex = j; // 更新最小值的索引
                }
            }

            // 将最小值与当前元素交换
            // （就算最小值是默认的当前元素也不会有问题，因为相当于没有交换）
            int tmp = sorted.get(i);
            sorted.set(i, min);
            sorted.set(minIndex, tmp);
        }

        return sorted;
    }
}

class InsertionSort {
    /**
     * 插入排序
     * @param list 要排序的数组
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> list) {
        ArrayList<Integer> sorted = new ArrayList<>(); // 需要一个新的数组来存放已排序的元素
        
        for (int i = 0; i < list.size(); i++) { // 遍历源数组
            int num = list.get(i); // 取出当前元素（要向已排序数组中插入的元素）
            if (i == 0) {
                // 如果已排序数组为空，直接将当前元素放入已排序数组
                sorted.add(num);
            } else {
                if (num <= sorted.get(0)) { // 如果当前元素小于等于已排序数组中的第一个元素
                    // 那么这个元素就是最小的
                    // 将已排序数组中的所有元素向后移动一个位置
                    sorted.add(sorted.get(sorted.size() - 1));
                    for (int j = sorted.size() - 2; j > 0; j--) {
                        sorted.set(j, sorted.get(j - 1));
                    }
                    // 将当前元素放入已排序数组的第一个位置
                    sorted.set(0, num);
                } else if (num > sorted.get(sorted.size() - 1)) {
                    // 如果当前元素比已排序数组中的最后一个元素大
                    // 直接将当前元素放入已排序数组的最后一个位置
                    sorted.add(num);
                } else {
                    // 否则，将当前元素插入到已排序数组中的合适位置
                    for (int j = 0; j < sorted.size() - 1; j++) { // 遍历已排序数组，找到合适的位置（搜索循环）
                        if (sorted.get(j) < num && num <= sorted.get(j + 1)) {
                            // 如果当前元素大于已排序数组中的第j个元素，且小于/等于第j+1个元素，那么当前元素应该插入到第j+1个位置
                            // 先将第j+1个位置以及之后的所有元素向后移动一个位置
                            sorted.add(sorted.get(sorted.size() - 1));
                            for (int k = sorted.size() - 2; k > j + 1; k--) {
                                sorted.set(k, sorted.get(k - 1));
                            }
                            // 将当前元素插入到第j+1个位置
                            sorted.set(j + 1, num);
                            break; // 不需要继续“搜索”循环了
                        }
                    }
                }
            }
        }

        return sorted;
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(-10);
        list.add(54);
        list.add(-18);
        list.add(-32);
        list.add(32);
        list.add(384);
        list.add(44);
        list.add(44);
        list.add(16);
        list.add(1);
        list.add(5);
        list.add(80);
        list.add(-32);
        list.add(0);
        list.add(48);
        list.add(384);

        System.out.println("Before sorting:");
        System.out.println(list);

        System.out.println("Bubble sort:");
        System.out.println(BubbleSort.sort(list));

        System.out.println("Selection sort:");
        System.out.println(SelectionSort.sort(list));

        System.out.println("Insertion sort:");
        System.out.println(InsertionSort.sort(list));
    }
}