排序算法记忆口诀：
选泡插，快归堆希统计基，恩方恩老恩一三，对恩加K恩乘K，不稳稳稳不稳稳，不稳不稳稳稳稳
二、简单排序算法简单排序算法包括选择排序、冒泡排序、桶排序和插入排序，本节选择排序
选择排序最简单但是最没用的排序算法，也有优化空间
基本思想
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，按照顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。
排序过程
初始：[5 4 6 8 7 1 2 3] 第一趟排序后 1 [4 6 8 7 5 2 3] 第二趟排序后 1 2 [6 8 7 5 4 3] 第三趟排序后 1 2 3 [8 7 5 4 6] 第四趟排序后 1 2 3 4 [7 5 8 6] 第五趟排序后 1 2 3 4 5 [7 8 6] 第六趟排序后 1 2 3 4 5 6 [8 7] 第七趟排序后 1 2 3 4 5 6 7 [8] 最后排序结果 1 2 3 4 5 6 7 8对应代码
public class 选择排序 {
public static void main(String[] args) {
int [] arr = {5,3,6,8,1,7,9,4,2};
for (int i = 0; i < arr.length; i++) {
//假设第i的位置是最小的数
int minPos = i;
//让minPos与此位置之后的数相比 找出 最小的数 的坐标
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minPos]) {
minPos = j;
}
}
System.out.println(minPos);
int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
简化代码
public class 选择排序 {
public static void main(String[] args) {
//对数组进行初始化
int [] arr = {5,3,6,8,1,7,9,4,2};
for (int i = 0; i < arr.length - 1; i++) {
//假设第i的位置是最小的数
int minPos = i;
//让minPos与此位置之后的数相比 找出 最小的数 的坐标
for (int j = i+1; j < arr.length; j++) {
minPos = arr[j] < arr[minPos] ? j : minPos;
}
System.out.println("minPos:" + minPos);
int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;
System.out.println("经过第" + i + "次循环之后数组的内容");
print(arr);
}
}
static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
大O分析
首先不计入算法时间的代码有：(以下四句不计入算法时间)
int [] arr = {5,3,6,8,1,7,9,4,2};
.............
System.out.println("minPos:" + minPos);
.................
System.out.println("经过第" + i + "次循环之后数组的内容");
.........
}
}
................
System.out.print(arr[i] + " ");
...................
比较次数：约n^2/2次 交换次数：与序列的初始排序有关。
当序列正序时，交换次数为 0。
当序列反序时，交换次数为n-1。
综上，时间复杂度为 O(n^2)。
空间复杂度 O(1)
