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

今天的小结

news 2025/8/3 5:28:20

1、冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历待排序的元素列表，比较相邻的元素并交换它们的位置，直到整个列表排序完成。冒泡排序的基本思想是通过不断交换相邻元素，将最大（或最小）的元素逐渐 “冒泡” 到列表的一端。

冒泡排序的基本步骤：

从列表的第一个元素开始，比较它与下一个元素的大小。

如果当前元素大于下一个元素，则交换它们的位置，使较大的元素 “冒泡” 到列表的末尾。

继续比较和交换相邻元素，直到达到列表的末尾。

重复上述步骤，直到整个列表排序完成。

每次比较两个相邻的元素，并且按照升序或者降序的规则进行位置的替换，需要使用到双层循环遍历，每遍历一圈只会对对一个数值进行排序，总共需要遍历n-1次；

稳定性：稳定，不会对数值相同的两个元素交换位置；

时间复杂度：O(n2)；

空间复杂度：1

使用情况：适合数据量较小的情况；

package com.ma.冒泡;import java.util.Arrays;
import java.util.Scanner;
//随机输入10个数字进行排序
public class Test1 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] a = new int[10];for (int i = 0; i < a.length; i++) {a[i] = sc.nextInt();}for (int i = 0; i < a.length - 1; i++) {for (int j = 0; j < a.length - 1 - i; j++) {int tmp = 0;if (a[j] > a[j + 1]) {tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}System.out.println(Arrays.toString(a));}
}

2、快速排序

快速排序（Quick Sort）是一种常用且高效的排序算法，它采用分治的思想。快速排序的基本思想是选择一个基准元素，将列表中的元素分割为两部分，使得左边部分的所有元素小于基准元素，右边部分的所有元素大于基准元素，然后对这两部分分别进行递归排序。

快速排序的基本步骤：

选择一个基准元素。通常可以选择列表的第一个元素、最后一个元素或随机选择。

将列表分割为两部分，使得左边部分的所有元素小于基准元素，右边部分的所有元素大于基准元素。这个过程称为分区（partitioning）。

对分割后的两部分递归地应用快速排序算法。即分别对左边部分和右边部分进行快速排序。

合并排序后的左右两部分，得到最终排序结果。

快速排序的平均时间复杂度是 O(n log n)，其中 n 是待排序列表的长度。尽管快速排序在大多数情况下表现良好，但在最坏情况下，时间复杂度为 O(n^2)。快速排序是一种常用的排序算法，被广泛应用于各种编程环境和场景中。

稳定性：不稳定，数值相同的两个元素可能交换位置；

时间复杂度：O(nlogn)，如果基数刚好为最大或者最小值则为O(n2)；

快速排序最好时间复杂度是O(n * log n),最坏时间复杂度是O(n*2) ，平均复杂度是O(n * log n)

空间复杂度：O(nlogn)，如果基数刚好为最大或者最小值则为O(n)；

使用情况：适合数据量较小的情况；

package com.ma.快排;import java.util.Arrays;public class Test3 {public static void main(String[] args) {int[] arr = {-9, 78, 0, 0, 1, 0, 3, -1, 23, -56, 7};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}public static void quickSort(int[] array, int low, int high) {/*** 分析：* 1.选定一个基准值，array[low]* 2.右指针从右向左遍历high--，查找比基准值小的数据，左指针从左向右low++，查找比基准值大的数据* 3.如果指针未相遇，交换左右两值位置，如果指针相遇，则替换基准值的位置* 4.左递归，右递归*/// 方法退出条件,指针相遇或错过if (low >= high) {return;}// 1. 指定基准值和左右指针记录位置int pivot = array[low];int l = low;int r = high;int temp = 0;// 2. 遍历条件，左右指针位置while (l < r) {// 2.1 右侧遍历while (l < r && array[r] >= pivot) {r--;}// 2.2 左侧遍历while (l < r && array[l] <= pivot) {l++;}// 2.3 l指针还在r指针左侧，尚未相遇if (l < r) {temp = array[l];array[l] = array[r];array[r] = temp;}}// 3. 当左右指针相遇，交换基准值位置array[low] = array[l];array[l] = pivot;// 4. 根据条件左侧递归遍历if (low < l) {quickSort(array, low, l - 1);}// 5. 根据条件右侧递归遍历if (r < high) {quickSort(array, r + 1, high);}}}