冒泡、插入和选择

冒泡、插入和选择

首先看一下三个排序算法的比较:

img

冒泡可能是我们最早接触的算法了,他和选择排序一样,只能用来开阔思维,并没有什么实际应用,具体为什么,后面会详细说

如何衡量一个排序算法的性能:

  • 最好、最坏、平均时间复杂度

每个排序算法要处理的数据中,逆序对是不同的,对于逆序对不同的数据集,不同的算法之间进行比较很大的说服力,不仅在排序中,在其他的算法问题中,都是需要思考最好最坏情况的

  • 比较和交换次数
  • 内存消耗:如果没有额外的内存消耗,那么就称之为原地算法
  • 稳定性:相同值的元素比较前后顺序不发生改变,可能我们比较的是数字感觉不到什么,但是当我们比较的是一个对象的时候,就可能出现问题,因为如果对象的key要是数字,但是value不是数字的话,就不允许发生前后顺序的改变

冒泡排序

之前应该也是写过一篇关于冒泡排序的文章,这里对三个排序算法进行一个合并总结,基础的理念不赘述了,这里直接写一个优化后的冒泡排序,可以通过增加一个flag的方法,如果在一遍的比较过程中并没有发生元素交换的行为,也就是flag为flase,那么接下来就没有再比较下去的必要,提前结束循环

package sort;
import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {6,5,4,3,2,1};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void bubbleSort(int[] a){
        if(a.length <= 1)   return;
        for (int i = 0; i < a.length - 1; i++) {
            boolean flag = false;
            for (int j = i + 1; j < a.length; j++) {
                if(a[j] < a[i]){
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                    flag = true;
                }
            }
            if(!flag)   break;
        }
    }
}

可以看出,冒泡并没有使用额外的空间,而且是一个稳定排序,这取决于if(a[j] < a[i])

当前后两个数字相等的时候,并没有进行交换,而是直接跳过,如果加上=,就破坏了稳定性,所以说写冒泡排序的时候以为加上=没有问题,不影响最后的排序结果,但是却破坏了稳定性

时间复杂度:

最好情况,只遍历一次,需要进行n-1次比较,时间复杂度为O(n)

最坏情况下,数组完全就是倒序的,那么就需要n-1ci遍历,每次遍历需要n-1次交换,时间复杂度为O(n2)

插入排序

为什么要将这三种算法放在一起写呢,因为这三种排序算法具有很大的相似性,都是基于比较的,并且总体上都是将一个数组大概分成了两部分,分别是有序的和无序的,而他们做的事情都是为了将无序的那一部分减少为0

来看一下插入排序的思想,默认数组的第一个元素已经是有序的,那么从第二个元素开始,和之前的元素进行比较,找到合适的位置并进行插入操作,同样需要数组的移动

Talk is cheap,show me the code

package sort;
import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {6,5,4,3,2,1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void insertSort(int[] a){
        for (int i = 1;i < a.length; i++){
            int value = a[i];
            int j = i - 1;
            for(;j >= 0;j--){
                if(a[j] > value){
                    a[j+1] = a[j];
                }else{
                    break;
                }
            }
            a[j+1] = value;
        }
    }
}

思想就是每个未排序的元素在已排序的元素中合适合适的插入位置,

找的过程也是数据移动的过程,一定不是进行就交换,而是进行覆盖,从这个角度来讲,当数据量达到一定规模之后,插入排序的性能会比冒泡排序的更好,因为冒泡排序要进行交换操作,一定要执行三步,而插入排序中只是将前面元素覆盖后一个元素,提前将要插入的元素保存起来,最后找到位置之后再插进去就可以了

这里有一个编程技巧值得学习,就是在这个循环条件中, int j = i - 1;for(;j >= 0;j--),将循环因子定义在了内层循环的外面,之前对这种操作不以为意,但是这次却发现有起效,这样定义之后就可以在外层循环中访问到j变量,进行赋值操作

下面来看一下插入排序的性能分析:

这还是一个原地算法,并没有开辟额外的内存空间,当然冒泡排序和插入排序都使用了一个临时变量,这里可以忽略不计了,同样,这也是一个稳定算法,在待插入的元素往前面比较的过程中,如果发现和自己相等的元素,那么就不再进行数据的一定,而是直接插入就好了

时间复杂度分析:

如果待排序数组本来就是有序的,那么每个元素每次只需要进行一次比较就可以确定要插入的位置,时间复杂度为O(n)

如果数组是倒序的,,那么每次插入都要在数组的第一个元素进行,要进行大量的比较和交换,时间复杂度为O(n2)

选择排序

错误代码演示

!!!注意,这是有问题的
package sort;
import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {6,5,4,3,2,1};

        System.out.println(Arrays.toString(arr));
    }
    public static void selectSort(int[] a){
        for (int i = 0; i < a.length; i++) {
            int minIndex = selectMin(a,i);
            swap(a,i,minIndex);
        }
    }
    //i 起始下标,,这个方法用来从给定下标范围的数组中选出最小值下标
    public static int selectMin(int[] a,int i){
        int min = a[i];
        int minIndex = i;
        for (int j = i; j < a.length; j++) {
            if(a[j] < min){
                min = a[j];
                minIndex = j;
            }
        }
        return minIndex;
    }
    //交换方法
    public static void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

抽象出了两个方法,分别是从待排序数组中选出一个最小索引的方法和给定两个索引进行交换的方法,因为这里面交换时候是a[i] = a[j];这样的形式,所以说没什么问题,但是当交换的两个对象为引用数据类型时,就会出现问题,这里面a[j]就是基本数据类型的意思了, 可以进行直接的赋值,而且swap函数中的a[i]和main方法中的a[i]指向的是同一对象数组,修改有效

选择排序的思想和额插入排序非常类似,也是将数组分为两个部分,有序的和待排序的,插入排序每次是操作处理待排序的第一个元素,而选择排序每次从待排序的数组中选择出一个最小的,直接放到已排序数组的后面就可以了,具体做法就是和未排序数组的第一个元素进行交换,和插入排序相比虽然节省了在有序数组中的比较和交换成本,但是在未排序数组中选择最小的元素还是需要成本的

复杂度分析

选择排序还是一种原地算法,不占用额外的空间,最好和最坏时间复杂度全部是O(n2),因为即使一个数组是有序的,还是要进行两层循环遍历,还是要一个个的选出最小值。。。

选择排序的最大问题还是在于不稳定性,这个性质在很多的业务场景中都是不被允许的,所以还是按照开篇所说的,冒泡排序和选择排序没有太大的应用空间,但是如果非要选一个的话,还是选择插入排序,为啥呢,上面说过,冒泡要进行三次单元操作,插入只需要一个,当数据量变大的时候,CPU多的这几次指令运算还是会在性能上显示出差距的

最后呢,插入排序还有很大的优化空间,后面会追加一篇升级版希尔排序

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/冒泡插入和选择md