编程马拉松 Day03 冒泡排序、选择排序、插入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public static void bubbleSort(Integer arr[]) {
        int compareCount = 0;//比较次数
        int swapCount = 0;//交换次数
        long before = System.currentTimeMillis();
        for (int i = 0; i < arr.length; i++) { //外层循环，与数组元素个数相关
            for (int j = 1; j < arr.length - i; j++) { //内层循环，只需在前 n-1 个元素内进行相邻比较
                compareCount++;
                if (arr[j - 1] > arr[j]) {
                    swapCount++;
                    swap(arr, j - 1, j);
                }
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("冒泡排序耗时："+(after-before)+"ms,"+"比较次数："+compareCount+",交换次数："+swapCount);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public static void bubbleSortOpt(Integer arr[]) {
        int compareCount = 0;//比较次数
        int swapCount = 0;//交换次数
        long before = System.currentTimeMillis();
        for (int i = 0; i < arr.length; i++) { //外层循环，与数组元素个数相关
        	boolean isSwap = false; //交换标记，每轮外循环开始时，将其置位false
            for (int j = 1; j < arr.length - i; j++) { //内层循环，只需在前 n-1 个元素内进行相邻比较
                compareCount++;
                if (arr[j - 1] > arr[j]) {
                	isSwap = true;//若内循环内发生交换，则将交换标志置位true
                    swapCount++;
                    swap(arr, j - 1, j);
                }
            }
            if (!isSwap) {//判断循环标记，若未发生交换，则跳出循环
            	break;
            }
        }
        long after = System.currentTimeMillis();
        System.out.println("冒泡排序耗时："+(after-before)+"ms,"+"比较次数："+compareCount+",交换次数："+swapCount);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public static void selectSort(Integer arr[]) {
    int compareCount = 0;
    int swapCount = 0;
    long before = System.currentTimeMillis();
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i+1; j < arr.length - i; j++) {
            compareCount++;
            if (arr[j]<arr[minIndex]){
                minIndex = j;
            }
        }
        if (minIndex!=i){
            swapCount++;
            swap(arr,i,minIndex);
        }
    }
    long after = System.currentTimeMillis();
    System.out.println("选择排序耗时：" + (after - before) + "ms," + "比较次数：" + compareCount + ",交换次数：" + swapCount);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public static void insertSort(Integer arr[]) {
    int compareCount = 0;
    int swapCount = 0;
    long before = System.currentTimeMillis();
    //外层循环，i表示有序子数组与无序子数组间的界限，i之前的元素为有序的，i及i之后的元素为无序的
    for (int i = 1; i < arr.length; i++) {
    	//内层循环，将i到0之间的元素两两比较，若i<i-1，则交换两者的位置
        for (int j = i; j > 0; j--) {
            compareCount++;
            if (arr[j] < arr[j - 1]) {
                swapCount++;
                swap(arr, j, j - 1);//两两交换
            }
        }
    }
    long after = System.currentTimeMillis();
    System.out.println("选择排序耗时：" + (after - before) + "ms," + "比较次数：" + compareCount + ",交换次数：" + swapCount);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public static void insertSortOpt(Integer arr[]) {
    long before = System.currentTimeMillis();
    for (int i = 1; i < arr.length; i++) {
    	//使用临时变量保存新牌
        int temp  =arr[i];
        int j = i;
        //从大到小，依次取左手中的牌与temp进行比较，若左手当前手牌大于temp，则将当前手牌后移一位
        while(j>0 && temp<arr[j-1]){
        	arr[j] = arr[j -1];
        	j--;//继续下一张较大的牌
        }
        arr[j] = temp;//最终将temp插入左手手牌中合适的位置
    }
    long after = System.currentTimeMillis();
    System.out.println("插入排序耗时：" + (after - before) + "ms");
}