算法02 七大排序之:直接选择排序和堆排序

上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。

1、直接选择排序及算法实现

2、堆排序及算法实现

1、直接选择排序及算法实现

直接选择排序(Straight Select Sort) 是一种简单的排序方法,它的基本思想是:通过length-1 趟元素之间的比较,从length-i+1个元素中选出最小的元素,并和第i个元素交换位置。直接选择排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n2)   

下图展示了直接选择排序的过程。

1-1、示意图

1-2、代码

SelectionSort.java

public class SelectionSort {
    public static void main(String[] args) {
        int[] list = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        System.out.println("************直接选择排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        selectionSort(list);
        display(list);
    }

    /**
     * 直接选择排序算法
     */
    public static void selectionSort(int[] list) {
        // 要遍历的次数(length-1次)
        for (int i = 0; i < list.length - 1; i++) {
            // 将当前下标定义为最小值下标
            int min = i;

            // 遍历min后面的数据
            for (int j = i + 1; j <= list.length - 1; j++) {
                // 如果有小于当前最小值的元素,将它的下标赋值给min
                if (list[j] < list[min]) {
                    min = j;
                }
            }
            // 如果min不等于i,说明找到真正的最小值
            if (min != i) {
                swap(list, min, i);
            }
        }
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int min, int i) {
        int temp = list[min];
        list[min] = list[i];
        list[i] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

测试结果:

2、堆排序及算法实现

堆排序(Heap Sort) 利用堆(一般为大根堆)进行排序的方法。它的基本思想是:将待排序的元素构造成一个大根堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将它与数组的末尾元素进行交换,此时末尾元素就是最大值),然后将剩余的length-1 个元素重新构造成一个大根堆,这样就会得到length个元素中的次大值。如此反复执行,便能得到一个有序的序列。

堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为大根堆;每个节点的值都小于或等于其左右孩子节点的值,称为小根堆。

堆排序的最坏时间复杂度为O(n*log2n),平均时间复杂度为O(n*log2n)   

2-1、示意图

图一:

图二:

图三:

图四:

图五:

图六:

2-2、代码

HeapSort.java

public class HeapSort {
    public static void main(String[] args) {
        int[] list = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
        System.out.println("************堆排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        heapSort(list);
        display(list);
    }

    /**
     * 堆排序算法
     */
    public static void heapSort(int[] list) {
        // 将无序堆构造成一个大根堆,大根堆有length/2个父节点
        for (int i = list.length / 2 - 1; i >= 0; i--) {
            headAdjust(list, i, list.length);
        }

        // 逐步将每个最大值的根节点与末尾元素交换,并且再调整其为大根堆
        for (int i = list.length - 1; i > 0; i--) {
            // 将堆顶节点和当前未经排序的子序列的最后一个元素交换位置
            swap(list, 0, i);
            headAdjust(list, 0, i);
        }
    }

    /**
     * 构造大根堆
     */
    public static void headAdjust(int[] list, int parent, int length) {
        // 保存当前父节点
        int temp = list[parent];

        // 得到左孩子节点
        int leftChild = 2 * parent + 1;

        while (leftChild < length) {
            // 如果parent有右孩子,则要判断左孩子是否小于右孩子
            if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
                leftChild++;
            }
            // 父亲节点大于子节点,就不用做交换
            if (temp >= list[leftChild]) {
                break;
            }
            // 将较大子节点的值赋给父亲节点
            list[parent] = list[leftChild];
            // 然后将子节点做为父亲节点
            parent = leftChild;
            // 找到该父亲节点较小的左孩子节点
            leftChild = 2 * parent + 1;
        }
        // 最后将temp值赋给较大的子节点,以形成两值交换
        list[parent] = temp;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int top, int last) {
        int temp = list[top];
        list[top] = list[last];
        list[last] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

测试结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

排序算法-冒泡排序

算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

35570
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

20990
来自专栏小樱的经验随笔

C/C++中连接函数strcat的应用(简单讲解)

有位学弟问到我如何将两个字符连接起来,想想java/python里面可以直接用+连接起来,可是C/C++里面有没有这么方便的做法呢?

12020
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

15820
来自专栏小小挖掘机

各种排序算法的分析及java&python实现

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

40370
来自专栏noteless

[一]基础类型概述

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

13530
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第4章 NumPy基础:数组和矢量计算4.1 NumPy的ndarray:一种多维数组对象4.2 通用函数:快速的元素级数组函数4.3 利用数组进行数据处理4.

NumPy(Numerical Python的简称)是Python数值计算最重要的基础包。大多数提供科学计算的包都是用NumPy的数组作为构建基础。 NumPy...

46480
来自专栏机器学习和数学

[编程经验]Python中的Lambda,Map, Reduce小结

今天要和大家分享的是Python匿名函数(anonymous functions),也叫lambda函数。匿名函数的意思就是说这个函数没有显式的函数名,因为一般...

33750
来自专栏五分钟学算法

五分钟弄懂有点难度的排序:堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

15140
来自专栏技术沉淀

Python: 函数式编程

17440

扫码关注云+社区

领取腾讯云代金券