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

一、权衡一个排序算法

1.1、排序算法的执行效率

  1. 最好情形、最坏情形、平均情形时间复杂度
  2. 时间复杂度的系数、常数 、低阶
    时间复杂度反映的是数据规模 n 很大的时刻的一个增进趋势,以是它示意的时刻会忽略系数、常数、低阶。
    然则现实的软件开发中,我们排序的可能是10个、 100个、 1000个这样规模很小的数据,以是,在对同一阶时间复杂度的排序算法性能对比的时刻,我们就要把系数、常数、低阶也思量进来。
  3. 对照次数和交流(或移动)次数
    冒泡、插入、选择都是基于对照的排序算法。基于对照的排序算法的执行历程,会涉及两种操作,一种是元素对照巨细,另一种是元素交流或移动。
    以是,若是我们在剖析排序算法的执行效率的时刻,应该把对照次数和交流(或移动)次数也思量进去。

1.2、排序算法的内存消耗

  • 算法的内存消耗可以通过空间复杂度来权衡,排序算法也不破例。
  • 不外,针对排序算法的空间复杂度,另有一个新的观点, 原地排序(Sorted in place)。
    原地排序算法,就是特指空间复杂度是 O(1) 的排序算法。我们今天讲的三种排序算法,冒泡、插入、选择原地排序算法。

1.3、排序算法的稳固性

  • 若是待排序的序列中存在值相等的元素,经由排序之后,相等元素之间原有的先后顺序稳固。
  • 好比一组数据 2, 9, 3, 4, 8, 3,根据巨细排序之后就是 2, 3, 3, 4, 8, 9。
  • 这组数据里有两个 3。经由某种排序算法排序之后,若是两个 3 的前后顺序没有改变,那我们就把这种排序算法叫作稳固的排序算法。
  • 若是前后顺序发生变化,那对应的排序算法就叫作不稳固的排序算法。

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

二、冒泡排序

  • 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素举行对照。
  • 看是否知足巨细关系要求。若是不知足就让它俩交换。一次冒泡会让至少一个元素移动到它应该在的位置。
  • 重复 n 次,就完成了 n 个数据的排序事情。
  • 冒泡的历程只涉及相邻数据的交流操作,只需要常量级的暂且空间,以是它的空间复杂度为 O(1),是一个原地排序算法
  • 在冒泡排序中,只有交流才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳固性,当有相邻的两个元素巨细相等的时刻。
  • 我们不做交流,

    面试问题—JAVA程序CPU占用过高怎么定位

    相同巨细的数据在排序前后不会改变顺序,以是冒泡排序是稳固的排序算法

  • 最好情形下,要排序的数据已经是有序的了,我们只需要举行一次冒泡操作,就可以竣事了,以是最好情形时间复杂度是 O(n)
  • 而最坏的情形是,要排序的数据刚好是倒序排列的,我们需要举行 n 次冒泡操作,以是最坏情形时间复杂度为 O(n²)

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

可以看出,经由一次冒泡操作之后, 6这个元素已经存储在准确的位置上。要想完成所有数据的排序,我们只要举行6次这样的冒泡操作就行了。
三、排序之冒泡、插入、选择

public static void bubbleSort(int[] arr) {
    if (arr.length <= 1)
        return;
    for (int i = 0; i < arr.length; i++) {
        boolean b = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                b = true;
            }
        }
        if (!b) {
            break;
        }
    }
}

三、插入排序(Insertion Sort)

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

  • 将数组中的数据分为两个区间, 已排序区间和未排序区间。
  • 初始已排序区间只有一个元素,就是数组的第一个元素。
  • 插入算法的焦点头脑是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。
  • 重复这个历程,直到未排序区间中元素为空,算法竣事。

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

  • 插入排序算法的运行并不需要分外的存储空间,以是空间复杂度是 O(1),也就是说,这是一个原地排序算法
  • 在插入排序中,对于值相同的元素,我们可以选择将后面泛起的元素,插入到前面泛起元素的后面,这样就可以保持原有的前后顺序稳固,
  • 以是插入排序是稳固的排序算法
  • 若是要排序的数据已经是有序的,我们并不需要搬移任何数据。
  • 若是我们从尾到头在有序数据组内里查找插入位置,每次只需要对照一个数据就能确定插入的位置。
  • 以是这种情形下,最好是时间复杂度为 O(n)。注重,这里是从尾到头遍历已经有序的数据。
  • 若是数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,以是需要移动大量的数据,以是最坏情形时间复杂度为O(n²)
  • 在数组中插入一个数据的平均时间复杂度是 O(n)。以是,对于插入排序来说,每次插入操作都相当于在数组中插入一个数据,循环执行n次插入操作,以是平均时间复杂度为O(n2)。
public static void insertionSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) {
        return;
    }
    for (int i = 0; i < n; i++) {
        int value = arr[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; --j) {
            if (arr[j] > value) {
                arr[j + 1] = arr[j];//移动数据
            } else {
                break;
            }
        }
        arr[j + 1] = value;//插入数据
    }
}

四、选择排序(Selection Sort)

  • 选择排序空间复杂度为 O(1),是一种原地排序算法。
  • 选择排序的最好情形时间复杂度、最坏情形和平均情形时间复杂度都为O(n²)
  • 选择排序是一种不稳固的排序算法,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交流位置,这样破坏了稳固性。
public static void selectionSort(int[] arr) {
    int length = arr.length;
    if (length == 1) {
        return;
    }
    int x;
    for (int i = 0; i < length; i++) {
        x = i;
        for (int j = i + 1; j < length; j++) {
            if (arr[x] > arr[j]) {
               x = j;
            }
        }
        if(x != i){
            int tmp = arr[i];
            arr[i] = arr[x];
            arr[x] = tmp;
        }
    }
}

总结一下

空间复杂度 是否稳固 最好时间复杂度 最坏时间复杂度 平均时间复杂度
冒泡排序 Q(1) Q(n) Q(n²) Q(n²)
插入排序 Q(1) Q(n) Q(n²) Q(n²)
选择排序 Q(1) Q(n²) Q(n²) Q(n²)

原创文章,作者:28x29新闻网,如若转载,请注明出处:https://www.28x29.com/archives/13424.html