【恋上数据结构】冒泡排序、选择排序、堆排序

简介: 【恋上数据结构】冒泡排序、选择排序、堆排序

经典的十大排序算法!
在这里插入图片描述
我的《恋上数据结构》源码(第1季 + 第2季):https://github.com/szluyu99/Data_Structure_Note

前言

请==务必==看一下这个:排序算法前置知识+代码环境准备

当上面的内容都准备好以后,那就从冒泡排序开始吧。

冒泡排序

冒泡排序也叫做起泡排序

执行流程

  • ① 从头开始比较每一对相邻元素,如果第1个比第2个大,就交换它们的位置
    执行完一轮后,最未尾那个元素就是最大的元素。
  • ② 忽略①中曾经找到的最大元素,重复执行步骤①,直到全部元素有序。

这是一个标准的冒泡排序。

/**
 * 冒泡排序-无优化
 */
public class BubbleSort1<T extends Comparable<T>> extends Sort<T>{
    
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                }
            }
        }
    }
    
}

冒泡排序-优化1

这个优化并不会提高冒泡排序的平均性能,只是针对极端条件进行处理

如果序列已经完全有序,可以提前终止冒泡排序。
在这里插入图片描述

/**
 * 冒泡排序-优化1
 * 如果序列已经完全有序,可以提前终止冒泡排序
 */
public class BubbleSort2<T extends Comparable<T>> extends Sort<T>{
    
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            boolean sorted = true;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }
    
}

冒泡排序-优化2

这个优化是在优化1的基础上,增大极端条件的范围,从完全有序变为尾部局部有序

如果序列==尾部==已经局部有序,可以记录最后1次交换的位置,减少比较次数。

在这里插入图片描述

/**
 * 冒泡排序-优化2
 * 如果序列尾部已经局部有序,可以记录最后1次交换的位置,减少比较次数
 */
public class BubbleSort3<T extends Comparable<T>> extends Sort<T>{
    
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            // 设为1是因为:如果这轮遍历一次交换都没进行
            // 则说明序列后面已经有序, 则 end = sortedIndex = 1
            // end--后等于0,会直接跳出循环
            int sortedIndex = 1; 
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    // 记录最后1次交换的位置,减少比较次数
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }

}

复杂度与稳定性

再强调一下,请==务必==看一下这个:排序算法前置知识+代码环境准备

最坏、平均时间复杂度: $O(n^2)$
最好时间复杂度: $O(n)$
空间复杂度: $O(1)$
冒泡排序属于 In-place
冒泡排序属于稳定的排序算法

稍有不慎,稳定的排序算法也能被写成不稳定的排序算法,比如下面的冒泡排序代码是不稳定的。
在这里插入图片描述

选择排序

执行流程:

  • ① 从序列中找出最大的那个元素,然后与最未尾的元素交换位置

执行完一轮后,最未尾的那个元素就是最大的元素。

  • ② 忽略①中曾经找到的最大元素,重复执行步骤①。
/**
 * 选择排序
 */
public class SelectionSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int max = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(max, begin) < 0) {
                    max = begin;
                }
            }
            swap(max, end);
        }
    }
    
}

生成 20000 个取值在[1, 10000] 的随机数进行排序:
在这里插入图片描述
选择排序的交换次数要远远少于冒泡排序,平均性能优于冒泡排序

复杂度与稳定性

  • 最好、最坏、平均时间复杂度:$O(n^2)$
  • 空间复杂度:$O(1)$
  • 选择排序属于不稳定排序

选择排序是否还有优化的空间?

  • 使用堆来选择最大值,可以大大提高选择速度

堆排序

堆排序的前提是了解 堆的知识点

执行流程:

  • ① 对序列进行原地建堆(heapify)
  • ② 重复执行以下操作(依次取出堆中最大值,并删除),直到堆的元素数量为 1

    • 交换堆顶元素与堆尾元素(把最大值放到最后面)
    • 堆的元素数量减 1(不管最后已经放到最后的最大值)
    • 对 0 位置进行 1 次 siftDown 操作

堆排序图解

在这里插入图片描述
对 {50, 21, 80, 43, 38, 14} 进行原地建堆。
在这里插入图片描述
重复执行以下操作,直到堆的元素数量为 1:

  • 交换堆顶元素与尾元素
  • 堆的元素数量减 1
  • 对 0 位置进行 1 次 siftDown 操作

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

堆排序实现

原地建堆:自下而上的下滤建堆
在这里插入图片描述
下滤:其实就是堆删除元素后,恢复堆的性质
在这里插入图片描述

完整源码:

/**
 * 堆排序
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    private int heapSize; // 堆大小

    @Override
    protected void sort() {
        // 原地建堆(自下而上的下滤)
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        
        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, --heapSize);

            // 对0位置进行siftDown(恢复堆的性质)
            siftDown(0);
        }
    }
    
    private void siftDown(int index) {
        T element = array[index];
        
        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];
            
            int rightIndex = childIndex + 1;
            // 右子节点要存在, 并且比左子节点大
            if (rightIndex < heapSize && 
                    cmp(array[rightIndex], child) > 0) { 
                child = array[childIndex = rightIndex];
            }
            
            // 大于等于子节点
            if (cmp(element, child) >= 0) break;
            
            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }

}

生成 20000 个取值在[1, 10000] 的随机数进行排序:
在这里插入图片描述

复杂度与稳定性

  • 最好、最坏、平均时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(1)$
  • 堆排序属于不稳定排序
相关文章
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
74 0
数据结构与算法学习十八:堆排序
|
2月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
21 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
4月前
|
存储 算法 搜索推荐
【初阶数据结构篇】冒泡排序和快速排序(中篇)
与直接插入排序法相比,比较次数一致,但冒泡排序的交换需要执行三次,而直接插入排序因为使用了tmp临时变量存储要插入的数据,只用执行一次,所以直接插入排序法效率明显更高。
35 1
|
5月前
|
存储 算法
【数据结构】堆,堆的实现,堆排序,TOP-K问题
数据结构——堆,堆的实现,堆排序,TOP-K问题
51 1
【数据结构】堆,堆的实现,堆排序,TOP-K问题
|
5月前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
|
4月前
|
搜索推荐 算法
【初阶数据结构篇】插入、希尔、选择、堆排序介绍(上篇)
堆排序(Heapsort)是指利⽤堆积树(堆)这种数据结构所设计的⼀种排序算法,它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆,排降序建⼩堆。
21 0
|
4月前
|
算法
【初阶数据结构篇】堆的应用(堆排序与Top-K问题)
即求数据结合中前K个最⼤的元素或者最⼩的元素,⼀般情况下数据量都⽐较⼤。
51 0
|
5月前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
137 9
|
25天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1