Java之排序算法

我就是我 2024-03-23 12:19 63阅读 0赞

### 一.概括 ###

###### 一.算法介绍 ######

Java算法是用于解决不同问题的计算机程序。它是许多应用程序的核心，例如搜索引擎、金融分析、图像处理等。Java算法的使用可以提高应用程序的性能和效率，使它们更加灵活，可靠。

Java中包含众多算法，它们可以分为以下几种类型：

1.  排序算法：排序算法用于对数据进行排序，例如冒泡排序、选择排序、插入排序、快速排序等。
2.  搜索算法：搜索算法用于从大量数据中查找指定的数据，例如深度优先搜索、广度优先搜索、二分搜索等。
3.  图论算法：图论算法用于处理图形和图形数据结构，例如最短路径算法、最小生成树算法、拓扑排序算法等。
4.  动态规划算法：动态规划算法用于解决复杂问题和最优化问题，例如最长公共子序列算法、背包问题算法等。
5.  分治算法：分治算法用于将大问题分解成小问题并逐步解决它们，例如归并排序、快速排序、Strassen矩阵乘法等。

Java算法的选择取决于所面临的问题。不同的算法可以解决相同的问题，但它们的效率和性能不同。因此，选择正确的算法可能对系统的整体性能产生巨大的影响。对于数据密集型应用程序，使用快速排序算法可以提高性能。对于搜索引擎等需要处理大量数据的应用程序，使用分布式搜索算法可以提高效率。

Java算法的重要性是不言而喻的。算法是计算机的核心，决定了程序的效率和性能。选择正确的算法和数据结构可以大大提高应用程序的性能和可扩展性。它还可以节省硬件和软件资源，降低了开发成本，增强了程序的可靠性。

总之，Java算法是编写高效、可靠和可扩展应用程序的关键之一。选择正确的算法和数据结构对系统性能的影响非常大。在开发过程中，应该认真评估选择的算法和数据结构，以确保应用程序具有优越的性能和可靠性。

###### 二.排序算法介绍 ######

排序算法是通过比较不同元素之间的大小或者其他关键字来实现排序的一种算法。Java中常见的排序算法有插入排序、快速排序、冒泡排序、选择排序、归并排序等等。

>  *  插入排序适用于小规模数据排序，时间复杂度为O(n^2)，是一种稳定性较高的排序算法。适用于小规模数据排序，简单易实现。
>  *  快速排序采用的是分治法思想，适用于大规模数据排序，时间复杂度为O(nlogn)，是所有基于比较的排序算法里最优的一种。但当数据量较小时，快速排序的效率相比其他排序算法较低。
>  *  冒泡排序和选择排序则是两种时间复杂度为O(n^2)的算法，适用于小规模数据排序。其中冒泡排序可以通过优化而达到O(n)的时间复杂度，但是其效率在大数据量的情况下仍然较低。
>  *  归并排序在Java中也被广泛使用，具有较高的稳定性和效率，适用于大规模数据排序，时间复杂度为O(nlogn)，但是其空间复杂度较高。

因此，在选择排序算法时应根据具体情况来选择最合适的算法，以达到较高的效率和较低的时间复杂度。当数据规模较小且排序稳定性要求较高时可以选择插入排序或选择排序；当数据量较大时则推荐使用快速排序或归并排序。

###### 三.插入排序 ######

插入排序是通过将元素插入到已经排好序的数组中来排序的一种算法。

> 插入排序的思路：
> 
>  *  依次遍历序列中的每个元素；
>  *  将该元素插入到已经排好序的序列中，形成一个新的已排序序列。

示例代码：

public static void main(String[] args) {
        
            int[] is = {
        10, 3, 9, 1, 6, 8, 5, 2};
            insertionSorting(is);
            System.out.println("排序后的数组为：" + Arrays.toString(is));
        }
    
        public static void insertionSorting(int[] is) {
        
            //从第二个元素开始，和前面的有序表进行比较
            for (int i = 1; i < is.length; i++) {
        
                int temp = is[i];//记录要插入的值，将待插入的值取出并保存在temp中，防止数据移动时该元素丢失
                int j = i - 1;
                //从后往前进行遍历比较
                for (; j >= 0; j--) {
        
                    if (is[j] > temp) {
        
                        is[j + 1] = is[j];//后移一个位置
                    } else {
        
                        is[j + 1] = temp;//直接将待插入的元素，插入在有序表的尾部
                        break;
                    }
                }
                is[j + 1] = temp;//遍历完有序表所有大于temp的元素后，将temp插入
            }
        }

插入排序是一种易于实现且在小规模数据中表现良好的排序算法。在实践中，对于某些Java应用程序而言，插入排序的执行速度可能优于归并排序和快速排序。

###### 4.快速排序 ######

快速排序是非常常见的一种排序算法，其执行速度快、效率高，能够在处理大块数据时表现出色。

> 快速排序的思路：
> 
>  *  选择一个基准元素，通常是第一个或最后一个元素；
>  *  将小于基准元素的所有元素移动到其左边，将大于基准元素的所有元素移动到其右边；
>  *  对左右两个子序列递归地调用快速排序。

示例代码：

public static void main(String[] args) {
        
            //定义一个要排序的初始化数据
            int[] is = new int[]{
        19, 28, 8, 23, 10, 21, 9};
            quickSort(is, 0, is.length - 1);
            System.out.println("最后排序后的结果：" + Arrays.toString(is));
        }
    
        public static void quickSort(int[] is, int left, int right) {
        
            if (left < right) {
        
                //开始排序 从左到右,返回一个基准位置
                int pivot = partition(is, left, right);
                // 基准元素一定比左边的数大，所以左边分区最大值是：pivot - 1，分区范围是[left, pivot - 1]
                quickSort(is, left, pivot - 1);
                // 基准元素一定比右边的数小，所以右边分区最小值是：pivot + 1，分区范围是[pivot + 1, right]
                quickSort(is, pivot + 1, right);
            }
        }
    
        public static int partition(int[] is, int left, int right) {
        
            // 定义基准元素
            int pivotValue = is[left];
            // 遍历（条件就是分区左边索引小于右边索引）
            while (left < right) {
        
                // 从右边right开始遍历，找到一个数比基准数小
                while (left < right && is[right] >= pivotValue) {
        
                    // 未找到，继续往前找
                    right--;
                }
                // 找到了，则把找到小值放到此时左边索引的位置
                // 第一次进入时,基准元素已存放到临时值pivotValue了，第一次就相当于放到基准位置了，同时，arr[right]也腾出了一个位置
                is[left] = is[right];
                // 从左边left开始遍历，找到一个数比基准数大
                while (left < right && is[left] <= pivotValue) {
        
                    // 未找到，继续往后找
                    left++;
                }
                // 找到了，则把找到大值放到此时右边索引的位置（也就是腾出的位置）
                // 同时，arr[left]也腾出了一个位置
                is[right] = is[left];
            }
            // left等于right说明遍历结束了，把基准元素插入到腾出的位置，也就是arr[left]或者arr[right]
            is[left] = pivotValue;
            // 返回基准元素插入的位置
            return left;
        }

快速排序通常在大量元素需要排序的情况下使用。由于其执行速度极快，因此它在工业生产环境中得到广泛应用。除此之外，快速排序还兼备了多个优势，因此这种算法已经成为Java社区首选的排序算法之一。

###### 5.冒泡排序 ######

冒泡排序是一种通过逐步交换邻近元素的排序算法。

> 冒泡排序的思路：
> 
>  *  依次遍历序列中的每个元素；
>  *  如果当前元素比其后面的元素大，则交换两个元素的位置；
>  *  继续进行以上步骤，直到没有可以交换的元素。

示例代码：

public static void main(String[] args) {
        
            //定义一个基本数组
            int[] arr = {
        1, 5, 3, 4, 7, 8, 9, 6, 2, 0};
            System.out.println("排序前的数组为：" + Arrays.toString(arr));
            //外循环是控制排序的次数N-1, 每次循环结束确定一个最大值
            for (int i = 0; i < arr.length - 1; i++) {
        
                // 内循环是比较的次数N-i
                for (int j = 0; j < arr.length - 1 - i; j++) {
        
                    if (arr[j] > arr[j + 1]) {
        
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
            System.out.println("排序后的数组为：" + Arrays.toString(arr));
        }

由于冒泡排序的算法效率较低，因此我们不推荐在大类别内使用冒泡排序。不过，在某些排序场景中，该算法的实现效果以及易于理解的特点可能会产生较大的影响。

###### 6.选择排序 ######

选择排序是一种通过依次选择未排序序列中的最小元素来排序的算法。

> 选择排序的思路：
> 
>  *  依次遍历序列中的每个元素；
>  *  找到未排序序列中最小的元素，将其插入到已排序序列的末尾。

示例代码：

public static void main(String[] args) {
        
            int[] arr={
        99,2,5,9,3,7,4,1,6,8,23};
            System.out.println("交换之前：" + Arrays.toString(arr));
            // 做第i趟排序
            for(int i = 0; i < arr.length - 1; i++) {
        
                int k = i;
                // 选最小的记录
                for(int j = k + 1; j < arr.length; j++){
        
                    if(arr[j] < arr[k]){
        
                        //记下目前找到的最小值所在的位置
                        k = j;
                    }
                }
                //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
                if(i != k){
        
                    //交换a[i]和a[k]
                    int temp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = temp;
                }
            }
            System.out.println("交换后：" + Arrays.toString(arr));
        }

选择排序是一种易于实现的排序算法，但其性能在大规模数据下表现差劣。对于一些小规模数据的排序操作，选择排序可以表现出比较优秀的性能表现。

###### 7.归并排序 ######

归并排序也是常见的一种排序算法，它的运行速度鲁棒性较好，在算法课程中往往是作为排序算法的标准解决方案出现。

> 归并排序的思路：
> 
>  *  将原序列不断递归地分解为左、右两个子序列，直到不可再分；
>  *  对左右两个子序列分别进行递归调用，最终将子序列进行合并。

示例代码：

public static void main(String[] args) {
        
            //定义一个基础数组
            int[] arr = {
        9, 6, 5, 3, 1, 18, 8, 22, 7, 2, 4};
            System.out.println("排序前: " + Arrays.toString(arr));
            mergeSort(arr, 0, arr.length - 1);
            System.out.println("最终结果：" + Arrays.toString(arr));
    
        }
    
        public static void mergeSort(int[] arr, int left, int right) {
        
            //首先判断 left 和 right是否指向一个地方
            if (left == right) {
        
                return;
            }
            int pivot = (left + right) / 2;
            //先递归左边
            mergeSort(arr, left, pivot);
            //在递归右边
            mergeSort(arr, pivot + 1, right);
            //合起来
            merge(arr, left, pivot, right);
            System.out.println(Arrays.toString(arr));
        }
    
        //合并
        public static void merge(int[] arr, int left, int pivot, int right) {
        
            //定义第一段
            int s1 = left;
            //定义第二段
            int s2 = pivot + 1;
            //定义临时数组
            int[] temp = new int[right - left + 1];
            int i = 0;
    
            //判断s1,s2是否有数据，放入临时数组
            while (s1 <= pivot) {
        
                temp[i++] = arr[s1++];
            }
            while (s2 <= right) {
        
                temp[i++] = arr[s2++];
            }
            for (int j = 0; j < temp.length; j++) {
        
                arr[j + left] = temp[j];
            }
        }

由于归并排序具有良好的鲁棒性和算法效率，因此它在Java社区中得到了广泛的应用。在实践中，许多Java程序员都将其用作初学者的排序算法教程。此外，我们还可以对归并排序进行一定程度的优化，从而实现更快的排序结果。