一. 选择排序
1. 算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
2. 动图演示
3. 代码实现
/**
* 选择排序
* @param arr 无序数组
*/
public static void selectSort(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[minIndex] > arr[j]) { // 如果发现了比minIndex位置的值更小的值,就更新minIndex,这样就保证了minIndex始终是最小元素的索引
minIndex = j;
}
}
// 找到外层循环中最小的值后,交换i位置和minIndex位置的值,目的是将最小的值往前放,在下一轮循环中不再遍历它了
swap(arr, minIndex, i);
}
}二. 冒泡排序
1. 算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2. 动图演示
3. 代码实现
/**
* 冒泡排序
*
* @param arr
*/
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) { // 极值判断,无需排序
return;
}
// 外层循环,从后往前遍历,目的是将数组按照从小到大的顺利排列
// 使用 i>0 而不是 i>=0,是因为这是从后往前遍历,当后面的元素全部已经排好序之后,最后一个元素无需再比较,它只能是最小的那个.
for (int i = arr.length - 1; i > 0; i--) {
// 内存循环逐个比较当前元素与后一个元素的大小,如果当前元素大于后一个元素,则交换位置
// i是数组的元素的个数,使用 j<i,而不是j<=i是因为要把j与j后面的元素比较大小和交换位置,无需遍历到最后一个元素.
for (int j = 0; j < i; j++) {
// 如果j大j+1的值,则将j与j+1位置交换
// 在交换位置后,有开始下一轮for循环,再往后比较和交换每一个值,重复下去,直到找到最大的值放到数组右边
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}三. 插入排序
1. 算法步骤
- 将数组中的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2. 动图演示
3. 代码实现
/**
* 插入排序
*
* @param arr
*/
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) { // 极值判断
return;
}
// 将arr数组的第0个元素看作是一个有序数组(就一个元素肯定有序),第1个元素到第arr.length-1个元素看作是无序数组,
// 外层循环就是遍历这个无序数组,将它们逐个向有序数组中插入.
for (int i = 1; i < arr.length; i++) {
// arr数组中i-1位置到0位置是有序的,i位置(也就是j+1)就是本轮内层循环要比较插入的数
// 内层循环从后向前(从大到小)遍历有序数组的每一个元素与j+1的数进行比较,如果j+1的数小,就往前插
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}参考链接
[菜鸟教程]: https://www.runoob.com/w3cnote/insertion-sort.html “插入排序”
[菜鸟教程]: https://www.runoob.com/w3cnote/bubble-sort.html “冒泡排序”
[菜鸟教程]: https://www.runoob.com/w3cnote/selection-sort.html “选择排序”
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 george_95@126.com