您现在的位置是:首页 >技术教程 >软考算法-排序篇-下网站首页技术教程
软考算法-排序篇-下
简介软考算法-排序篇-下
排序篇
一:故事背景
最近在准备5月底的软件工程师的考试,这个考试最困难的就是算法部分了。这是排序算法的第二篇文章,本篇文章将会分享四种算法,分别是 冒泡排序、快速排序、归并排序、基数排序。本文将于上篇文章一样,详细的介绍各种排序,给出对应的图和代码实现,比较不同排序算法。希望大家通过此文章,了解不同排序算法。
二:冒泡排序
2.1 概念
通过相邻元素(i与i-1)之间的比较和交换,将排序码较小的元素逐渐从底层移向顶层。整个过程像水底的气泡逐渐向上冒,由此得名冒泡排序。
2.2 画图表示
通过观察动图可以发现,与我们上面描述的概念相符,相邻的数据一直在比较,并且逐渐的在排成由小到大。
2.3 代码实现
以下为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 - i - 1; j++) {
// 如果前一个元素比后一个元素大,则交换它们的位置
if (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 = { 3, 44, 38, 5, 47, 15, 36}; // 定义一个数组
bubbleSort(arr); // 调用 bubbleSort 方法进行冒泡排序
System.out.println("Sorted array:"); // 打印排序后的数组
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
2.4 总结提升
- 冒泡排序的时间复杂度为 O(n²)
- 在冒泡排序中,只需要使用一个临时变量来交换两个元素的值,所以空间复杂度是常量级别的,即O(1)。无论输入的数据规模大小如何,所需的额外空间都是固定的,与输入规模无关。
- 冒泡排序是一种原地排序算法,可以对原始数组进行排序,不需要使用额外的空间。
三:快速排序
3.1 概念
通过一趟排序将要排序的数据分成独立的两个部分,其中一部分的所有数据比另外一部分的数据的所有数据都要小,然后按照此方法对这两部分分别进行快速排序,整个排序过程递归进行,从而达到整个数据编程有序序列。
3.2 画图表示
3.3 代码实现
public class QuickSort {
public static void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
private static int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && nums[i] < pivot) {
i++;
}
while (i <= j && nums[j] >= pivot) {
j--;
}
if (i < j) {
swap(nums, i, j);
}
}
swap(nums, left, j);
return j;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {5, 1, 7, 3, 9, 2};
quickSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
}
3.4 总结提升
- 快速排序的核心是一直选出一个应该放到指令位置的数据,在我们这里体现的就是选择的基准数据。快排也属于一种交换排序,相对于冒泡排序而言,其效率更高。快排的时间复杂度为O(nlogn) ~ O(n^2)
- 快速排序的空间复杂度是 O(logn)。这是因为快速排序算法需要递归地调用自己,每次递归需要使用一个栈空间来保存参数、返回地址和局部变量等信息。在平均情况下,快速排序算法的递归深度是 O(logn),因此它的空间复杂度也是 O(logn)。
- 在最坏情况下,快速排序算法的递归深度是 O(n),因此它的空间复杂度也是 O(n)。在最坏情况下,快速排序算法的空间复杂度比较高,但是通常情况下快速排序算法的空间复杂度较低,适用于处理大规模数据的排序。
四:归并排序
4.1 概念
归并排序的过程分为三步:
- 分解:将n个元素分成各含n/2个元素的子序列
- 求解:使用归并排序对两个子序列递归的进行排序
- 合并:将两个已经排好的子序列进行合并得到排序结果
4.2 画图表示
4.3 代码实现
public class MergeSort {
public static void sort(int[] arr) {
int n = arr.length;
if (n < 2) {
return;
}
int mid = n / 2;
int[] leftArr = new int[mid];
int[] rightArr = new int[n - mid];
System.arraycopy(arr, 0, leftArr, 0, mid);
System.arraycopy(arr, mid, rightArr, 0, n - mid);
sort(leftArr);
sort(rightArr);
merge(leftArr, rightArr, arr);
}
private static void merge(int[] leftArr, int[] rightArr, int[] resultArr) {
int i = 0, j = 0, k = 0;
while (i < leftArr.length && j < rightArr.length) {
if (leftArr[i] <= rightArr[j]) {
resultArr[k++] = leftArr[i++];
} else {
resultArr[k++] = rightArr[j++];
}
}
while (i < leftArr.length) {
resultArr[k++] = leftArr[i++];
}
while (j < rightArr.length) {
resultArr[k++] = rightArr[j++];
}
}
}
4.4 总结提升
- 归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。
- 归并排序的时间复杂度可以分为两部分来考虑。首先是将数组拆分成较小的子数组,这个过程需要O(logn)的时间复杂度,因为它涉及到了对数级别的递归。然后是将子数组合并成一个有序的数组,这个过程需要O(n)的时间复杂度,因为它需要遍历整个数组并对每个元素进行比较。因此,归并排序的总时间复杂度为O(nlogn)。
- 归并排序的空间复杂度为O(n),因为在合并子数组时,需要创建一个大小为n的辅助数组来存储排序后的元素。在归并排序的过程中,由于每次都需要将数组分成两半,因此需要创建递归调用栈,栈的深度为logn。因此,归并排序的总空间复杂度为O(n)。
五:基数排序
5.1 概念
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort。顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。
基数排序属于一种按位排序,从个位逐渐向上进行比较。
5.2 画图表示
5.3 代码实现
public class RadixSort {
// 获取数组中最大值
public static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 基数排序
public static void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
// 计数排序
public static void countSort(int[] arr, int exp) {
int[] output = new int[arr.length];
int[] count = new int[10];
// 统计每个数字出现的次数
for (int i = 0; i < arr.length; i++) {
count[(arr[i] / exp) % 10]++;
}
// 计算每个数字的位置
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 将数字按照计算出的位置放入 output 数组中
for (int i = arr.length - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将 output 数组中的结果复制回 arr 数组中
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
// 测试代码
public static void main(String[] args) {
int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
}
5.4 总结提升
基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法
六:表格比较
算法名 比较项 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
冒泡排序 | O(n²) | O(1) | 稳定 |
快速排序 | O(nlogn) ~ O(n^2) | O(nlogn) ~ O(n) | 不稳定 |
归并排序 | O(nlogn) | O(n) | 稳定 |
基数排序 | O (nlog®m) | O(n+k) ) | 稳定 |
七:总结提升
此篇文章为大家介绍了冒泡排序、快速排序、归并排序、基数排序、并且给出了这几种排序对应的图和代码。希望通过此篇博客,大家对排序算法有一个更加深刻的了解。学习算法,学会看时间复杂度和空间复杂度,在以后的开发中优化代码。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。