当前位置: 首页 > news >正文

常见算法题目5 -常见的排序算法

常见算法题目5 -常见的排序算法

本文介绍常见的排序算法的思路及代码实现(都是按照从小到大排列),包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

1.冒泡排序

  • 思路:重复遍历数组,依次比较相邻元素,若顺序错误则交换,直至没有交换发生。每次外层循环后,最大的都会移动到数组末尾,就像冒水泡一样(水泡由水底往上升起的过程中原来越大),故称为冒泡排序。
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定
  • 实现代码:
    /*** 常见的排序算法(从小到大排列) 之 冒泡排序* @param arr*/public static void bubbleSort1(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {// 比较相邻元素 前>后 则交换位置if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}// 为了直观的显现冒泡的过程,可以在这里打下输出System.out.println("冒泡排序,第" + (i + 1) + "轮排序后,:" + Arrays.toString(arr));}}
  • 测试:
public class SortTest {public static void main(String[] args) {int[] arr1 = {7, 6, 5, 4, 3, 2, 1};System.out.println("原数组:" + Arrays.toString(arr1));bubbleSort1(arr1);System.out.println("冒泡排序后:" + Arrays.toString(arr1));}

在这里插入图片描述

2. 选择排序

  • 思路:每次从未排序部分选择最小元素,与未排序部分的第一个元素交换。每次外层循环结束后,最小的元素都会一步步移动到数据的前面。
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:不稳定。与冒泡排序相比都涉及数据位置交换,但涉及相同数值数据的交换,会改变相同数值的相对位置,因此不稳定。但冒泡排序在进行等值判断后不会进行位置交换,故稳定。
  • 实现代码:
    /*** 常见的排序算法(从小到大排列) 之 选择排序* @param arr*/public static void testSelectionSort2(int[] arr) {// 遍历比较for (int i = 0; i < arr.length - 1; i++) {// 存储最小值下标索引int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换位置if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}// 为了直观的显现选择排序的过程,可以在这里打下输出System.out.println("选择排序,第" + (i + 1) + "轮排序后,:" + Arrays.toString(arr));}}
  • 测试:
public class SortTest {public static void main(String[] args) {int[] arr2 = {7, 6, 5, 4, 3, 2, 1};System.out.println("原数组:" + Arrays.toString(arr2));testSelectionSort2(arr2);System.out.println("选择排序后:" + Arrays.toString(arr2));}

在这里插入图片描述

3. 插入排序

  • 思路:将数组分为已排序部分和未排序部分,已排序部分为已排序的元素,未排序部分为未排序的元素。将未排序部分中的每一个元素逐个插入到已排序部分的正确位置。
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定
  • 实现代码:
    /*** 常见的排序算法(从小到大排列) 之 插入排序* @param arr*/public static void insertSort3(int[] arr) {// 循环判断for (int i = 1; i < arr.length; i++) {// 存储当前元素int temp = arr[i];// 循环判断,找到插入的位置int j = i - 1;// 已排序部分的元素,找到插入的位置while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}// 当前循环下标位置数据赋值arr[j + 1] = temp;// 为了直观的显现插入排序的过程,可以在这里打下输出System.out.println("插入排序,第" + i + "轮排序后,:" + Arrays.toString(arr));}}
  • 测试:
public class SortTest {public static void main(String[] args) {int[] arr3 = {7, 6, 5, 4, 3, 2, 1};System.out.println("原数组:" + Arrays.toString(arr3));insertSort3(arr3);System.out.println("插入排序后:" + Arrays.toString(arr3));}

在这里插入图片描述

4. 快速排序

  • 思路:将数组分为已排序部分和未排序部分,已排序部分为已排序的元素,未排序部分为未排序的元素。将未排序部分中的每一个元素逐个插入到已排序部分的正确位置。
    ①选择基准元素:一般选择第一个或最后一个元素作为基准元素。
    ②数组分区:比基准元素小的在基准元素的左边,比基准元素大的在基准元素的右边
    ③递归:递归对基准元素左边和右边的部分进行快速排序
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(logn)
  • 稳定性:不稳定
  • 实现代码:
    /*** 常见的排序算法 之 快速排序(从小到大排列) * @param arr*/public static void quickSort4(int[] arr, int left, int right) {if (left < right) {int baseIndex = partition(arr, left, right);// 递归对基准元素左边和右边的进行快速排序quickSort4(arr, left, baseIndex - 1);quickSort4(arr, baseIndex + 1, right);}}/*** 获取基准原始位置* @param arr* @param left* @param right* @return*/private static int partition(int[] arr, int left, int right) {// 选择最后一个元素为基准元素int baseValue = arr[right];int i = left - 1;for (int j = left; j < right; j++) {// 当前元素小于基准元素if (arr[j] < baseValue) {// 交换位置i++;// 交换当前元素与较小元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}System.out.println("快速排序,排序中间过程结果:" + Arrays.toString(arr));}// 交换基准元素与较小元素索引下一个元素int temp = arr[i + 1];arr[i + 1] = arr[right];arr[right] = temp;System.out.println("快速排序,基准元素交换位置后结果:" + Arrays.toString(arr));// 返回基准元素索引return i + 1;}
  • 测试:
public class SortTest {public static void main(String[] args) {int[] arr4 = {5, 6, 2, 3, 1, 7, 4};System.out.println("原数组:" + Arrays.toString(arr4));quickSort4(arr4, 0, arr4.length - 1);System.out.println("快速排序后:" + Arrays.toString(arr4));}

在这里插入图片描述

5.归并排序

  • 思路:归并排序是一种典型的分治算法。
    ①分:将数组分成两半;
    ②治:递归对左右两部分进行排序;
    ③合:将左右两部分有序数组合并为有序数组。
  • 时间复杂度:O(nlog n)
  • 空间复杂度:O(n)
  • 稳定性:稳定
  • 实现代码:
    /*** 常见的排序算法 之 归并排序(从小到大排列) * @param arr*/public static void mergeSort5(int[] arr, int left, int right, int[] temp) {if (arr == null || arr.length < 1) {return;}if (left < right) {// 取中间索引int mid = (right + left) / 2;// 递归排序左半边mergeSort5(arr, left, mid, temp);// 递归排序右半边mergeSort5(arr, mid + 1, right, temp);// 合并左右两个有序数组merge(arr, left, mid, right, temp);}}/*** 合并两个有序数组** @param arr   原数组* @param left  左指针* @param mid   中间索引* @param right 右指针* @param temp  临时数组*/private static void merge(int[] arr, int left, int mid, int right, int[] temp) {// 左子数组起始索引int leftIndex = left;// 右子数组起始索引int rightIndex = mid + 1;//  临时数组索引int tempIndex = 0;// 比较左右两部分的元素,将较小的放入tempwhile (leftIndex <= mid && rightIndex <= right) {if (arr[leftIndex] <= arr[rightIndex]) {temp[tempIndex++] = arr[leftIndex++];} else {temp[tempIndex++] = arr[rightIndex++];}}// 将左边剩余元素填充进temp中while (leftIndex <= mid) {temp[tempIndex++] = arr[leftIndex++];}//  将右边剩余元素填充进temp中while (rightIndex <= right) {temp[tempIndex++] = arr[rightIndex++];}// 将temp中的元素拷贝到arr中tempIndex = 0;while (left <= right) {arr[left++] = temp[tempIndex++];}}
  • 测试:
public class SortTest {public static void main(String[] args) {int[] arr5 = {5, 6, 2, 3, 1, 7, 4};System.out.println("原数组:" + Arrays.toString(arr5));int[] tempArr = new int[arr5.length];mergeSort5(arr5, 0, arr5.length - 1, tempArr);System.out.println("归并排序后:" + Arrays.toString(arr5));}

在这里插入图片描述

6. 堆排序

  • 思路:堆排序(Heap Sort)是一种基于二叉堆数据结构的比较排序算法,排序思路:
    ①构建堆,将无序数组构建成一个最大堆(或者最小堆)
    ②排序,每次取出堆顶元素,并调整堆,将堆顶元素放到已排序的末尾,重复n-1次,即可得到一个有序数组。
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)
  • 稳定性:不稳定
  • 实现代码:
    /*** 常见的排序算法 之 堆排序(从小到大排列) * @param arr*/public static void heapSort6(int[] arr) {if (arr == null || arr.length < 1) {return;}// 构建最大堆buildMaxHeap(arr);// 逐一交换堆顶元素(最大值)到数组末尾,并调整堆for (int i = arr.length - 1; i > 0; i--) {// 将堆顶元素与末尾元素交换int temp = arr[i];arr[i] = arr[0];arr[0] = temp;// 调整堆,使其重新成为最大堆(堆大小减1)heapAdjust(arr, 0, i);System.out.println("堆排序中间过程:" + Arrays.toString(arr));}}/*** heapAdjust* @param arr*/public static void buildMaxHeap(int[] arr) {// 从最后一个非叶子节点开始,从下至上,从右至左进行堆化for (int i = arr.length / 2 - 1; i >= 0; i--) {// 堆化heapAdjust(arr, i, arr.length);}}/*** 调整堆* @param arr* @param i* @param heapSize*/public static void heapAdjust(int[] arr, int i, int heapSize) {// 初始化最大值为当前节点int largest = i;// 左子节点int left = 2 * i + 1;// 右子节点int right = 2 * i + 2;// 如果左子节点大于当前最大节点if (left < heapSize && arr[left] > arr[largest]) {largest = left;}// 如果右子节点大于当前最大节点if (right < heapSize && arr[right] > arr[largest]) {largest = right;}// 如果最大节点不是当前节点,交换并继续调整if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapAdjust(arr, largest, heapSize);}}
  • 测试:
public class SortTest {public static void main(String[] args) {int[] arr6 = {5, 6, 2, 3, 1, 7, 4};System.out.println("原数组:" + Arrays.toString(arr6));heapSort6(arr6);System.out.println("堆排序后:" + Arrays.toString(arr6));}

在这里插入图片描述

7. 总结

算法平均时间复杂度空间复杂度稳定性适用场景
冒泡排序O(n²)O(1)稳定教学、小数据集
选择排序O(n²)O(1)不稳定简单实现但效率低
插入排序O(n²)O(1)稳定部分有序数组
快速排序O(n log n)O(log n)不稳定通用排序,性能优秀
归并排序O(nlog n)O(n)稳定大数据、需要稳定性
堆排序O(nlog n)O(1)稳定原地排序,无需额外空间
http://www.lqws.cn/news/68005.html

相关文章:

  • LabVIEW准分子激光器智能控制系统
  • 【Pytorch学习笔记】模型模块07——hook实现Grad-CAM
  • 数据库系统概论(十四)详细讲解SQL中空值的处理
  • Spring框架学习day6--事务管理
  • 《人性的弱点》能带给我们什么?
  • IoTGateway项目生成Api并通过swagger和Postman调用
  • [免费]微信小程序网上花店系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
  • 提升嵌入式软件调试效率的核心方
  • 内存管理--《Hello C++ Wrold!》(8)--(C/C++)--深入剖析new和delete的使用和底层实现
  • 【Linux】网络--网络层--IP协议
  • PyTorch——卷积层(3)
  • CppCon 2014 学习:0xBADC0DE
  • CSS之动画(奔跑的熊、两面反转盒子、3D导航栏、旋转木马)
  • 小目标检测:YOLOV7改进之双坐标注意力(DCA)
  • TDengine 高级功能——读缓存
  • 汽车安全体系:FuSa、SOTIF、Cybersecurity 从理论到实战
  • 机器人自动火焰切割H型钢的系统设计与应用
  • 机器人夹爪的选型与ROS通讯——机器人抓取系统基础系列(六)
  • 【Redis】Set 集合
  • 【基于阿里云搭建数据仓库(离线)】IDEA导出Jar包(包括第三方依赖)
  • 微型导轨在手术机器人领域中有哪些关键操作?
  • 【Linux】线程控制
  • java 多线程
  • dvwa4——File Inclusion
  • Spring Boot 3.X 下Redis缓存的尝试(二):自动注解实现自动化缓存操作
  • [特殊字符] Python开发革命!uv工具:让环境管理像点外卖一样简单
  • 振动分析师(ISO18436-2)四级能力矩阵 - 简介
  • Arbitrum Stylus 合约实战 :Rust 实现 ERC721
  • 01 Ubuntu20.04下编译QEMU8.2.4,交叉编译32位ARM程序,运行ARM程序的方法
  • JavaWeb预习(jsp)