本文我們將使用Java編程語(yǔ)言實(shí)現(xiàn)經(jīng)典的選擇排序、冒泡排序和插入排序算法，并用對(duì)數(shù)器進(jìn)行測(cè)試。

1. 選擇排序

選擇排序的基本思想是：遍歷數(shù)組，每次找到數(shù)組中最小的元素，將其放到數(shù)組的前端。接著，在剩余的元素中繼續(xù)尋找最小的元素，將其放在已找到的最小元素之后。重復(fù)該過(guò)程，直到數(shù)組完全有序。

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 測(cè)試部分

為了測(cè)試選擇排序的正確性，我們需要使用到對(duì)數(shù)器。 對(duì)數(shù)器由以下幾部分組成：

1. 一種正確的排序方法(comparator)，用于對(duì)比測(cè)試；
2. 隨機(jī)生成一個(gè)數(shù)組(generateRandomArray)；
3. 復(fù)制一個(gè)相同的數(shù)組(copyArray)；
4. 判斷兩個(gè)數(shù)組的值是否相同(isEquals)；
5. 打印數(shù)組(printArray)。

public static void comparator(int[] arr) {
    Arrays.sort(arr);
}
 //生成長(zhǎng)度隨即大小隨機(jī)的數(shù)組
public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];//隨機(jī)長(zhǎng)度
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) ((int) (maxValue + 1) * Math.random() - (int) (maxValue * Math.random()));
    }
    return arr;
}
 //復(fù)制數(shù)組
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;
}
 //判斷兩個(gè)數(shù)組的值是否相同
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;
}
 //打印數(shù)組
public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

接下來(lái)，我們進(jìn)行選擇排序的大量測(cè)試

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. 冒泡排序

冒泡排序的基本思想是：遍歷數(shù)組，相鄰的兩個(gè)元素進(jìn)行比較，如果前一個(gè)元素大于后一個(gè)元素，則交換它們的位置。通過(guò)多次遍歷，較大的元素不斷地往數(shù)組的后端移動(dòng)，最終實(shí)現(xiàn)數(shù)組的完全排序。

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 測(cè)試部分

使用與選擇排序相同的測(cè)試方法，進(jìn)行冒泡排序的大量測(cè)試

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. 插入排序

插入排序的基本思想是：將數(shù)組的元素一個(gè)個(gè)地插入到已經(jīng)有序的部分，使得有序部分不斷擴(kuò)大，直至數(shù)組完全有序。

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];
    }
}

測(cè)試內(nèi)容同上面一樣文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-433874.html

到了這里，關(guān)于Java實(shí)現(xiàn)：選擇排序、冒泡排序、插入排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！