每日一算-选择排序算法

刺骨的言语ヽ痛彻心扉 2024-03-22 17:21 44阅读 0赞

大家好，我是易安！

今天我们开始每日一算的篇章，今天带来的是选择算法。

**选择排序**是一种简单而高效的排序算法，它通过从列表的未排序部分中重复选择最小（或最大）元素并将其移动到列表的已排序部分来工作。该算法反复从列表的未排序部分中选择最小（或最大）的元素，并将其与未排序部分的第一个元素交换。对列表中剩余的未排序部分重复此过程，直到整个列表排序完毕。选择排序的一种变体称为“双向选择排序”，它通过在最小元素和最大元素之间交替遍历元素列表，这种方式在某些情况下可以更快。

![alt][]

选择排序算法

> 该算法在给定数组中维护两个子数组。
> 
>  *  已经排序的子数组。
>  *  剩余的子数组未排序。
> 
> 在选择排序的每次迭代中，从未排序的子数组中选取最小元素（考虑升序）并将其移动到已排序子数组的开头。
> 
> 每次迭代后，已排序的子数组大小增加一，未排序的子数组大小减少一。
> 
> 在 N（数组的大小）次迭代之后，我们将得到一个排序的数组。

### **选择排序流程图：** ###

![alt][alt 1]

### **选择排序原理？** ###

> 让我们以下面的数组为例：**arr\[\] = \{64, 25, 12, 22, 11\}**
> 
> **第一步：**
> 
>  *  对于排序数组中的第一个位置，整个数组从索引 0 到 4 依次遍历。 **当前存放64**的第一个位置，遍历整个数组后显然 **11**是最低值。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">64</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">25</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">11</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
>  *  **因此，将 64 替换为11。**经过一次迭代后，恰好是数组中最小值的 11 往往会出现在排序列表的第一个位置。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">11</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">25</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **第二步：**
> 
>  *  对于存在 25 的第二个位置，再次按顺序遍历数组的其余部分。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">11</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">25</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
>  *  遍历后发现 **12**是数组中倒数第二的值，应该出现在数组的第二位，因此交换这些值。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">11</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">12</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">25</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **第三步：**
> 
>  *  现在，对于第三位，再次出现 **25 的**地方遍历数组的其余部分并找到数组中第三小的值。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">11</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">25</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
>  *  遍历时， **22**是第三小的值，它应该出现在数组的第三位，因此将 **22**与第三位的元素交换。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">11</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">22</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">25</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **第四步：**
> 
>  *  同样，对于第四个位置，遍历数组的其余部分，找到数组中第四小的元素
>  *  由于 **25**是第四低的值，因此它将排在第四位。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">11</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;"><strong style="font-weight: bold; color: black;">25</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; font-weight: bold; background-color: #f0f0f0; min-width: 85px;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; text-align: left; min-width: 85px;"></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **第五步：**
> 
>  *  最后，数组中存在的最大值自动放置在数组的最后一个位置
>  *  结果数组是排序后的数组。
> 
> <table style="display: table; text-align: left;"> 
>  <thead> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; font-weight: bold; background-color: #f0f0f0; min-width: 85px; text-align: center;">11</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; font-weight: bold; background-color: #f0f0f0; min-width: 85px; text-align: center;">12</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; font-weight: bold; background-color: #f0f0f0; min-width: 85px; text-align: center;">22</th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; font-weight: bold; background-color: #f0f0f0; min-width: 85px; text-align: center;"><strong style="font-weight: bold; color: black;">25</strong></th> 
>    <th style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; font-weight: bold; background-color: #f0f0f0; min-width: 85px; text-align: center;">64</th> 
>   </tr> 
>  </thead> 
>  <tbody style="border: 0;"> 
>   <tr style="border: 0; border-top: 1px solid #ccc; background-color: white;"> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; min-width: 85px; text-align: center;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; min-width: 85px; text-align: center;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; min-width: 85px; text-align: center;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; min-width: 85px; text-align: center;"></td> 
>    <td style="font-size: 16px; border: 1px solid #ccc; padding: 5px 10px; min-width: 85px; text-align: center;"></td> 
>   </tr> 
>  </tbody> 
> </table>

### **实战演练** ###

请按照以下步骤实现代码：

*  将最小值 ( **min\_idx** ) 初始化为位置 0。
 *  遍历数组，找到数组中的最小元素。
 *  在遍历时，如果找到任何小于 **min\_idx 的元素，则交换两个值。**
 *  然后，递增 **min\_idx**以指向下一个元素。
 *  重复直到数组被排序。

下面是上述方法的实现：

*  **java**版本

import java.io.*;
    public class SelectionSort
    {
        
     void sort(int arr[])
     {
        
      int n = arr.length;
    
      // 逐步移动未排序数组的边界
      for (int i = 0; i < n-1; i++)
      {
        
       //查找未排序数组中的最小元素
       int min_idx = i;
       for (int j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
         min_idx = j;
    
       // 将找到的最小元素与第一个元素进行交换
       int temp = arr[min_idx];
       arr[min_idx] = arr[i];
       arr[i] = temp;
      }
     }
    
     // 打印排序后的数组结果
     void printArray(int arr[])
     {
        
      int n = arr.length;
      for (int i=0; i<n; ++i)
       System.out.print(arr[i]+" ");
      System.out.println();
     }
    
    
     public static void main(String args[])
     {
        
      SelectionSort ob = new SelectionSort();
      int arr[] = {64,25,12,22,11};
      ob.sort(arr);
      System.out.println("Sorted array");
      ob.printArray(arr);
     }
    }

**输出**

排序数组：
    11 12 22 25 64

### **选择排序的复杂度分析：** ###

**时间复杂度：**选择排序的时间复杂度为 O(N 2 )，因为有两个嵌套循环：

*  一个循环一个一个地选择Array的一个元素= O(N)
 *  将该元素与每个其他数组元素进行比较的另一个循环 = O(N)

因此整体复杂度 = O(N) \* O(N) = O(N\*N) = O(N 2 )

**辅助空间：** O(1) 作为唯一使用的额外内存用于临时变量，同时交换数组中的两个值。选择排序永远不会进行超过 O(N) 次交换，并且在内存写入是一项代价高昂的操作时非常有用。

### **选择排序算法是否稳定？** ###

**稳定性**：默认实现**不稳定**。然而，它可以变得稳定。这个后续再讲。

### **选择排序算法的优点：** ###

*  简单易懂。
 *  保留具有相同键的项目的相对顺序，这意味着它是稳定的。
 *  适用于小型数据集。
 *  它适用于各种类型的数据类型。
 *  选择排序是一种就地排序算法，这意味着它不需要任何额外的内存来对列表进行排序。
 *  它具有 O(n^2) 的最佳情况和平均情况时间复杂度，使其对于小型数据集非常有效。
 *  很容易修改为按升序或降序排序。
 *  它可以很容易地在硬件中实现，使其适用于实时应用。
 *  它也可以用作更有效的排序算法中的子程序。
 *  它不需要任何特殊的内存或辅助数据结构，使其成为轻量级解决方案。
 *  该算法可以轻松并行，允许在多核处理器上进行高效排序。
 *  它可以在有限的内存环境中使用，因为它需要最少的额外内存。
 *  它易于理解，使其成为教学目的的热门选择。
 *  它适用于对唯一键很少的数据进行排序，因为它在这种情况下表现良好。

### **选择排序算法的缺点：** ###

*  选择排序在最坏和平均情况下的时间复杂度为 O(n^2)。
 *  在大型数据集上效果不佳。
 *  选择排序算法需要多次迭代列表，因此会导致不平衡分支。
 *  选择排序的缓存性能很差，因此对缓存不友好。
 *  不是自适应的，这意味着它没有利用列表可能已经排序或部分排序的事实
 *  对于具有慢速随机存取存储器 (RAM) 的大型数据集来说不是一个好的选择
 *  它不是比较排序，也没有像合并排序或快速排序那样的任何性能保证。
 *  它的缓存性能很差
 *  由于其高分支预测错误率，它可能导致分支预测不佳
 *  它有很多写操作，导致在存储速度慢的系统上性能不佳。
 *  它不是可并行算法，这意味着它不能轻易拆分以在多个处理器或内核上运行。
 *  它不能很好地处理具有许多重复项的数据，因为它会进行许多不必要的交换。
 *  在大多数情况下，它可以被其他算法（如快速排序和堆排序）超越。

### **总结：** ###

*  选择排序是一种简单易懂的排序算法，其工作原理是从列表的未排序部分重复选择最小（或最大）的元素并将其移动到列表的已排序部分。
 *  对列表中剩余的未排序部分重复此过程，直到整个列表排序完毕。
 *  在最坏和平均情况下，它的时间复杂度为 O(n^2)，这使得它对于大型数据集的效率较低。
 *  选择排序是一种稳定的排序算法。
 *  它可用于对不同类型的数据进行排序。
 *  它在特定应用程序中很有用，例如小型数据集和内存受限系统。

本文由[ mdnice ][mdnice]多平台发布

[alt]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/8a5510f2a9ec4ea3b8c8ab6c2afed151.png
[alt 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/1a644dc108c54d78bac841652badb2ae.png
[mdnice]: https://mdnice.com/?platform=4