Java中的六种经典比较排序算法:代码实现全解析(上)

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: Java中的六种经典比较排序算法:代码实现全解析

一、 前言

1.1 引入

排序算法是程序开发和计算机科学中常见的算法之一。排序算法可以对一个未排序的数据集合进行排序,使得数据集合中的元素按照一定的顺序排列。排序算法是算法分析的重要内容之一,因为排序算法的效率影响着程序的性能和稳定性。

1.2 目的

本文的目的是介绍常见的排序算法,并且通过代码示例演示它们的实现过程。本文会逐一介绍冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序等六种排序算法,并对它们的原理、思路、代码实现及时间复杂度进行详细分析。最后通过性能比较实验,比较这些算法在不同数据规模下的耗时情况,从而得出各种算法的优劣。

二、 排序算法概述

2.1 什么是排序算法

排序算法是一种对数据集合进行排序的算法,按照某种顺序重新排列数据集合中的元素。排序算法可以应用于各种领域,例如程序开发、数据库查询优化等。

2.2 排序算法分类

常见的排序算法可分为以下几类:

(1)比较排序:通过比较数据集合中元素的大小关系来进行排序。比较排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序等。

(2)非比较排序:不需要比较数据集合中元素的大小关系来进行排序,而是通过类似于哈希表的方式将数据集合中的元素进行分配。非比较排序算法包括计数排序、桶排序、基数排序等。

2.3 排序算法比较

不同的排序算法有不同的时间复杂度和空间复杂度,不同的应用场景需要选择不同的排序算法。下表列出了常见的排序算法,以及它们的时间复杂度和空间复杂度。

排序算法 平均时间复杂度 最优时间复杂度 最坏时间复杂度 空间复杂度 排序稳定性
冒泡排序(Bubble Sort) O(n^2) O(n) O(n^2) O(1) 稳定
选择排序(Selection Sort) O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序(Insertion Sort) O(n^2) O(n) O(n^2) O(1) 稳定
快速排序(Quick Sort) O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定
归并排序(Merge Sort) O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
堆排序(Heap Sort) O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
计数排序(Counting Sort) O(n+k) O(n+k) O(n+k) O(k) 稳定
基数排序(Radix Sort) O(kn) O(kn) O(kn) O(n+k) 稳定

这些是时间复杂度的表示法,常常用来衡量算法的效率和实用性:

时间复杂度 含义
O(1) 常数时间复杂度
O(logn) 对数时间复杂度
O(n) 线性时间复杂度
O(nlogn) 线性对数时间复杂度
O(n^2) 平方时间复杂度
O(kn) 线性乘以常数时间复杂度
O(n+k) 线性加常数时间复杂度

根据表格中的数据,我们可以得出一些结论:

(1)冒泡排序、选择排序和插入排序虽然实现简单,但其时间复杂度都比较高,不适合处理大规模的数据集合。

(2)希尔排序的时间复杂度比较稳定,是一种比较实用的排序算法。

(3)归并排序和快速排序都是基于分治思想的排序算法,它们的时间复杂度比较低,是处理大规模数据集合的不二选择。

三、 冒泡排序

3.1 原理与思想

冒泡排序是一种比较简单的排序算法,它重复地遍历要进行排序的数组,比较相邻两个元素的大小,如果前一个元素大于后一个元素,则交换它们的位置。这样一遍遍历下来,每次都将数组中最大的元素“冒泡”到最后面。如此操作,直到所有元素都排列好位置。

3.2 代码实现

下面是冒泡排序的代码实现:

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

3.3 时间复杂度分析

时间复杂度的表示法的含义可以在2.3查看 冒泡排序的时间复杂度为 O(n^2),因此在处理大规模数据时,效率较低。具体来说,最坏情况下需要执行 n*(n-1)/2 次比较和交换,而最优情况下则只需要执行 n-1 次比较和 0 次交换。在平均情况下,冒泡排序需要执行 n*(n-1)/4 次比较和交换。由于时间复杂度为 O(n^2),因此冒泡排序不适合处理大规模数据的排序问题,但由于其思想简单,实现容易,并且常常被用作教学用例,以帮助学生理解排序算法的基本原理。

四、 选择排序

4.1 原理与思想

选择排序是一种简单直观的排序算法,它的基本思想是:每次在待排序的数组中选取最小的元素,然后把它和数组的第一个元素交换位置,接着在剩下的元素中再选取最小的元素,放在已排好序的数组的最后面。如此操作,直到所有元素都排列好位置。

4.2 代码实现

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

4.3 时间复杂度分析

时间复杂度的表示法的含义可以在2.3查看

选择排序的时间复杂度为 O(n^2),因此与冒泡排序一样,不适合处理大规模数据的排序问题。具体来说,在平均情况下需要执行 n*(n-1)/2 次比较和 n-1 次交换。在最坏情况下,需要执行 n*(n-1)/2 次比较和 n-1 次交换。在最优情况下,也需要执行 n*(n-1)/2 次比较和 0 次交换。虽然时间复杂度比较高,但实现简单,不占用额外的内存空间。

五、 插入排序

5.1 原理与思想

插入排序是一种简单直观的排序算法,它的基本思想是:将待排序的数组分为已排好序的部分和未排序的部分,从未排序的部分中取出一个元素插入到已排好序的部分中,使得插入后仍然有序。如此操作,直到所有元素都排列好位置。

5.2 代码实现

public class InsertionSort {
public static void main(String[] args) {
int[] arr = {5, 2, 4, 6, 1, 3};
    insertionSort(arr);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
}
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
}

5.3 时间复杂度分析

时间复杂度的表示法的含义可以在2.3查看

对于插入排序,时间复杂度取决于需要进行排序的数据的数量以及数据的状态。最好情况下,当数据已经按照从小到大的顺序排序时,插入排序的时间复杂度为O(n)。最坏情况下,当数据以从大到小的顺序排序时,插入排序的时间复杂度为O(n^2)。由于插入排序在大多数情况下执行效率很高,因为它仅仅需要比较少量的元素。

目录
相关文章
|
7天前
|
负载均衡 算法 Java
Spring Cloud全解析:负载均衡算法
本文介绍了负载均衡的两种方式:集中式负载均衡和进程内负载均衡,以及常见的负载均衡算法,包括轮询、随机、源地址哈希、加权轮询、加权随机和最小连接数等方法,帮助读者更好地理解和应用负载均衡技术。
|
2天前
|
设计模式 Java 关系型数据库
【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码解析
本文是“Java学习路线”专栏的导航文章,目标是为Java初学者和初中高级工程师提供一套完整的Java学习路线。
|
3天前
|
SQL JavaScript 前端开发
基于Java访问Hive的JUnit5测试代码实现
根据《用Java、Python来开发Hive应用》一文,建立了使用Java、来开发Hive应用的方法,产生的代码如下
17 6
|
2天前
|
存储 监控 算法
Java中的内存管理与垃圾回收机制解析
本文深入探讨了Java编程语言中的内存管理策略和垃圾回收机制。首先介绍了Java内存模型的基本概念,包括堆、栈以及方法区的划分和各自的功能。进一步详细阐述了垃圾回收的基本原理、常见算法(如标记-清除、复制、标记-整理等),以及如何通过JVM参数调优垃圾回收器的性能。此外,还讨论了Java 9引入的接口变化对垃圾回收的影响,以及如何通过Shenandoah等现代垃圾回收器提升应用性能。最后,提供了一些编写高效Java代码的实践建议,帮助开发者更好地理解和管理Java应用的内存使用。
|
1天前
|
Java 开发者
探索Java中的Lambda表达式:简化代码,提升效率
【9月更文挑战第14天】本文旨在揭示Java 8中引入的Lambda表达式如何革新了我们编写和管理代码的方式。通过简洁明了的语言和直观的代码示例,我们将一起走进Lambda表达式的世界,了解其基本概念、语法结构以及在实际编程中的应用。文章不仅会展示Lambda表达式的魅力所在,还会指导读者如何在日常工作中有效利用这一特性,以提高编码效率和程序可读性。
|
2天前
|
Java 开发者
深入解析Java中的异常处理机制
本文将深入探讨Java中异常处理的核心概念和实际应用,包括异常的分类、捕获、处理以及最佳实践。我们将通过具体示例展示如何有效使用try-catch块、throws关键字和自定义异常类,以帮助读者更好地理解和应用Java异常处理机制。
9 1
|
3天前
|
Java 程序员 开发者
Java中的异常处理机制深度解析
本文旨在深入探讨Java中异常处理的机制,包括异常的分类、如何捕获和处理异常,以及自定义异常的最佳实践。通过实例讲解,帮助读者更好地理解如何在Java编程中有效管理和利用异常处理来提高代码的健壮性和可维护性。
|
4天前
|
存储 负载均衡 Java
Jetty技术深度解析及其在Java中的实战应用
【9月更文挑战第3天】Jetty,作为一款开源的、轻量级、高性能的Java Web服务器和Servlet容器,自1995年问世以来,凭借其卓越的性能、灵活的配置和丰富的扩展功能,在Java Web应用开发中占据了举足轻重的地位。本文将详细介绍Jetty的背景、核心功能点以及在Java中的实战应用,帮助开发者更好地理解和利用Jetty构建高效、可靠的Web服务。
16 2
|
7天前
|
并行计算 Java 开发者
探索Java中的Lambda表达式:简化代码,提升效率
Lambda表达式在Java 8中引入,旨在简化集合操作和并行计算。本文将通过浅显易懂的语言,带你了解Lambda表达式的基本概念、语法结构,并通过实例展示如何在Java项目中应用Lambda表达式来优化代码,提高开发效率。我们将一起探讨这一现代编程工具如何改变我们的Java编码方式,并思考它对程序设计哲学的影响。
|
2天前
|
存储 缓存 安全
【Java面试题汇总】多线程、JUC、锁篇(2023版)
线程和进程的区别、CAS的ABA问题、AQS、哪些地方使用了CAS、怎么保证线程安全、线程同步方式、synchronized的用法及原理、Lock、volatile、线程的六个状态、ThreadLocal、线程通信方式、创建方式、两种创建线程池的方法、线程池设置合适的线程数、线程安全的集合?ConcurrentHashMap、JUC
【Java面试题汇总】多线程、JUC、锁篇(2023版)

热门文章

最新文章

推荐镜像

更多