知新_RL

这个屌丝很懒，什么也没留下！

热门标签

排序算法：选择排序算法

作者：知新_RL | 2024-08-02 20:17:19

踩

选择排序

选择排序算法有效地将元素排列成两个部分：已排序的子列表和未排序的子列表。这种方法简化了列表组织，提高了排序效率。在本文中，我们深入研究选择排序的机制，解释其对各种类型列表进行排序的过程和有效性。让我们探讨什么是选择排序以及它是如何工作的。

要点

选择排序的复杂度：
- 时间复杂度 -
- 空间复杂度 - O(1)

什么是选择排序？

选择排序，也称为就地比较排序，是一种简单的排序算法。它的工作原理是重复查找最小元素并将其放置在正确的排序位置。

选择排序的工作原理是将列表分为两个子列表：

排序子列表——从左到右构建在列表的左端。
未排序子列表- 这是未排序列表的其余部分，位于右端。

最初，已排序的子列表是空的，我们只有未排序的子列表。

在选择排序的每次迭代中，我们 –

在未排序的子列表中搜索最小的元素。
将其放在已排序子列表的末尾。

我们重复上述步骤，直到得到一个已排序的列表，并且未排序的子列表中不再有任何元素。每次迭代后，已排序子列表的大小都会增加，而未排序子列表的大小会减少。

注意 –我们正在搜索最小的元素，因为我们想按升序对列表进行排序。如果我们想按降序对列表进行排序，我们也可以搜索最大的元素。

选择排序的流程图

选择排序算法的流程图可以描述如下：

开始：开始该过程。
输入列表：获取要排序的列表或数组。
初始化：将当前索引设置为起始索引。这代表列表中未排序部分的开始。
查找最小值：遍历未排序部分的其余部分以查找最小元素。
Swap：将找到的最小元素与当前索引处的元素交换。
Increment Index：将当前索引增加 1，移动列表的已排序和未排序部分的边界。
检查：检查当前索引是否小于列表的长度 - 1。如果是，则返回到“查找最小值”步骤。如果不是，则所有元素都已排序。
结束：结束进程。该列表现在按升序排序。

选择排序如何工作？

回想一下上面按身高顺序排列学生的示例。在这种情况下，我们可以按照以下步骤将学生按身高顺序排列：

将学生队列分为两部分——已排列的和未排列的。
首先，将所有学生放入未安排的队列中。
从这个未排列的队列中，搜索最矮的学生，并将他/她放入已排列的学生列表中。
再次从未排列的队列中选择第二矮的学生。将此学生放入已安排的队列中，紧接在最小的学生之后。
重复上述步骤，直到所有学生都被放入排列好的队列中。你看到我们刚刚在这里做了什么吗？我们使用选择排序算法将所有学生按身高顺序排列。

现在，让我们考虑一下我们想要按升序对列表进行排序。以下是该算法将遵循的步骤：

从第一个元素开始。此时，整个列表尚未排序。并且排序后的子列表为空。
迭代列表以搜索其中的最小元素。
将此元素添加到已排序的子列表中，并将其从未排序的子列表中删除。换句话说，将未排序子列表中的最小元素与其正确排序位置处的元素交换。
重复上述步骤，直到未排序子列表中的所有元素都转移到已排序子列表中。

为了更好地理解选择排序，请回想一下最初包含元素5、6、4、2 的列表。

对该列表进行排序的步骤包括 -

从上图，我们可以推断出关于选择排序算法的以下结论：

我们有4 个元素，通过3 次交换得到了排序列表。由此，我们可以得出结论，要对大小为 n的列表进行排序，我们需要执行 n – 1 次迭代。
在第一步或迭代中，选择最小的元素（在本例中为 2）并将其添加到已排序的子列表中。类似地，每次迭代后，未排序元素中最小的元素被放置在其位置。我们在每次迭代中选择一个特定元素来对其进行排序。这就是为什么这种排序算法被称为选择的原因。
在选择排序中，每次迭代未排序的子列表时，仅对一个元素进行排序。
在第二步中，我们从元素 6 而不是 2 开始搜索。这是因为我们知道 2 已经处于正确的位置，从那里开始搜索不会有任何区别。第三步也一样。在每一步中，我们都从未排序的子列表开始搜索。这样，我们可以减少比较次数，从而减少程序的执行时间。

选择排序算法

我们知道，要使用选择排序对 n 个元素的列表进行排序，我们需要执行n-1 次迭代。

以下是选择排序的算法——


begin selectionSort(list)
  for i = 0 to sizeof(list) - 1    
      
       minIndex = i;
      
       for j = i + 1 to sizeof(list)
          
           if list[j] < list[mid_index]
               minIndex = j;
           end if
      
          swap(list[minIndex], list[i])
      
       end for
 
  end for
end selectionSort

现在让我们通过以下步骤来了解选择排序的算法-

从i = 0开始循环，直到达到列表的大小。在循环下——
- 声明一个名为minIndex 的变量。minIndex 有助于跟踪将与索引i处的元素交换的下一个元素的索引。
- 从j = i + 1运行嵌套 for 循环，直到达到列表的大小。我们用i + 1初始化j，因为它允许我们减少总比较次数。在这个循环下——
  - 检查索引j处的元素是否小于索引 mid_index 处的元素。如果是，请将 minIndex 设置为等于j。它帮助我们在未排序的子列表中搜索最小的元素。
  - 将索引i处的元素与索引minIndex处的元素交换。它允许我们将未排序子列表中的最小元素放置在已排序子列表的末尾。请注意，每次找到比 minIndex 小的元素时，我们都会更新minIndex的值。

现在我们已经了解了什么是选择排序，让我们看看如何通过代码实现选择排序算法。

选择排序代码

1. Java中的选择排序代码


// Selection Sort in Java
class SelectionSort
{
    void selectionSort(int arr[])
    {       
        int size = arr.length;
 
        // loop to iterate over the entire array
        for (int i = 0; i < size - 1; i++)
        {
            // set minIndex equal to the first unsorted element
            int minIndex = i;
         
          //iterate over unsorted sublist
            for (int j = i+1; j < size; j++)
      //helps in finding the minimum element
                if (arr[j] < arr[minIndex])
                    minIndex = j;
 
            // swapping the minimum element with the element at minIndex to place it at its proper position
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

2.Python中的选择排序代码


# Selection sort in Python
 
def selectionSort(arr):
 
   # loop to iterate over the array elements
   for i in range(len(arr)):
   
       # set min_index equal to the first unsorted element
       min_index = i
 
       # iterate over unsorted sublist
       for j in range(i+1, len(arr)):
 
    #helps in finding the minimum element
           if arr[min_index] > arr[j]:
               min_index = j
           
       # swapping the minimum element with the element at min_index to place it at its correct position
     
       arr[i], arr[min_index] = arr[min_index], arr[i]

3. C 中的选择排序代码


// Selection Sort in C++
//function to swap elements
void swap(int *xp, int *yp)
{
   int temp = *xp;
   *xp = *yp;
   *yp = temp;
}
void selectionSort(int arr[], int size)
{
   int i, j, minIndex;
   // loop to iterate over the entire array
   for (i = 0; i < size - 1; i++)
   {
       // set minIndex equal to the first unsorted element
       minIndex = i;
 
       //iterate over unsorted sublist
       for (j = i+1; j < size; j++)
 
      //helps in finding the minimum element
         if (arr[j] < arr[minIndex])
           minIndex = j;
       
// swapping the minimum element with the element at minIndex to place it at its correct position
       swap(&arr[minIndex], &arr[i]);
   }
}

4. C++ 中的选择排序代码


// Selection Sort in C++
void selectionSort(int arr[], int size)
{
   int i, j, minIndex;
   // loop to iterate over the entire array
   for (i = 0; i < size - 1; i++)
   {
       // set minIndex equal to the first unsorted element
       minIndex = i;
 
       //iterate over unsorted sublist
       for (j = i+1; j < size; j++)
      
    // helps in finding the minimum element
         if (arr[j] < arr[minIndex])
           minIndex = j;
       
// swapping the minimum element with the element at minIndex to place it at its correct position 
// using std::swap() method for swapping
       swap(arr[minIndex], arr[i]);
   }
}

5. JavaScript 中的选择排序代码


// Selection sort in JavaScript
function swap(arr,xp, yp)
{
   var temp = arr[xp];
   arr[xp] = arr[yp];
   arr[yp] = temp;
}
function selectionSort(arr)
{
   var i, j, minIndex;
 
   // loop to iterate over the entire array
   for (i = 0; i < arr.length - 1; i++)
   {
       // set minIndex equal to the first unsorted element
       minIndex = i;
 
       // iterate over unsorted sublist
       for (j = i + 1; j < arr.length; j++)
         if (arr[j] < arr[minIndex])
              minIndex = j;
 
       // swapping the minimum element with the element at minIndex
       swap(arr, minIndex, i);
   }
}

6. C# 中的选择排序代码


// Selection sort in C#
class ScalerTopics
{
   //selection sort function
   static void SelectionSort(int[] arr)
   {
       int size = arr.Length;
       // loop to iterate over the entire array
       for (int i = 0; i < size - 1; i++)
       {
           // set minIndex equal to the first unsorted element
           int minIndex = i;
 
           //iterate over unsorted sublist
           for (int j = i + 1; j < size; j++)
               if (arr[j] < arr[minIndex])
                   minIndex = j;
           // swapping the minimum element with the element at minIndex
           int temp = arr[minIndex];
           arr[minIndex] = arr[i];
           arr[i] = temp;
       }
   }
}

选择排序的复杂度分析

1.时间复杂度

为了更好地理解选择排序的时间复杂度，让我们将SelectionSort()函数分为以下部分：

循环遍历整个列表
- 零件交换元件。
循环以迭代未排序的子列表。

设列表中元素的数量为n。现在，我们知道对于第 1 部分，循环将运行 n 次。

在第 1 部分中，交换发生的次数将等于 n，并且每次交换将花费常数时间。因此，对于第 1 部分，我们可以说时间复杂度为O(n)。

第 2 部分嵌套在第 1 部分中运行的循环内。此循环有助于搜索最小数字。在这部分下，进行n次比较，执行时间恒定。换句话说，每执行一次第 1 部分，第 2 部分就会执行 n 次。如果第 1 部分执行 n 次，则第 2 部分将执行n * n次。

由此，我们可以说选择排序算法的复杂度为O(n ^ 2)。

现在让我们讨论最佳、平均和最坏情况下的时间复杂度。

最坏的情况下：。最坏的情况发生在我们想要按升序对列表进行排序，但它却按降序排列。
平均情况：。一般情况是列表按混乱的顺序排列。
最佳案例：。最好的情况发生在列表已按所需顺序排列时。回想一下我们对 n 个元素的列表进行排序的部分。我们需要执行 n – 1 次传递。对于每次传递，我们都需要运行一个循环来迭代列表。现在，由于 for 循环的复杂度为O(n)，并且我们使用两个嵌套的 for 循环，因此选择排序的时间复杂度可以解释为 –

(n – 1) * (( n – 2) + (n – 3) + (n – 4) +….1 )，这将等于 n * (n – 1)/2 。而且，用 Big-Oh 表示法来说，这将是。

2. 空间复杂度

选择排序算法的空间复杂度为O(1)。这是因为我们使用了固定数量的变量，除了循环变量和辅助变量（包括 temp、size 和 minIndex）之外，我们不需要任何额外的内存空间。这意味着我们甚至可以在不使用任何额外变量的情况下对包含一千个元素的数组进行排序。

选择排序算法的优点

选择排序可以有效地检查所有元素是否已排序。这意味着它可以快速确认排序列表。
它是一种就地排序算法。这意味着它直接在原始存储中对数据进行排序，而不需要额外的临时存储空间。当内存空间有限时，这使其成为一个不错的选择
选择排序很容易理解和实现。它的简单性使其成为小型数据集的不错选择。

选择排序应用

小列表：选择排序适用于小列表或数组，其中二次时间复杂度的低效率不是一个重要问题。
内存使用：在内存严重限制的环境中，选择排序可能是一个不错的选择，因为它是一种就地排序算法，这意味着它不需要额外的存储空间。
当交换成本高昂时：如果交换元素的成本很高（例如，处理大记录和小键时），选择排序会非常高效，因为它最大限度地减少了交换次数。
检查排序性：它可用于有利于快速确定列表是否已排序的场景，因为选择排序可以有效地执行此操作。

结论

选择排序可以很好地检查所有内容是否已经排序。
适合在内存空间有限时使用。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/919700