15. 算法之排序算法

news/2024/10/30 15:20:20/

前言

排序是在软件开发中经常遇到的需求。比如基于订单的创建时间倒排，基于金额大小排序等等，那么这些排序底层是怎么写的呢，本节，我们就常用排序算法展开介绍。

1. 冒泡排序

1.1 算法思想

冒泡排序是最基础的排序算法。冒泡排序的英文是bubble sort，它是一种基础的交换排序。
冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。
按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

1.2 代码实现

package org.wanlong.sort;/*** @author wanlong* @version 1.0* @description: 冒泡排序* @date 2023/6/6 13:38*/
public class BubbleSort {public static int[] sort(int[] nums) {for (int i = 0; i < nums.length - 1; i++) {for (int j = 0; j < nums.length - 1; j++) {//临时变量 用于交换int tmp = 0;if (nums[j] > nums[j + 1]) {tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}return nums;}
}

1.3 测试验证

@Test
public void testBubble(){int[] nums = new int[]{5, 8, 6, 3, 9, 2, 1, 7};for (int i : BubbleSort.sort(nums)) {System.out.println(i);}
}

运行结果：

1
2
3
5
6
7
8
9

1.4 冒泡排序优化

1.4.1 优化项：

  1. 已经循环过的不需要再遍历，每次外层循环会将一个元素移动到最左边或者最右边，为此，内层循环遍历的时候不需要每次都遍历整个数组
  2. 在外层循环处，设置标志isSort，默认为排好，如果不交换则跳出本次循环，说明所有元素有序，可以不继续了

1.4.2 代码实现

/**
* @Description: 排序优化
* @Author: wanlong
* @Date: 2023/6/6 13:51
* @param nums:
* @return int[]
**/
public static int[] sort2(int[] nums) {//是否已排序标识boolean isSort=true;for (int i = 0; i < nums.length - 1; i++) {//优化1，每次循环迭代会将最大的元素移动到末尾，所以内存循环不需要移动到末尾元素for (int j = 0; j < nums.length - 1-i; j++) {//临时变量 用于交换int tmp = 0;if (nums[j] > nums[j + 1]) {//有交换说明还没排好序，标识设置为falseisSort=false;tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}//排好了跳出循环if (isSort){break;}}return nums;
}

1.4.3 测试验证

@Test
public void testBubble2(){int[] nums = new int[]{5, 8, 6, 3, 9, 2, 1, 7};for (int i : BubbleSort.sort2(nums)) {System.out.println(i);}
}

运行结果：

1
2
3
5
6
7
8
9

2. 快速排序

2.1 算法思想

2.1.1 简介

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，这种思路就叫作分治法。
在这里插入图片描述

2.1.2 基准元素选择

基准元素，英文是pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
我们可以随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。
在这里插入图片描述

2.1.3 元素的交换

选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。

2.1.3.1 双边循环法

  1. 选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素
    在这里插入图片描述

  2. 接下来进行第1次循环：从right指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针轮到left指针行动，让指针所指向的元素和基准元素做比较。如果小于或等于pivot，则指针向右移动；

  3. 如果大于pivot，则left指针停止移动左右指针指向的元素交换位置，由于left开始指向的是基准元素，判断肯定相等，所以left右移1位
    在这里插入图片描述

  4. 由于7>4，left指针在元素7的位置停下。这时，让left和right指针所指向的元素进行交换。
    在这里插入图片描述

  5. 进入第2次循环，重新切换到right指针，向左移动。right指针先移，动到8，8>4，继续左移。由于2<4，停止在2的位置

在这里插入图片描述

2.1.3.2 单边循环法

单边循环法只从数组的一边对元素进行遍历和交换。
开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，
这个mark指针代表小于基准元素的区域边界。
在这里插入图片描述
接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素大于基准元素，就继续往后遍历
如果遍历到的元素小于基准元素，则需要做两件事：
第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；
第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小
于pivot的区域

  1. 遍历到元素7，7>4，所以继续遍历。
    在这里插入图片描述
  2. 遍历到的元素是3，3<4，所以mark指针右移1位
    在这里插入图片描述
  3. 让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
    在这里插入图片描述
  4. 按照这个思路，继续遍历，后续步骤如图所示
    在这里插入图片描述

2.2 代码实现

2.2.1 双边循环

package org.wanlong.sort;/*** @author wanlong* @version 1.0* @description: 快速排序* @date 2023/6/7 18:39*/
public class QuickSort {public static void quickSort(int[] arr, int startIndex, int endIndex){// 递归结束条件：startIndex大于或等于endIndex时if (startIndex >= endIndex) {return;}// 得到基准元素位置int pivotIndex = partition(arr, startIndex, endIndex);// 根据基准元素，分成两部分进行递归排序quickSort(arr, startIndex, pivotIndex - 1);quickSort(arr, pivotIndex + 1, endIndex);}/*** 分治（双边循环法）** @param arr        待交换的数组* @param startIndex 起始下标* @param endIndex   结束下标* @return*/private static int partition(int[] arr, int startIndex, int endIndex) {// 取第1个位置（也可以选择随机位置）的元素作为基准元素int pivot = arr[startIndex];int left = startIndex;int right = endIndex;while (left != right) {//控制right 指针比较并左移while (left < right && arr[right] > pivot) {right--;}//控制left指针比较并右移while (left < right && arr[left] <= pivot) {left++;}//交换left和right 指针所指向的元素if (left < right) {int p = arr[left];arr[left] = arr[right];arr[right] = p;}}//pivot 和指针重合点交换arr[startIndex] = arr[left];arr[left] = pivot;return left;}
}

2.2.2 单边循环

public class QuickSort {public static void quickSort2(int[] arr, int startIndex,int endIndex) {// 递归结束条件：startIndex大于或等于endIndex时if (startIndex >= endIndex) {return;}// 得到基准元素位置int pivotIndex = partition2(arr, startIndex, endIndex);// 根据基准元素，分成两部分进行递归排序quickSort2(arr, startIndex, pivotIndex - 1);quickSort2(arr, pivotIndex + 1, endIndex);}/*** 分治（单边循环法）** @param arr 待交换的数组* @param startIndex 起始下标* @param endIndex 结束下标* @return*/private static int partition2(int[] arr, int startIndex, int endIndex) {// 取第1个位置（也可以选择随机位置）的元素作为基准元素int pivot = arr[startIndex];int mark = startIndex;for (int i = startIndex + 1; i <= endIndex; i++) {if (arr[i] < pivot) {mark++;int p = arr[mark];arr[mark] = arr[i];arr[i] = p;}}arr[startIndex] = arr[mark];arr[mark] = pivot;return mark;}
}

2.3 测试验证

    @Testpublic void testQuickSingle(){int[] nums = new int[]{5, 8, 6, 3, 9, 2, 1, 7};QuickSort.quickSort2(nums,0,nums.length-1);for (int i : nums) {System.out.println(i);}}@Testpublic void testQuickDouble(){int[] nums = new int[]{5, 8, 6, 3, 9, 2, 1, 7};QuickSort.quickSort(nums,0,nums.length-1);for (int i : nums) {System.out.println(i);}}

运行结果和预期一致：

1
2
3
5
6
7
8
9

3. 堆排序

3.1 算法思想

堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值

之前介绍过，因为堆是完全二叉树，那么我们完全可以用数组来维护堆这种数据结构。
我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 2*(i+1)
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

  1. 构造初始堆，将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

在这里插入图片描述

  1. 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-
    1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整
    在这里插入图片描述
  2. 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换
    在这里插入图片描述
  3. 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
    在这里插入图片描述
  4. 我们就将一个无需序列构造成了一个大顶堆。将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换
    将堆顶元素9和末尾元素4进行交换

在这里插入图片描述

  1. 重新调整结构，使其继续满足堆定义
    在这里插入图片描述
  2. 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
    在这里插入图片描述
  3. 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

3.2 代码实现

package org.wanlong.sort;/*** @author wanlong* @version 1.0* @description: 堆排序* @date 2023/6/7 18:59*/
public class HeapSort {public static void sort(int[] array) {// 1. 把无序数组构建成最大堆for (int i = array.length / 2 - 1; i >= 0; i--) {adjustHeap(array, i, array.length);}// 2. 调整堆结构+交换堆顶元素与末尾元素，调整堆产生新的堆顶for (int i = array.length - 1; i > 0; i--) {// 最后1个元素和第1个元素进行交换int temp = array[i];array[i] = array[0];array[0] = temp;// “下沉”调整最大堆adjustHeap(array, 0, i);}}public static void adjustHeap(int[] array, int parentIndex, int length) {// temp 保存父节点值，用于最后的赋值int temp = array[parentIndex];int childIndex = 2 * parentIndex + 1;while (childIndex < length) {// 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子if (childIndex + 1 < length && array[childIndex + 1] >array[childIndex]) {childIndex++;}// 如果父节点大于任何一个孩子的值，则直接跳出if (temp >= array[childIndex])break;//无须真正交换，单向赋值即可array[parentIndex] = array[childIndex];parentIndex = childIndex;//下一个左孩子childIndex = 2 * childIndex + 1;}array[parentIndex] = temp;}
}

3.3 测试验证

@Test
public void testHeapSort(){int[] nums = new int[]{5, 8, 6, 3, 9, 2, 1, 7};HeapSort.sort(nums);for (int i : nums) {System.out.println(i);}
}

4. 计数排序

4.1 算法思想

计数排序，这种排序算法是利用数组下标来确定元素的正确位置的。

假设数组中有10个整数，取值范围为0～10，要求用最快的速度把这10个整数从小到大进行排序。
可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0
假设数组数据为：9，1，2，7，8，1，3，6，5，3
下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加1操作
例如第1个整数是9，那么数组下标为9的元素加1
在这里插入图片描述
当数列遍历完毕时，数组的状态如下：
在这里插入图片描述
该数组中每一个下标位置的值代表数列中对应整数出现的次数，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次，0不输出
则顺序输出是：1、1、2、3、3、5、6、7、8、9

可以看到，计数排序适合于连续的取值范围不大的数组，不连续和取值范围过大会造成数组过大
如果起始数不是从0开始，比如分数排序：
95，94，91，98，99，90，99，93，91，92
数组起始数为90，这样数组前面的位置就浪费了
可以采用偏移量的方式：
在这里插入图片描述

4.2 代码实现

package org.wanlong.sort;/*** @author wanlong* @version 1.0* @description: 计数排序* @date 2023/6/5 19:00*/
public class CountSort {public static int[] countSort(int[] array, int offset) {int[] nums = new int[array.length];for (int i = 0; i < array.length; i++) {int n = (array[i] - offset);//数字自增nums[n]++;}int[] nums2 = new int[array.length];// i是计数数组下标，k是新数组下标for (int i = 0, k = 0; i < nums.length; i++) {for (int j = 0; j < nums[i]; j++) {nums2[k++] = i + offset;}}return nums2;}
}

4.3 测试验证

@Test
public void testCountSort(){int[] nums = new int[]{95, 94, 91, 98, 99, 90, 99, 93, 91, 92};for (int i : CountSort.countSort(nums,90)) {System.out.println(i);}
}

5. 桶排序

5.1 算法思想

桶排序同样是一种线性时间的排序算法。桶排序需要创建若干个桶来协助排序。

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。

  1. 桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。

  2. 我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外， 前面各个桶的区间按照比例来确定。
    区间跨度 = （最大值-最小值）/ （桶的数量 - 1）

  3. 假设有一个非整数数列如下：
    4.5，0.84，3.25，2.18，0.5
    在这里插入图片描述

  4. 遍历原始数列，把元素对号入座放入各个桶中。
    在这里插入图片描述

  5. 对每个桶内部的元素分别进行排序（显然，只有第1个桶需要排序）
    在这里插入图片描述

  6. 遍历所有的桶，输出所有元素

5.2 代码验证

package org.wanlong.sort;import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;/*** @author wanlong* @version 1.0* @description:* @date 2023/6/3 19:01*/
public class BucketSort {public static double[] bucketSort(double[] array) {double max = 0;double min = 0;//获得最大值和最小值之间的差for (int i = 0; i < array.length; i++) {if (array[i] > max) {max = array[i];}if (array[i] < min) {min = array[i];}}double d = max - min;//桶初始化int bucketNum = array.length;ArrayList<LinkedList<Double>> bucketList =new ArrayList<LinkedList<Double>>(bucketNum);for (int i = 0; i < bucketNum; i++) {bucketList.add(new LinkedList<Double>());}//将每个元素放入桶中for (int i = 0; i < array.length; i++) {int num = (int) ((array[i] - min) * (bucketNum - 1) / d);bucketList.get(num).add(array[i]);}//对每个桶内部进行排序for (int i = 0; i < bucketList.size(); i++) {Collections.sort(bucketList.get(i));}//输出全部元素double[] sortedArray = new double[array.length];int index = 0;for (LinkedList<Double> list : bucketList) {for (double element : list) {sortedArray[index] = element;index++;}}return sortedArray;}
}

5.3 测试验证

@Test
public void testBucketSort(){double[] nums = {4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};for (double i : BucketSort.bucketSort(nums)) {System.out.println(i);}
}

6. 总结

6.1 稳定性概念介绍

如果大小相同的两个值在排序之前和排序之后的先后顺序不变，那就可以说这种排序算法是稳定的。
比如初始序列为 1,2,2,3,4
排序后序列：1,2,2,3,4
并且序列中两个2的元素顺序没有调整，则算法可认为是稳定的。反之，则算法是不稳定的

6.2 几种排序算法比较

在这里插入图片描述

6.3 适用场景

严格来说，算法的优劣不是绝对的，算法的性能取决于数据的大小，数据顺序是否已基本有序，存储空间限制等。下面列出来的是一些网上的经验总结，但是我们实际开发中，需要基于实际情况，来决定使用哪种排序算法。

  1. 当数据规模较大时，应用速度最快的排序算法，可以考虑使用快速排序。当记录随机分布的时候，快速排序平均时间最短，但是会出现最坏的情况，这个时候的时间复杂度是O(n^2)，且递归深度为n,所需的占空间为O(n)
  2. 堆排序不会出现快排那样最坏情况，且堆排序所需的辅助空间比快排要少，但是这两种算法都不是稳定的，要求排序时是稳定的，可以考虑用归并排序。
  3. 特殊的桶排序、基数排序都是稳定且高效的排序算法，但有一定的局限性：
    1、关键字可分解。
    2、记录的关键字位数较少，如果密集更好
    3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
  4. 当文件的初态已经基本有序，可以用优化后的冒泡排序。

http://www.ppmy.cn/news/263542.html

相关文章

【手撕Spring源码】深度理解SpringBoot

【手撕Spring源码】深度理解SpringBoot

文章目录 Tomcat内嵌容器Tomcat 基本结构创建Tomcat内嵌容器内嵌Tomcat集成Spring 容器 Boot 自动配置什么是自动配置类自动配置类原理Aop自动配置DataSource自动配置MyBatis自动配置事务自动配置MVC自动配置条件装配 附&#xff1a;注解小总EnableConfigurationPropertiesCond…
阅读更多...
自编码器（Autoencoder）应用场景

自编码器（Autoencoder）应用场景

自编码器&#xff08;Autoencoder&#xff09;是一种无监督学习模型&#xff0c;通常用于特征学习、降维和生成任务。自编码器由编码器&#xff08;Encoder&#xff09;和解码器&#xff08;Decoder&#xff09;两部分组成。编码器将输入数据压缩成较低维度的隐向量&#xff0c…
阅读更多...
神经网络单元测试 1 ~14单元

神经网络单元测试 1 ~14单元

第1讲 单元测试 ‌1. 被誉为“人工智能之父”的科学家是__图灵_。 ‎ 2 ‌下面说法中&#xff0c;正确的是___我们现在实现的几乎都是弱人工智能_____。 ‏ 3 ‎AI的英文缩写是___ Artificial Intelligence_____。 ‎ 4 ‍研究人工智能的目的是让机器___模拟、延伸和扩展人的智…
阅读更多...
【MySQL数据库 | 第五篇】DDl操作数据库

【MySQL数据库 | 第五篇】DDl操作数据库

目录 &#x1f914;DDL介绍&#xff1a; &#x1f914;语法详解&#xff1a; 1.查询&#xff1a; 1.查询所有数据库&#xff1a; 示例&#xff1a;查询自带数据库 2.查询当前数据库&#xff1a; 2.创建&#xff1a; 示例&#xff1a;创建一个名字叫做itcast的数据库&…
阅读更多...
28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

2023.6.7 KMP给我人脑cpu干烧了┭┮﹏┭┮ 第一阶段&#xff1a;最长相等前后缀的引入给暴力解法带来的改善 暴力解法&#xff1a; needle每次向前推进一位&#xff0c;然后判断是否与haystack中的相应字串对应&#xff0c;如图所示 当已知needle中不配对位 前面字串 的 最长相…
阅读更多...
电脑如何共享代理到wifi

电脑如何共享代理到wifi

最简单的方法&#xff1a; 电脑代理后&#xff0c;下载猎豹wifi&#xff0c;开启wifi&#xff0c;就可以共享啦。&#xff08;但记得下载的时候开任意一个安全软件&#xff0c;不然猎豹wifi会安装金山毒霸捆绑&#xff09;&#xff08;火绒拦截了无数次的人如是说&#xff09;…
阅读更多...
WIFI共享精灵

WIFI共享精灵

公司很坑爹&#xff0c;没有WIFI&#xff0c;想忙里偷闲用手机看个新闻都不行&#xff0c;经过网上一番搜索&#xff0c;发现了一个好东西&#xff1a;WIFI共享精灵 只要电脑有无线功能就可以用此软件&#xff0c;现在的笔记本电脑都带无线功能吧 下载地址&#xff1a;http://…
阅读更多...
笔记本电脑如何开启wifi热点共享

笔记本电脑如何开启wifi热点共享

在Win10操作系统&#xff0c;自带了一个功能就是把有线连接的网络以wifi热点共享出去&#xff0c;给使用无线网络连接的设备上网。以前是要安装一个wifi共享软件来实现这一功能&#xff0c;现在完全不需要了。这需要你的笔记本能使用有线上网&#xff0c;即带有RJ45接口&#x…
阅读更多...
最新文章

Copyright @ 2022~2023