排序算法
选择排序
/**
* 选择排序的思路 :
* 依次遍历数组，每次遍历数组的时候，记录当前未排序的最小值的索引
* 让最小值的索引和待排序的数组的第一个元素进行交换，然后继续重复操作
* 直到所有元素都排序
*/
public class SelectionSort {
public static void selectionSort(int[] arr) {
// 数组为空或已有序，直接返回
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
// 记录当前未排序的最小值
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// 找出未排序中最小值的索引
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换
swap(arr, i, minIndex);
}
}
/**
* 数组元素的交换方法，交换数组 i 和 j 处的值
*
* @param arr 数组
* @param i 数组索引 i
* @param j 数组索引 j
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
复杂度分析
时间复杂度
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度
O
(
1
)
O(1)
O(1)
冒泡排序
/**
* 冒泡排序的思路 :
* 从第 i = 0 处的元素开始，依次和 i + 1 做对比，如果 i 处的元素值大于 i + 1 处
* 则交换元素，即依次让未排序中的元素的最大元素从左往右边冒泡过去。
*/
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
// 每次从索引 0 处开始
for (int j = 0; j < arr.length - i - 1; j++) {
// 不断让较大的值上浮
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
/**
* 数组元素的交换方法，交换数组 i 和 j 处的值
*
* @param arr 数组
* @param i 数组索引 i
* @param j 数组索引 j
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
复杂度分析
时间复杂度
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度
O
(
1
)
O(1)
O(1)
