首页 > 编程语言 >数组的算法

数组的算法

时间:2024-07-30 19:07:19浏览次数:15  
标签:sort arr int 元素 算法 数组 排序

冒泡法


冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤:

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码示例(Java):

javapublic class BubbleSort {
    public static void bubbleSort(int[] arr) {
        //冒泡排序
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j + 1]
                    int temp = arr[j];//临时变量
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

算法特性:

  • 时间复杂度:平均和最坏情况时间复杂度为�(�2)O(n2),其中�n是数组的长度。最好情况时间复杂度为�(�)O(n)(当数组已经是排序好的)。
  • 空间复杂度:�(1)O(1),因为它只需要一个额外的空间来交换元素。
  • 稳定性:冒泡排序是稳定的排序算法,因为它不会改变相同元素的顺序。
  • 适用场景:由于其简单性,冒泡排序适合于小数据集或基本教学目的。对于较大的数据集,更高效的算法(如快速排序、归并排序等)更合适。

image-20240729143943399

选择排序


选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是每次从待排序的数据中选出最小(或最大)的元素,将其放在数列的起始位置,然后剩余的元素中再找最小(或最大)的元素,将其放在第二个位置,以此类推,直到排序完成。

算法步骤:

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。

代码示例(Java):

javapublic class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        int temp = 0;
        //选择排序
        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;
                }
            }
            // 将找到的最小值与第i位的元素交换
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

算法特性:

  • 时间复杂度:无论最好、最差或平均情形,时间复杂度都是�(�2)O(n2),其中�n是数组的长度。
  • 空间复杂度:�(1)O(1),选择排序是原地排序,不需要额外存储空间。
  • 稳定性:选择排序是不稳定的排序算法,因为相同元素的顺序可能会改变。
  • 适用场景:由于其实现简单,选择排序适用于初学者学习和小规模数据集。对于大规模数据集,更高效的算法(如快速排序、归并排序等)更为合适。

选择排序的主要优点是它简单易实现,且对于小型数组或基本有序的数组效率相对较高。然而,由于其时间复杂度较高,它通常不适用于大型数据集。

排序算法库:sort


在Java中,sort 方法是集合框架中 java.util.Collections 类和 java.util.Arrays 类提供的一个非常强大且常用的排序方法。这两个类提供了对数组和集合进行排序的方法。

1. java.util.Arrays.sort

Arrays.sort 方法用于对数组进行排序。这个方法可以对原始数据类型的数组(如 int[]double[] 等)和对象数组进行排序。对于对象数组,需要实现 Comparable 接口或提供 Comparator 实例来定义排序的顺序。

原始数据类型数组示例

javaimport java.util.Arrays;

public class SortExample {
    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 3, 1};
        Arrays.sort(numbers);
        System.out.println(Arrays.toString(numbers)); // 输出排序后的数组
    }
}

对象数组示例

javaimport java.util.Arrays;
import java.util.Comparator;

class Person {
    String name;
    int age;

    // Constructor, getters and setters
}

public class SortExample {
    public static void main(String[] args) {
        Person[] people = new Person[] {
            new Person("Alice", 22),
            new Person("Bob", 30),
            new Person("Charlie", 25)
        };

        // 按照年龄排序
        Arrays.sort(people, Comparator.comparingInt(Person::age));

        for (Person person : people) {
            System.out.println(person.name + " - " + person.age);
        }
    }
}

2. java.util.Collections.sort

Collections.sort 方法用于对 List 集合进行排序。它需要一个 List 接口的实现和 Comparator 来定义排序的顺序。

集合排序示例

javaimport java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Product {
    String name;
    double price;

    // Constructor, getters and setters
}

public class SortExample {
    public static void main(String[] args) {
        List<Product> products = new ArrayList<>();
        products.add(new Product("Apple", 0.75));
        products.add(new Product("Orange", 1.00));
        products.add(new Product("Banana", 0.50));

        // 按照价格排序
        Collections.sort(products, Comparator.comparingDouble(Product::getPrice));

        for (Product product : products) {
            System.out.println(product.name + " - " + product.price);
        }
    }
}

排序算法库的特性:

  • 通用性sort 方法是泛型的,可以用于多种数据类型的排序。
  • 灵活性:通过 Comparator,可以灵活地定义任何对象的排序规则。
  • 效率:底层实现通常是基于快速排序、归并排序或其他高效的排序算法,具有很好的性能。
  • 稳定性:Java中的 sort 方法是稳定的,即相等的元素在排序后保持原有的顺序。

标签:sort,arr,int,元素,算法,数组,排序
From: https://www.cnblogs.com/czj03/p/18333182

相关文章

  • 多维度数组
    多维度数组多维度数组(MultidimensionalArrays)在Java中可以视为数组的数组,最常见的是二维数组,但Java也支持更多维度的数组。多维度数组在内存中并不是连续存储的,它们是按行或按列连续的,这取决于数组的布局方式。声明多维度数组:javaint[][]twoDimArray;//声明一个二维数组i......
  • 【智能算法应用】基于球形矢量的灰狼算法求解UAV路径规划问题
    目录1.算法原理2.数学模型3.结果展示4.参考文献5.代码获取1.算法原理【智能算法】灰狼算法(GWO)原理及实现2.数学模型路径最优性为了实现UAV的高效运行,计划的路径需要在某一特定标准上达到最优。UAV飞行路径Xi表示为UAV需要飞过的一系列n个航路点,每个航路点对应搜......
  • 【智能算法应用】A*和改进A*求解大规模栅格地图路径规划问题
    目录1.算法原理2.二值图像构建大规模栅格地图3.结果展示4.代码获取1.算法原理精准导航:用A*算法优化栅格地图的路径规划【附Matlab代码】改进A*算法通过删除必要的拐点或简化路径来减少路径长度,使得路径更为直观和高效。2.二值图像构建大规模栅格地图给定一幅二......
  • 算法:请找出数组a所有重复元素和比较数组a和数组b得到不重复的新数组和比较数组a和数组
    /***1.给定数组int[]a,int[]b*(1)请找出数组a所有重复元素,例:int[]a={1,2,3,4,8,9,3,5,1,3},结果int[]a1={1,1,3,3,3}*(2)比较数组a和数组b得到不重复的新数组,例:int[]a={1,2,3,4,8,9,3,5,1,3},int[]b={2,7,6,0,5},结果int[]c={1,2,3,4,5,6,......
  • JavaScript 数据结构与基础算法
    数据结构全解参考:数据结构|博客园-SRIGT相关代码仓库查看:data-struct-js|Github-SR1GT0x00前置知识(1)类使用关键字class声明一个类classPerson{}JavaScript的类中通过constructor使用构建函数classPerson{constructor(name){this.name......
  • Android开发 - ArrayList类动态数组与ArrayList<Fragment>解析
    什么是ArrayListArrayList是Java编程语言中的一个类,它实现了动态数组的数据结构。简单来说,ArrayList允许我们创建一个可以动态增长或缩减的数组,这在处理需要频繁添加或删除元素的情况下非常有用主要特点和用途动态大小:ArrayList的大小可以根据需要动态增长或缩减,与普通的数......
  • 强化学习Reinforcement Learning算法的样本效率提升策略
    强化学习ReinforcementLearning算法的样本效率提升策略1.背景介绍1.1问题的由来在强化学习领域,提升算法的样本效率是关键挑战之一。在许多现实世界的应用场景中,比如机器人自主导航、智能游戏、自动驾驶、医疗健康决策以及大规模服务系统优化,获取高价值的环境反馈往往......
  • 强化学习算法:策略梯度 (Policy Gradient) 原理与代码实例讲解
    强化学习算法:策略梯度(PolicyGradient)原理与代码实例讲解关键词:强化学习策略梯度深度学习神经网络案例分析1.背景介绍1.1问题的由来强化学习(ReinforcementLearning,RL)是一种学习方式,通过与环境的交互来学习如何作出最佳决策。在许多现实世界的问题中,比如......
  • 循环赛算法:每队比赛总数
    循环赛安排要求:每支球队的比赛总数我是循环赛安排的新手,并且坚持这个要求,我们在团队数组中传递以及球队应该参加的最小比赛数。我已经实现了单循环算法和双循环算法,例如:teams=['T1','T2','T3','T4'];单循环生成此:T3vsT2T4vsT1T2vsT4T3vsT1T1vsT2......
  • 利用结构体数组 实现学生信息管理系统(模块化编程)
    核心功能(必须实现):                        新增信息查询信息修改信息删除信息 信息排序扩展功能:                        按字符串索引, 插入信息 提升功能:                        账号注......