首页 > 编程语言 >Java 排序算法详解

Java 排序算法详解

时间:2024-09-11 12:52:56浏览次数:10  
标签:arr Java int 元素 算法 详解 排序 public

排序是计算机科学中的基本操作,Java 提供了多种排序算法来满足不同的需求。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。本文将逐一介绍这些排序算法及其 Java 实现。

1. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法,其基本思想是通过重复遍历待排序的元素,比较相邻元素并交换位置,直到所有元素有序。时间复杂度为 O(n^2),适合小规模数据的排序。

1.1 算法步骤

  1. 从头到尾遍历数组。
  2. 比较相邻的元素,如果前一个元素大于后一个元素,则交换它们。
  3. 重复步骤 1 和 2,直到没有元素需要交换为止。

1.2 Java 实现


java

复制代码

public class BubbleSort { public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } }

2. 选择排序 (Selection Sort)

选择排序是一种简单的排序算法,其基本思想是每次从未排序的部分中选择最小(或最大)的元素,并将其放到已排序部分的末尾。时间复杂度为 O(n^2),适用于小规模数据。

2.1 算法步骤

  1. 从未排序的部分选择最小元素。
  2. 将选出的最小元素与未排序部分的第一个元素交换。
  3. 将已排序部分的范围扩展,重复步骤 1 和 2。

2.2 Java 实现


java

复制代码

public class SelectionSort { public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } }

3. 插入排序 (Insertion Sort)

插入排序是一种简单直观的排序算法,其基本思想是将待排序的数据分为已排序和未排序两部分,每次从未排序部分取出一个元素,将其插入到已排序部分的正确位置。时间复杂度为 O(n^2),适用于小规模数据或部分已排序的数据。

3.1 算法步骤

  1. 从第二个元素开始,向前与已排序部分比较。
  2. 如果当前元素小于已排序部分的元素,则将已排序部分的元素右移,直到找到合适的位置。
  3. 插入当前元素,扩展已排序部分的范围。

3.2 Java 实现


java

复制代码

public class InsertionSort { public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } }

4. 归并排序 (Merge Sort)

归并排序是一种有效的排序算法,基于分治法,其基本思想是将数组分成两个子数组,分别排序,然后将排序好的子数组合并。时间复杂度为 O(n log n),适用于大规模数据的排序。

4.1 算法步骤

  1. 将数组递归地分成两半,直到每个子数组只有一个元素。
  2. 合并已排序的子数组,形成排序好的更大子数组。
  3. 重复步骤 2,直到所有子数组合并成一个排序好的数组。

4.2 Java 实现


java

复制代码

public class MergeSort { public static void mergeSort(int[] arr) { if (arr.length < 2) return; int mid = arr.length / 2; int[] left = new int[mid]; int[] right = new int[arr.length - mid]; System.arraycopy(arr, 0, left, 0, mid); System.arraycopy(arr, mid, right, 0, arr.length - mid); mergeSort(left); mergeSort(right); merge(arr, left, right); } private static void merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { arr[k++] = left[i++]; } else { arr[k++] = right[j++]; } } while (i < left.length) arr[k++] = left[i++]; while (j < right.length) arr[k++] = right[j++]; } }

5. 快速排序 (Quick Sort)

快速排序是一种高效的排序算法,基于分治法,其基本思想是通过一个“基准”元素将数组分为两部分,一部分比基准小,另一部分比基准大,然后递归地排序这两部分。时间复杂度为 O(n log n),但在最坏情况下为 O(n^2),适用于大规模数据。

5.1 算法步骤

  1. 选择一个基准元素。
  2. 将数组分成两部分,一部分小于基准,一部分大于基准。
  3. 递归地对这两部分进行快速排序。

5.2 Java 实现


java

复制代码

public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } }

6. 堆排序 (Heap Sort)

堆排序是一种基于堆数据结构的排序算法,时间复杂度为 O(n log n)。它的基本思想是将数组视为一个堆,通过调整堆的结构,使得每次都可以将最大元素(或最小元素)取出,重复此操作直到排序完成。

6.1 算法步骤

  1. 建立一个最大堆(或最小堆)。
  2. 取出堆顶元素,将其与堆的最后一个元素交换,然后调整堆。
  3. 重复步骤 2,直到堆为空。

6.2 Java 实现


java

复制代码

public class HeapSort { public static void heapSort(int[] arr) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } private static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } }

总结

本文介绍了常见的 Java 排序算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。每种排序算法都有其特定的应用场景和优缺点,了解这些算法的基本原理和实现方法可以帮助你在实际编程中选择最合适的排序方法。希望本文的讲解能帮助你更好地掌握和应用这些排序算法。如果你有任何问题或需要进一步的详细说明,欢迎留言讨论!

标签:arr,Java,int,元素,算法,详解,排序,public
From: https://blog.csdn.net/m0_68570169/article/details/142071648

相关文章

  • 零基础国产GD32单片机编程入门(十六)DMA详解及ADC-DMA方式采集含源码
    文章目录一.概要二.GD32F103C8T6单片机DMA外设特点三.GD32单片机DMA内部结构图四.DMA各通道请求五.GD32F103C8T6单片机ADC-DMA采集例程六.工程源代码下载七.小结一.概要基本概念:DMA是DirectMemoryAccess的首字母缩写,是一种完全由硬件执行数据交换的工作方式。DM......
  • 【卷起来】VUE3.0教程-06-组件详解
    ============各位看官,点波关注和赞吧===========组件允许我们将UI划分为独立的、可重用的部分,并且可以对每个部分进行单独的思考。在实际应用中,组件常常被组织成层层嵌套的树状结构:这和我们嵌套HTML元素的方式类似,Vue实现了自己的组件模型,使我们可以在每个组件内封装......
  • 【高级编程】Java IO流(补)序列化 & 反序列化
    序列化(ObjectOutputStream)&反序列化(ObjectInputStream)Java的序列化和反序列化是用于将对象转换为字节流的过程,以便在网络上传输或保存到磁盘,然后将这些字节流再转换回对象。这个过程是Java中处理对象持久化和传输的常见方法。序列化是将对象的状态转换为字节流的过......
  • 基于JavaWeb开发的java eclipse+jsp+mysql+servlet+Spring的学生信息管理系统基础版
    基于JavaWeb开发的javaeclipse+jsp+mysql+servlet+Spring的学生信息管理系统基础版......
  • 【高级编程】Java IO流(下)字符流 Reader Writer 字节流读取二进制文件
    文章目录ReaderFileReaderBufferedReaderWriterFileWriterBufferedWriter读写二进制文件ReaderReader是一个抽象类,用于读取字符流。它是所有字符输入流的基类。Reader提供了一些基本的方法来读取字符数据intread()//读取单个字符,并返回一个整数。如果到达流......
  • 【高级编程】认识Java多线程 代码举例三种创建线程的方式
    文章目录主线程创建线程方式1:Thread方式2:Runnable方式3:Callable进程:应用程序的执行实例,有独立的内存空间和系统资源线程:CPU调度和分派的基本单位,进程中执行运算的最小单位,可完成一个独立的顺序控制流程多线程:如果在一个进程中同时运行了多个线程,用来完成不同的工......
  • java常规web面试题考点
    在java的理论知识中,有一个模块作为最基础的组成,但在学习的难度上较大所以往这方面发展的人不多。其实这就是web模块,开发一些软件都离不开web方面的理论支撑。web面试题主要考察一些基础开发的工具的用法和实际代码运用的试题,下面我们来就具体的题目进行作答。1.网络编程首先要......
  • 全网最火的AI技术:GraphRag概念详解
    GraphRAG是一种结合了知识图谱(KnowledgeGraph)和大语言模型(LLM)的检索增强生成(Retrieval-AugmentedGeneration,RAG)技术,旨在通过将结构化和非结构化数据相结合来增强生成式AI的表现。它的出现代表了人工智能生成技术与知识表示领域的一次重要融合,为许多需要复杂信息检索和生成的应......
  • 【JAVA】第五天
    【JAVA】第五天一、Math类二、System类三、Runtime类四、BigDecimal类五、JDK8之前传统的日期、时间(不推荐)1.Date类2.SimpleDateFormat类3.Calendar类六、JDK8之后新增的日期、时间1.LocalDateTime类2.ZoneId类3.ZonedDateTime类4.Instant类5.DateTimeFormatter类6.Peri......
  • (转)万字长文——Go 语言现代命令行框架 Cobra 详解
    原文:https://juejin.cn/post/7231197051203256379Cobra是一个Go语言开发的命令行(CLI)框架,它提供了简洁、灵活且强大的方式来创建命令行程序。它包含一个用于创建命令行程序的库(Cobra库),以及一个用于快速生成基于Cobra库的命令行程序工具(Cobra命令)。Cobra是由Go团队成员......