算法(三)初等排序后篇[选择和冒泡排序]

本文首发于微信公众号「刘望舒」

1.选择排序

根据上一篇文章讲到的插入排序和希尔排序,我们把选择排序的数组也分为已排序部分和未排序部分。

图解选择排序

在用图来讲解选择排序之前,我们要先了解选择排序的规则。
选择排序的规则
就是重复执行以下的处理:
1.找出未排序部分最小值的位置min。
2.将min位置的元素与未排序部分的起始元素做对比,如果顺序错误则将它们进行就交换。

以数组a={5,4,8,7,9,3,1}为例,我们对其进行从小到大排序,排序过程如下图所示。

VmVXw9.png
首先我们找到未排序部分最小的值a[6]=1和未排序的起始元素a[0]=5相比较,发现a[6]的值更小,则将两个数进行交换,以此类推。
VmVjoR.png

最终得到的结果为a={1,3,4,5,7,8,9}

实现选择排序

接下来要实现插入排序,针对下图来定义变量。
VmVqL4.png

如上图所示,i为循环变量,代表未排序部分的开头元素; j为循环变量,用来遍历未排序部分找出最小值min。
接下来我们用代码来实现选择排序,如下所示。

public class SelectionSort {
    public static void main(String[] args) {
        int a[] = {5, 4, 8, 7, 9, 3, 1};
        ArrayUtils.printArray(a);
        int b[] = selection(a);
        ArrayUtils.printArray(b);
    }

    public static int[] selection(int[] a) {
        int i, j, min, v;
        int n = a.length;
        for (i = 0; i < n; i++) {
        //每次将未排序部分的首元素下标赋值给下标min
            min = i;
            //得到未排序部分的最小值的下标并赋值给min
            for (j = i+1; j < n; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            v = a[i];
            a[i] = a[min];
            a[min] = v;
        }
        return a;
    }
}

其中负责打印数组的ArrayUtils类如下所示。

public class ArrayUtils {
    public static void printArray(int[] array) {
        System.out.print("{");
        int len=array.length;
        for (int i = 0; i < len; i++) {
            System.out.print(array[i]);
            if (i < len - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("}");
    }
}

输出结果为:
{5, 4, 8, 7, 9, 3, 1}
{1, 3, 4, 5, 7, 8, 9}

选择排序复杂度

假设数据总数为n,则为了搜索未排序部分最小的的值需要(n-1)+(n-2)+(n-3)+……+1次比较,也就是n²/2+n/2次比较,因此时间复杂度为O(n²)。同样的,此前讲过的插入排序和冒泡排序的时间复杂度也是O(n²)。它们的区别就是:不含flag的冒泡算法和选择排序并不依赖于比较运算的次数,不受输入数据的影响,而插入算法却依赖于比较运算的次数,处理某些数据时会具有很高的效率。

2.冒泡排序

冒泡排序应该是开发者最容易理解的排序算法,它的基本思想就是每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。需要进行排序的元素则向水中的气泡一样慢慢的移向水面。

图解冒泡排序

与选择排序一样,需要进行冒泡排序的数组也分为已排序部分和未排序部分。
冒泡排序的规则为:从数组末尾开始依次比较相邻的两个元素,如果大小关系相反则交换位置,直到数组中不再有顺序相反的相邻元素。

我们对数组 a={5,3,2,4,1} 进行从小到大排序,排序过程如下所示。
第一轮排序:

VmVOeJ.png

我们将数组末尾的a[4]的值和a[3]的值进行对比,发现a[4]的值比a[3]的值小,则将它们交换,再接着对剩下的相邻的两个元素进行对比和交换,最终得到的结果为a={1,5,3,2,4},已排序的部分的元素为1。

第二轮排序:

VmVxF1.png

首先对比a[3]和a[4]的值,发现a[3]的值比a[4]的值小,则不需要进行排序。最终得到的结果为a={1,2,5,3,4},已排序部分的元素为1、2。

第三轮排序:
VmZSW6.png

经过第三轮排序,已排序部分的元素为1、2、3。

第四轮排序:

VmVzJx.png

经过四轮排序我们最终得到的结果为a={1,2,3,4,5}

实现冒泡排序

实现插入排序时,我们要先定义两个变量,i为循环变量,表示未排序部分的开头元素,从数组开头向末尾移动。j也为循环变量,用于对未排序部分中相邻元素两两比较,从数组的末尾n-1开始减小到 i 结束(i=1)。

VmZ9SK.png

代码实现如下所示。

public class BubbleSort {
    public static void main(String[] args) {
        int a[] = {5, 3, 2, 4, 1};
        ArrayUtils.printArray(a);
        int b[] = bubble(a);
        ArrayUtils.printArray(b);
    }
    public static int[] bubble(int[] a) {
        int i, j, v;
        int n = a.length;
        for (i = 0; i < n - 1; i++) {
            for (j = n - 1; j > i; j--) {
                if (a[j] < a[j - 1]) {
                    v = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = v;
                }
            }
        }
        return a;
    }
}

其中ArrayUtils的printArray方法此前讲过,这里就不再给出,打印结果为:
{5, 3, 2, 4, 1}
{1, 2, 3, 4, 5}

当然有的同学不喜欢这样从数组的末尾开始比较,这里给出常规的冒泡,如下所示。

public class BubbleSort2 {
    public static void main(String[] args) {
        int a[] = {5, 3, 2, 4, 1};
        ArrayUtils.printArray(a);
        int b[] = bubble(a);
        ArrayUtils.printArray(b);
    }
    public static int[] bubble(int[] a) {
        int i, j, v;
        int n = a.length;
        for (i = 0; i < n - 1; i++) {
            for (j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    v = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = v;
                }
            }
        }
        return a;
    }
}

冒泡排序的复杂度

最坏的情况下,冒泡排序对未排序部分的相邻元素进行了(n-1)+(n-2)+(n-3)+……+1次比较,也就是n²/2-n/2次比较,根据推导大O阶的规则我们得出冒泡排序的时间复杂度为O(n²)。

github源码

分享到 评论

分享大前端、Java、Android、 跨平台等技术,关注职业发展和行业动态。

---