您现在的位置是:首页 >技术教程 >软考算法-排序篇-下网站首页技术教程

软考算法-排序篇-下

不拿博客专家不改名 2024-05-30 13:36:12
简介软考算法-排序篇-下

一:故事背景

最近在准备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 概念

归并排序的过程分为三步:

  1. 分解:将n个元素分成各含n/2个元素的子序列
  2. 求解:使用归并排序对两个子序列递归的进行排序
  3. 合并:将两个已经排好的子序列进行合并得到排序结果

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) )稳定

七:总结提升

此篇文章为大家介绍了冒泡排序、快速排序、归并排序、基数排序、并且给出了这几种排序对应的图和代码。希望通过此篇博客,大家对排序算法有一个更加深刻的了解。学习算法,学会看时间复杂度和空间复杂度,在以后的开发中优化代码。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。