选择排序、冒泡排序、插入排序

发表于 分类于 本文字数： 2.1k 阅读时长 ≈ 2 分钟
基于Java实现三种简单的排序算法并使用对数器验证

1. 对数器的设定

1.1. 对数器概念和使用

　 - 有一个你想要的测的方法a
　 - 实现一个绝对正确但是复杂度不好的方法b
　 - 实现对比的方法

  • 把方法a和方法b对比很多次来验证方法a是否是正确的

  • 如果有个样本使得对比出错，打印出样本分析是哪个方法出错的

  • 当样本数量很多的时候，对比测试依然正确，可以确定方法a已经正确

　　

1.2. 数组排序对数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package com.company;

import java.util.Arrays;

public class Main {

    private static final int MIN = 0;
    private static final int MAX = 1000;
    private static final int MAXLENGTH = 10000;
    private static final int FREQUENCY = 10000;

    public static void main(String[] args) {
	// write your code here

        boolean succeed = true;
        for (int i = 0; i < FREQUENCY; i++) {
            int[] arr = GenerateRandom();
            int[] arr2 = Arrays.copyOf(arr, arr.length);
//            Arrays.sort(arr);你测试的排序函数
            comparator(arr2);
            if (!Arrays.equals(arr, arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed?"succeed":"failed");
    }

    /*
    产生随机数组
     */
    public static int[] GenerateRandom(){
        int length = (int)(MAXLENGTH*Math.random());
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = MIN + (int)(Math.random()*(MAX-MIN));
        }
        return arr;
    }

    /*
    最稳健的对比算法作为对比，此处调用JDK自带的排序算法
     */
    public static void comparator(int[] arr){
        Arrays.sort(arr);
    }

}

2. 选择排序

选择排序的实质就是每次从剩下的数组中选出最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
选择排序：实质就是每次选出最值
 */
public static void chooseSort(int[] arr){
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length ; j++) {
            if (arr[j] < arr[minIndex]) { //choose minimum value
                minIndex = j;
            }
        }
        if (i != minIndex)
            swap(arr, i, minIndex);
    }
}

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

3. 冒泡排序

冒泡排序的实质就是进行N次比较

1
2
3
4
5
6
7
8
9
10
11
12
/*
冒泡排序：实质就是进行N次比较
 */
private static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] > arr[j+1]){
                swap(arr, i, j);
            }
        }
    }
}

4. 插入排序

插入排序的实质就是将一个数插入一个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
插入排序：实质就是将一个数插入一个有序数组
 */
private static void insertSort(int[] arr){
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int j = i;
        while (j>0 && arr[j-1]>tmp){//将比他大的数后移
            arr[j] = arr[j-1];
            j--;
        }
        if (i != j)//如果有比他小的数就插入，如果没有就下一次循环
            arr[j] =tmp;
    }
}