vlambda博客
学习文章列表

超大:排序算法之冒泡、插入和选择排序

前言:排序作为算法中最基础的一环,相信大部分程序员不会陌生。但是排序算法分类众多,从复杂度来看,O(n^2)的有冒泡、插入、选择排序等;O(nlogn)的有快速、合并排序等;O(n)的有桶、基数排序等。下面几章会分别介绍这些排序算法,希望大家在看的同时,也可以动手实操一下,加深理解。

今天来讲讲最经典的冒泡和插入排序,我们都知道他们的时间复杂度都为O(n^2),那么在实际应用时会考虑使用哪个呢?你的考虑方向是什么呢?
带着这个问题,我们先来介绍如何分析“排序算法”。

  1. 执行效率
    1.1 最好、最坏、平均时间复杂度
    1.2 时间复杂度的系数
    1.3 比较的次数和交换次数

  2. 内存消耗
    即指之前提到的空间复杂度,引入一个原地排序(特指空间复杂度为O(1)的排序)

  3. 稳定性
    待排序的序列中存在值相等的元素时,经过排序后相等的元素之间原有的先后顺序是否改变
    为什么要考虑稳定性呢?
    可解决下面这种场景。对交易系统中的“订单”进行排序。订单中有两个属性,下单时间和下单金额。希望根据下单金额大小对订单数据排序。金额相同的订单按照下单时间从早到晚排序。
    如果按照常规思路,先按照金额对订单数据进行排序,然后再遍历对金额相同的小区间进行下单时间排序,实现起来会很复杂。
    通过稳定排序算法,可以先对下单时间进行排序,再对下单金额进行排序,可以很方便的实现。


冒泡 VS 插入

冒泡排序

n个待排序的序列,经过n-1个循环每次经过(n-已经排完数-1)的交换,把较大数依次放到相应的位置,完成排序。

    private static void sort(int[] a){
int length = a.length;
//外循环需要n-1
for (int i = 0; i < length - 1; i++) {
//每次都比要少一个i的交换
for (int j = 0; j < length- i - 1; j++) {
if(a[j] > a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
  • 优化点:若内循环已经没有交换,说明整个待排序列已经排好序。直接退出。

    private static void sort(int[] a){
int length = a.length;
//外循环需要n-1
for (int i = 0; i < length - 1; i++) {
boolean flag = false;
//每次都比要少一个i的交换
for (int j = 0; j < length- i - 1; j++) {
if(a[j] > a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
flag = true;
}
}
//没有交换的话说明已经排好序
if(!flag) break;
}
}

冒泡分析:

  1. 因为只涉及一个常量级的临时空间开辟,所以为原地排序。

  2. 因为交换时只在>时进行交换,所以是具有稳定性的。

  3. 时间复杂度,最好情况下只需要一次冒泡,复杂度为O(n);最坏情况逆序下需要n次冒泡,复杂度为O(n^2)。平均时间复杂度可以分析交换次数。交换次数又可以通过有序度来分析。有序度定义如下:

有序元素对:a[i] <= a[j], 如果 i < j

  最好的情况下有序度为n*(n-1)/2,即不需要交换。最坏的情况下有序度为0,即需要n*(n-1)/2次交换。平均就是n*(n-1)/4,即为O(n^2)。

插入排序

通过遍历数组,找到数据应该插入的位置进行插入。
核心思想为:取未排序区间中的元素,在已排序区间中找到合适的位置进行插入,并保证已排序区间数据一直有序。

public static void sort(int[] a){
int length = a.length;
//轮到数组中下标为i的数进行插入
for (int i = 1; i < length; i++) {
int j = i-1;
int value = a[i];
//j下标前为已排序的序列 寻找插入位置
for (; j>=0; j--) {
if(a[j] > value){
a[j+1] = a[j];
}else {
break;
}
}
a[j+1] = value;

}
}

插入分析:

  1. 因为不涉及开辟临时空间,所以肯定为原地排序。

  2. 移动数组的条件为>,因此可以把后进行排序的数安排到已排序序列中相同数后边。

  3. 时间复杂度,最好的情况为只需要进行判断而不用进行交换操作,即O(n)。最坏为O(n^2)。

选择排序

跟插入排序类似,分为已排序区域和未排序区域。每次都从未排序区域中选择最小值和未排序区中最小index的值进行交换。直接贴代码:

    public static void sort(int[] a){
int length = a.length;
//未排序的区域
for (int i = 0; i < length; i++) {
//设置未排序区域的最小值
int min = a[i];
//未排序区域的最小index
int index = i;
for (int j = i+1; j < length; j++) {
if(a[j] < min){
min = a[j];
index = j;
}
}
//交换
int temp = a[i];
a[i] = min;
a[index] = temp;
}
}

选择分析:

  1. 空间复杂度为O(1),为原地排序

  2. 最好、最坏、平均空间复杂度都为O(n^2)

  3. 因为会有和已排序最小index进行交换,所以会破坏原有相等值的前后顺序,为不稳定排序