简单选择排序介绍
简单选择排序：每一趟从待排序数列中选出最小或最大的一个元素，存放到数列的起始位置，直至待排序数列中的所有元素全部排放完。
每趟初始默认设定待排序数列中的第一个元素为最小（或最大）的元素；
将其与后面的元素逐一进行比较，若其大于（或小于）某一元素，则将这一元素记为最小（或最大）的元素，并按此方式继续向后比较；
当所有元素都比较过后，最终记录的元素即为该趟排序中最小（或最大）的元素，将其与待排序数列中的第一个元素交换位置；
去除起始位置排序完成的元素，将包含剩余元素的待排序数列按上述步骤进行排序；
执行(n-1)趟后，所有元素排序完成。
简单选择排序特点
-
时间复杂度
- 平均：O(n^2)
- 最坏：O(n^2)
- 最好：O(n^2)
-
空间复杂度
- O(1)
-
稳定性
- 不稳定
Java代码实现 （从小到大排序）
public void sort(int[] arr) {
// 需要执行的趟次(n-1)
for (int i = 0; i < arr.length - 1; i++) {
// 默认设置起始位置为最小
int min = i;
// 将当前最小的元素与后面的元素逐一比较
for (int j = i + 1; j < arr.length; j++) {
// 若当前最小元素大于后面的元素，将后面的元素设为最小
if (arr[min] > arr[j]) {
min = j;
}
}
// 将最小元素交换到起始位置
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}