排序算法的简单认识

我就是我 2023-10-01 19:31 1阅读 0赞

在进行很多便捷算法之前总是要实现对象的有序化，而这就将使用到排序相关的算法，即使目前诸多高级语言已然完成对于排序算法的封装，用户只需导入对应库文件即可调用排序算法完成排序，无需手写排序算法，但具体的排序算法的选择就必须对于排序算法有所认识。本文就将介绍两个简单的排序算法：选择排序与冒泡排序。

### 选择排序 ###

为什么称为选择排序？  
该算法每次都是对于未排序的关键字进行比较，选择出最小或最大的关键字，再对其交换位置，实现一次排序，需进行多次比较。

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。  
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。在复杂度分析上，它最大的特点就是交换移动数据的次数较少，无需占用较大的内存空间。

#### 算法代码实现 ####

假设存在一个长度为 n 的数组，需要进行选择排序，每次下标变量设为 i ，即 1<=i<=n 。算法实现的基本思路是将数组进行 n-1 次关键字的比较，即对于数组下标对应值的比较，记录下标存进 min 或 max ，最后将其关键字与第 i 个关键字进行交换，完成一次选择。

选择排序基本存在两层 for 循环嵌套，最外层循环是为了保证 n-1 次排序，第二层 for 循环是为了在每一次排序的过程中寻找最值的下标，并且避免死循环，内层循环将从 i+1 开始进行比较。它们对于循环的判断条件区别如下：

*  外层循环：从零开始且小于数组长度减一，迭代语句为迭代标志加一
 *  内层循环：从 i+1 开始小于数组长度，迭代语句为迭代标志加一

内层循环中的选择语句是当前迭代标志对应的数组元素与记录当前剩余部分最值下标的对应数组元素的比较，按排序要求选择大小关系，进入选择语句，将最值下标赋给记录变量。

排序顺序主要看你的下标记录值的情况，在每一次比较中，下标记录较大值，为降序排序，下标记录较小值，为升序排序，下面将展示升序排序代码实现。

public class SelectionSort implements IArraySort {
        
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception {
        
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            // 总共要经过 N-1 轮比较
            for (int i = 0; i < arr.length - 1; i++) {
        
                int min = i;
                // 每轮需要比较的次数 N-i
                for (int j = i + 1; j < arr.length; j++) {
        
                    if (arr[j] < arr[min]) {
        
                        // 记录目前能找到的最小值元素的下标
                        min = j;
                    }
                }
    
                // 将找到的最小值和i位置所在的值进行交换
                if (i != min) {
        
                    int tmp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = tmp;
                }
    
            }
            return arr;
        }
    }

与选择排序同属基础排序算法的还有冒泡排序，它也是基于比较与交换实现对于对象的排序的算法，思路十分简单。开始介绍吧！

### 冒泡排序 ###

冒泡排序也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

假设所需排序的数组为 \[2,1,3,4,5,6,7,8,9\] ，尝试使用以上思路下的冒泡排序算法来进行的话，将会发现除了第一次交换数据有所意义之外，对于后面已然有序的数组而言，应该结束循环，完成排序，但它没有，它还是义无反顾地执行了 n-2 次循环。这将有一定地优化空间。

优化算法思路就是立一个 flag 作为标志，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序，无需重复进行多次循环，在数据规模巨大的情况下，这种优化所起到的作用是强大的。

#### 算法代码实现 ####

与选择排序一致，拥有两层 for 循环，外层循环决定排序次数，内层循环决定排序做法。冒泡排序常常是从左到右进行移动元素，所以，内层循环迭代标志需小于数组长度减已排序次数。内层循环每次比较，只要反序，直接交换位置。

##### 简单算法 #####

public class BubbleSort implements IArraySort {
        
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception {
        
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
            for (int i = 1; i < arr.length; i++) {
        
                for (int j = 0; j < arr.length - i; j++) {
        
                    if (arr[j] > arr[j + 1]) {
        
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                    }
                }
            }
            return arr;
        }
    }

##### 优化算法： #####

public class BubbleSort implements IArraySort {
        
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception {
        
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            for (int i = 1; i < arr.length; i++) {
        
                // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                boolean flag = true;
    
                for (int j = 0; j < arr.length - i; j++) {
        
                    if (arr[j] > arr[j + 1]) {
        
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
    
                        flag = false;
                    }
                }
    
                if (flag) {
        
                    break;
                }
            }
            return arr;
        }
    }

### 算法比较 ###

算法的比较，无非从算法复杂度（即时间复杂度与空间复杂度）分析以及算法稳定性下手，简单讲一下这些概念：

*  算法复杂度：算法复杂度可分为时间复杂度与空间复杂度，是作为一个算法评判一个优质算法的基本标准，往往一个优质算法，是可以做到一个时间复杂度与空间复杂度的很好平衡，但在某些情况下，一个极端偏向其中一个复杂度的算法也不为一个优质算法。
 *  时间复杂度 ：算法所耗费时间，常常使用大写 O()表示，可分为常数阶，即O(常数)，函数阶，如线性阶O(f(n))、平方阶O(f(n^2))等等
 *  空间复杂度：算法代码运行耗费的内存空间。
 *  算法稳定性：对于运行算法代码前后的无需改变部分的判断，如果发生了一定改变，即使基本性质不变，它也是不稳定的。  
    举个例子 5，8，5，2，9 我们知道第一遍选择第一个元素 5 会和 2 交换，那么原序列中 2 个 5 的相对位置前后顺序就破坏了，就是不稳定的。

冒泡排序优缺点：

*  优点: 比较简单，空间复杂度较低，是稳定的；
 *  缺点: 时间复杂度太高，效率慢；

选择排序优缺点：

*  优点：一轮比较只需要换一次位置；
 *  缺点：效率慢，不稳定

![求点赞转发][format_png]

[format_png]: https://img-blog.csdnimg.cn/img_convert/f8373e8744c0e5391af5ce9bc89a0cc4.webp?x-oss-process=image/format,png