查找与排序算法详解:冒泡、选择、插入和快速排序
需积分: 5 189 浏览量
更新于2024-08-04
收藏 4KB TXT 举报
"查找与排序算法今日干货"
查找与排序算法是计算机科学中最基本和最重要的概念之一。排序算法是指将一组数据按照一定的顺序排列的算法,查找算法是指在一个已排序的数据集合中找到特定元素的算法。今天,我们将讨论四种常见的排序算法:冒泡排序、选择排序、插入排序和快速排序。
1. 冒泡排序
冒泡排序是一种简单的排序算法,通过不断地比较和交换相邻元素来实现排序。其主要思想是:通过比较相邻元素,大的元素逐渐“浮”到数组的末尾,而小的元素逐渐“沉”到数组的前端。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1)。
在 Java 中,冒泡排序的实现代码如下所示:
```java
for (int i = 0; i < ints.length - 1; i++) {
for (int j = 0; j < ints.length - 1 - i; j++) {
if (ints[j] > ints[j + 1]) {
int temp = ints[j];
ints[j] = ints[j + 1];
ints[j + 1] = temp;
}
}
}
```
2. 选择排序
选择排序是另一种简单的排序算法,通过选择最小或最大的元素来实现排序。其主要思想是:首先,认为数组的第一个元素是最小的,然后,遍历数组,找到比当前最小元素小的元素,并将其作为新的最小元素。最后,将当前最小元素和数组的第一个元素进行交换。选择排序的时间复杂度为O(n^2),空间复杂度为O(1)。
在 Java 中,选择排序的实现代码如下所示:
```java
for (int i = 0; i < ints.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < ints.length; j++) {
if (ints[minIndex] > ints[j]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = ints[i];
ints[i] = ints[minIndex];
ints[minIndex] = temp;
}
}
```
3. 插入排序
插入排序是一种简单的排序算法,通过将未排序序列的每一个元素插入到已排序序列中的适当位置来实现排序。其主要思想是:首先,认为数组的第一个元素是已排序的,然后,将未排序序列的每一个元素插入到已排序序列中的适当位置。插入排序的时间复杂度为O(n^2),空间复杂度为O(1)。
在 Java 中,插入排序的实现代码如下所示:
```java
for (int i = 1; i < ints.length; i++) {
for (int j = i; j > 0; j--) {
if (ints[j - 1] > ints[j]) {
int temp = ints[j];
ints[j] = ints[j - 1];
ints[j - 1] = temp;
} else {
break;
}
}
}
```
4. 快速排序
快速排序是一种高效的排序算法,通过将数组分为两个部分,左侧部分的元素都小于基准元素,右侧部分的元素都大于基准元素来实现排序。其主要思想是:首先,选择一个基准元素,然后,将数组分为两个部分,左侧部分的元素都小于基准元素,右侧部分的元素都大于基准元素。最后,将左侧部分和右侧部分递归排序。快速排序的时间复杂度为O(n log n),空间复杂度为O(log n)。
在 Java 中,快速排序的实现代码如下所示:
```java
public static void quickSort(int[] ints) {
quickSort(ints, 0, ints.length - 1);
}
private static void quickSort(int[] ints, int low, int high) {
if (low >= high) {
return;
}
int pivot = partition(ints, low, high);
quickSort(ints, low, pivot - 1);
quickSort(ints, pivot + 1, high);
}
private static int partition(int[] ints, int low, int high) {
int pivot = ints[low];
int i = low + 1;
int j = high;
while (i <= j) {
while (i <= j && ints[i] <= pivot) {
i++;
}
while (i <= j && ints[j] > pivot) {
j--;
}
if (i <= j) {
int temp = ints[i];
ints[i] = ints[j];
ints[j] = temp;
}
}
ints[low] = ints[j];
ints[j] = pivot;
return j;
}
```
以上四种排序算法都是常见的排序算法,每种算法都有其优缺,选择合适的排序算法取决于实际情况。
2019-12-24 上传
2021-03-03 上传
2023-10-06 上传
2019-10-28 上传
2023-06-06 上传
2022-05-07 上传
点击了解资源详情
2024-10-26 上传
会点魔法o
- 粉丝: 1
- 资源: 1
最新资源
- ES管理利器:ES Head工具详解
- Layui前端UI框架压缩包:轻量级的Web界面构建利器
- WPF 字体布局问题解决方法与应用案例
- 响应式网页布局教程:CSS实现全平台适配
- Windows平台Elasticsearch 8.10.2版发布
- ICEY开源小程序:定时显示极限值提醒
- MATLAB条形图绘制指南:从入门到进阶技巧全解析
- WPF实现任务管理器进程分组逻辑教程解析
- C#编程实现显卡硬件信息的获取方法
- 前端世界核心-HTML+CSS+JS团队服务网页模板开发
- 精选SQL面试题大汇总
- Nacos Server 1.2.1在Linux系统的安装包介绍
- 易语言MySQL支持库3.0#0版全新升级与使用指南
- 快乐足球响应式网页模板:前端开发全技能秘籍
- OpenEuler4.19内核发布:国产操作系统的里程碑
- Boyue Zheng的LeetCode Python解答集