点击使用幕布网页版查看(含思维导图)

有序度:数组中具有有序关系的元素对的个数

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
有序元素对:a[i] <= a[j],如果i < j。

完全有序的数组,有序度就是 n * (n - 1) /2(满有序度)

逆序度 = 满有序度 - 有序度
  • 冒泡排序
    • 特性

      • 原地
      • 稳定
      • O(n**2)(最少0次交换,最多n*(n-1)/2次交换)
    • 冒泡排序每次比较相邻两数,若为逆序则交换,所以冒泡排序交换次数总是确定的,即为逆序度。

  • 插入排序

    • 特性

      • 原地
      • 稳定
      • O(n**2)(将一个数据插入数组(O(n)),重复n次)
    • 插入排序将数组分为两个区间:已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组首元素。每次取未排序区间元素在已排序区间中找到合适的位置插入,直到未排序区间为空。插入排序移动操作的次数是固定的,等于逆序度。

  • 两种排序算法比较

    • 虽然两种排序算法相同,都是原地、稳定排序,但插入排序要比冒泡排序更优

    • 冒泡排序交换次数和插入排序数据移动次数一样,都等于逆序度

    • 冒泡排序数据交换需要3个赋值操作,而插入排序数据移动只需要1个。

冒泡排序和插入排序Java实现

public class Sort {
    /**
     * 冒泡排序
     *
     * @param arr
     * @param n
     */
    public static void bubbleSort(int arr[], int n) {
        if (n <= 1) return;
        int count = 0;
        //最多进行n - 1次冒泡
        for (int i = 0; i < n; i++) {
            boolean swaped = false;
            for (int j = 0; j < n - i - 1; j++) {
                //每次比较相邻数 把较大的放在后面
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    swaped = true;
                }
            }
            count++;
            if (!swaped) break;
        }
        System.out.println("进行了" + count + "次冒泡");
    }

    /**
     * 插入排序
     *
     * @param arr
     * @param n
     */
    public static void inserctionSort(int arr[], int n) {
        if (n <= 1) return;
        //将数组分为已排序部分和未排序部分
        for(int i = 1; i < n; i++) {
            int value = arr[i];//未排序部分的第一个值
            int j = i - 1;
            //每次将未排序部分的第一个值插入已排序部分中
            for(; j >= 0; j--){
                //寻找插入点 arr[j]为第一个小于等于value的值
                if(arr[j] > value)
                    arr[j + 1] = arr[j];
                else
                    break;
            }
            //将value插入到j后面
            arr[j + 1] = value;
        }
    }

    public static void sortTest() {
        int arr[] = {3, 5, 4, 1, 2, 6};
        printArr(arr);
        inserctionSort(arr, arr.length);
        printArr(arr);
    }

    public static void printArr(int arr[]) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄