本文我们将使用Java编程语言实现经典的选择排序、冒泡排序和插入排序算法，并用对数器进行测试。
1. 选择排序
选择排序的基本思想是：遍历数组，每次找到数组中最小的元素，将其放到数组的前端。接着，在剩余的元素中继续寻找最小的元素，将其放在已找到的最小元素之后。重复该过程，直到数组完全有序。
1.1 选择排序代码
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//0~n-1
//1~n-1
//2~n-1
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {//从i~n-1上找最小值
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
1.2 测试部分
为了测试选择排序的正确性，我们需要使用到对数器。 对数器由以下几部分组成：
- 一种正确的排序方法(comparator)，用于对比测试；
- 随机生成一个数组(generateRandomArray)；
- 复制一个相同的数组(copyArray)；
- 判断两个数组的值是否相同(isEquals)；
- 打印数组(printArray)。
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
//生成长度随即大小随机的数组
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];//随机长度
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((int) (maxValue + 1) * Math.random() - (int) (maxValue * Math.random()));
}
return arr;
}
//复制数组
public static int[] copyArray(int[] arr) {
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
//判断两个数组的值是否相同
public static boolean isEquals(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
//打印数组
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
接下来，我们进行选择排序的大量测试
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
selectionSort(arr1);
comparator(arr2);
if (!isEquals(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
2. 冒泡排序
冒泡排序的基本思想是：遍历数组，相邻的两个元素进行比较，如果前一个元素大于后一个元素，则交换它们的位置。通过多次遍历，较大的元素不断地往数组的后端移动，最终实现数组的完全排序。
2.1 冒泡排序代码
public class Code02_BubbleSort {
public static void bubbleSort(int[] arr) {
if(arr==null||arr.length<2){
return;
}
for(int j=arr.length - 1; j >0; j--){
for(int i=0;i<j;i++){
if(arr[i]>arr[i+1]){
swap(arr, i,i+1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
}
2.2 测试部分
使用与选择排序相同的测试方法，进行冒泡排序的大量测试
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
bubbleSort(arr1);
comparator(arr2);
if (!isEquals(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
3. 插入排序
插入排序的基本思想是：将数组的元素一个个地插入到已经有序的部分，使得有序部分不断扩大，直至数组完全有序。文章来源：https://www.toymoban.com/news/detail-433874.html
3.1 插入排序代码
public class Code03_InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
测试内容同上面一样文章来源地址https://www.toymoban.com/news/detail-433874.html
到了这里，关于Java实现：选择排序、冒泡排序、插入排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
