数组排序

[xiwenAndlejian]

对于一个长度为 N 的整数数组进行排序。

方法一：冒泡排序

1. 从0索引开始，比较当前元素和后一个元素的大小，如果前一个大于后一个，则交换它们的位置
2. 如此直到比较完数组元素，此时数组中最后一个应是数组中最大的元素
3. 对数组剩下元素进行上述操作，直到比较完最后一对；

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] > nums[j+1]) {
                swap(nums, j, j+1);
            }
        }
    }
}
// 交换数组指定位置的元素
public void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

方法二：选择排序

和冒泡法类似，减少了交换的次数

1. 遍历数组，找寻最小的元素，让它与数组第一个元素交换位置
2. 遍历剩下数组，找寻最小元素，让它与剩下元素中第一个交换

public void chooseSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i ++) {
        int min = i;
        for (int j = i+1; j < nums.length; j++) {
            if (nums[min] > nums[j]) {
                min = j;
            }
        }
        swap(nums, i, min);
    }
}

方法三：插入排序

1. 比较前两个元素，将较小的那个放在前面
2. 将第三个元素与左边有序的部分比较，如果元素小于前一个元素，则交换它们并且继续向左比较；如果大于等于则停止比较。
3. 如此往复，直到所有元素都完成排序

public void insertSort(int[] nums) {
    for (int i = 1; i < nums.length; i ++) {
        for (int j = i; j > 0 && nums[j] < nums[j-1]; j--) {
            swap(nums, j, j-1);
        }
    }
}