冒泡、选择、插入排序

---

冒泡排序

排序过程

0 ~ i 范围上，相邻位置较大的数滚下去，最大值最终来到 i 位置，然后 0 ~ i -1 范围上继续

代码实现

// 数组中交换i和j位置的数
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 冒泡排序
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int end = arr.length - 1; end > 0; end--) {
        for (int i = 0; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
}

选择排序

排序过程

i ~ n -1 范围上，找到最小值并放在 i 位置，然后 i + 1 ~ n -1 范围上继续

代码实现

// 数组中交换i和j位置的数
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 选择排序
public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 在当前元素后找更小的元素，避免越界，i 遍历到 arr.length - 1
    for (int minIndex, i = 0; i < arr.length - 1; i++) {
        // 初始时假设当前位置是最小
        minIndex = i;
        // 遍历一轮是为了找到当前元素之后的最小的元素
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 找到了当前元素之后的最小的元素，交换位置
        swap(arr, i, minIndex);
    }
}

插入排序

排序过程

0 ~ i 范围上已经有序，新来的数从右到左滑到不再小的位置插入，然后继续

代码实现

// 数组中交换i和j位置的数
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 插入排序
public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 初始时 index = 0 的位置已经有序，从 index = 1 开始遍历
    for (int i = 1; i < arr.length; i++) {
        /*
            遍历一个元素，就和当前元素的前一个元素比较
            只要当前元素比前一个元素小，就交换位置
            注意点
            （1）比较的过程中，索引不能越界
            （2）通过当前元素的索引找到前一个元素，且前一个元素的索引是不断更新的
        */
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

本节代码

package class004;

public class SelectBubbleInsert {

	// 数组中交换i和j位置的数
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// 选择排序
	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int minIndex, i = 0; i < arr.length - 1; i++) {
			minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			swap(arr, i, minIndex);
		}
	}

	// 冒泡排序
	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int end = arr.length - 1; end > 0; end--) {
			for (int i = 0; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	// 插入排序
	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

}