选择排序
第一遍遍历：从头开始，找到最小值的坐标，将最小值和数组第一个元素对调
第二遍遍历：从第二个元素开始，找到最小值的坐标，将最小值和数组第二个元素对调
第三遍遍历：从第三个元素开始，找到最小值的坐标，将最小值和数组第三个元素对调
....
冒泡排序
第一遍遍历：只要前数比后数大就交换，一遍之后最大元素被移动到最后
第二遍遍历：还是从头来，只要前数比后数大就交换，一遍之后，次大的元素被移动到倒数第二个位置
第三遍遍历：还是从头来，只要前数比后数大就交换，一遍之后，第三大的元素被移动到倒数第三个位置
...
插入排序
第一遍遍历：插入第一个元素，不动
第二遍遍历：插入第二个元素，依次和它前面的元素比较看看能否互换，直到无法互换
第三遍遍历：同上
...
代码
点击查看代码
import cn.hutool.core.lang.Assert;
import cn.hutool.core.util.ArrayUtil;
import org.junit.Test;
import java.util.Arrays;
public class Day003_选择排序冒泡排序插入排序 {
@Test
public void test01(){
for (int p = 0; p < 10000; p++) {
for (int i = 1; i < 4; i++) {
int[] xx = 随机等概率生成一个数组.invoke(50, -30, 50);
int[] xxClone = ArrayUtil.clone(xx);
System.out.println(Arrays.toString(xx));
System.out.println(Arrays.toString(xxClone));
Assert.isTrue(ArrayUtil.equals(xx, xxClone));
if (i == 1) {
sort1(xx);
} else if (i == 2) {
sort2(xx);
} else {
sort3(xx);
}
Arrays.sort(xxClone);
System.out.println(Arrays.toString(xx));
System.out.println(Arrays.toString(xxClone));
Assert.isTrue(ArrayUtil.equals(xx, xxClone));
System.out.println("=========================");
}
}
}
/**
* 选择排序
*/
private void sort1(int[] xx) {
System.out.println("选择排序");
for (int i = 0; i < xx.length; i++) {
int minIndex = i;
for (int j = i + 1; j < xx.length; j++) {
if (xx[j] < xx[minIndex]) {
minIndex = j;
}
}
swap(xx, i, minIndex);
}
}
/**
* 冒泡排序
*/
private void sort2(int[] xx) {
System.out.println("冒泡排序");
for (int i = xx.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (xx[j] > xx[j + 1]) {
swap(xx, j, j + 1);
}
}
}
}
/**
* 插入排序
*/
private void sort3(int[] xx) {
System.out.println("插入排序");
for (int i = 0; i < xx.length; i++) {
for (int j = i; j - 1 >= 0; j--) {
if (xx[j] < xx[j - 1]) {
swap(xx, j, j - 1);
}
}
}
}
/**
* 交换
*/
private void swap(int[] xx, int x, int y) {
int temp = xx[x];
xx[x] = xx[y];
xx[y] = temp;
}
}
public class 随机等概率生成一个数组 {
public static int[] invoke(int max, int min, int length) {
int[] xx = new int[length];
for (int i = 0; i < xx.length; i++) {
//生成一个 [0,N] 的整数
int i1 = (int) (Math.random() * (max + 1 - min));
int i2 = i1 + min;
if (i2 > max || i2 < min) {
throw new RuntimeException("报错啦");
}
xx[i] = i2;
}
return xx;
}
/**
* 相邻两个元素不相等
*/
public static int[] invoke1(int max, int min, int length) {
int[] xx = new int[length];
for (int i = 0; i < xx.length; i++) {
//生成一个 [0,N] 的整数
do {
int i1 = (int) (Math.random() * (max + 1 - min));
int i2 = i1 + min;
if (i2 > max || i2 < min) {
throw new RuntimeException("报错啦");
}
xx[i] = i2;
} while (i > 0 && xx[i] == xx[i - 1]);
}
return xx;
}
}