2019-07-19 14:07 南京理工大学紫金学院 Java

关注

算法基础-冒泡-选择-插入-归并

// 整理于左神的算法课
一，对数器

对数器的概念和使用

0，有一个你想要测的方法a，

1，实现一个绝对正确但是复杂度不好的方法b，

2，实现一个随机样本产生器

3，实现比对的方法

4，把方法a和方法b比对很多次来验证方法a是否正确。

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

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

=================================================================================

一。冒泡排序（时间复杂度 O（n^2），额外空间复杂度 O(1))

   public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
        for (int i = 0; i < e; 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];
}

二。选择排序（时间复杂度 O（n^2），额外空间复杂度 O(1))

a) 原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）

b) 简单选择排序的基本思想：给定数组：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。

c) 举例：数组 int[] arr={5,2,8,4,9,1};

第一趟排序：原始数据：5 2 8 4 9 1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果：1 2 8 4 9 5

第二趟排序：

第1以外的数据{2 8 4 9 5}进行比较，2最小，

排序结果：1 2 8 4 9 5

第三趟排序：

除1、2以外的数据{8 4 9 5}进行比较，4最小，8和4交换

排序结果：1 2 4 8 9 5

第四趟排序：

除第1、2、4以外的其他数据{8 9 5}进行比较，5最小，8和5交换

排序结果：1 2 4 5 9 8

第五趟排序：

除第1、2、4、5以外的其他数据{9 8}进行比较，8最小，8和9交换

排序结果：1 2 4 5 8 9

 public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

三。插入排序（时间复杂度 O（n^2），额外空间复杂度 O(1))

插入排序的基本方法是：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。

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

四。归并排序（时间复杂度O(N*logN)，额外空间复杂度O(N)）

详细 https://www.cnblogs.com/chengxiao/p/6194356.html

 public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}

public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

public static void merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    while (p1 <= m && p2 <= r) {
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
}

master公式的使用

T(N) = a*T(N/b) + O(N^d)

1） log(b,a) > d -> 复杂度为O(N^log(b,a))

2） log(b,a) = d -> 复杂度为O(N^d * logN)

3）log(b,a) < d -> 复杂度为O(N^d)

五：对数器例子

  package basic_class_01;

 import java.util.Arrays;

 public class Code_00_BubbleSort {

 public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
        for (int i = 0; i < e; 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];
}

// for test
public static void comparator(int[] arr) {
    Arrays.sort(arr);
}

// for test
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) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
}

// for test
public static int[] copyArray(int[] arr) {
    if (arr == null) {
        return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        res[i] = arr[i];
    }
    return res;
}

// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
        return false;
    }
    if (arr1 == null && arr2 == null) {
        return true;
    }
    if (arr1.length != arr2.length) {
        return false;
    }
    for (int i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

// for test
public static void printArray(int[] arr) {
    if (arr == null) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

// for test
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 (!isEqual(arr1, arr2)) {
            succeed = false;
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "***ing ***ed!");

    int[] arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    bubbleSort(arr);
    printArray(arr);
}

}

六：小和问题和逆序对问题

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：

[1,3,4,2,5]

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。

 package basic_class_01;

 public class Code_12_SmallSum {

public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    return mergeSort(arr, 0, arr.length - 1);
}

public static int mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return 0;
    }
    int mid = l + ((r - l) >> 1);
    return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}

public static int merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    int res = 0;
    while (p1 <= m && p2 <= r) {
        res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
    return res;
}

// for test
public static int comparator(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int res = 0;
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            res += arr[j] < arr[i] ? arr[j] : 0;
        }
    }
    return res;
}

// for test
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) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
}

// for test
public static int[] copyArray(int[] arr) {
    if (arr == null) {
        return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        res[i] = arr[i];
    }
    return res;
}

// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
        return false;
    }
    if (arr1 == null && arr2 == null) {
        return true;
    }
    if (arr1.length != arr2.length) {
        return false;
    }
    for (int i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

// for test
public static void printArray(int[] arr) {
    if (arr == null) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

// for test
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);
        if (smallSum(arr1) != comparator(arr2)) {
            succeed = false;
            printArray(arr1);
            printArray(arr2);
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "***ing ***ed!");
}

}