使用插入排序以降序排列数组的 Swift 程序

在 Swift 中，插入排序是一种排序技术，其中给定的数组被虚拟地分成两个部分，即已排序部分和未排序部分。然后顺序搜索数组，比较未排序部分中的两个元素，并将它们移动到已排序部分的正确位置。使用插入排序，我们可以轻松地按升序或降序对数组元素进行排序。因此，在本文中，我们将学习如何使用插入排序以降序对数组进行排序。

插入排序的工作原理

给定未排序数组

要以降序对数组进行排序，请比较前两个元素 2 和 5。

这里 2 小于 5。因此，我们交换元素的位置。

现在再次比较元素 2 和 3。这里 2 小于 3，因此我们交换位置。

现在我们比较元素 5 和 3。这两个元素都处于正确的位置，因此我们现在移动到下一个元素。

再次比较元素 2 和 4，其中 2 小于 4，因此我们交换它们的位置。现在我们比较元素 3 和 4，这里 3 小于 4，因此我们交换它们的位置。

最后，我们得到以降序排序的数组。

算法

  • 步骤 1 − 创建一个以数组作为参数并返回已排序数组的函数。

  • 步骤 2 − 在函数内部创建原始数组的副本。

  • 步骤 3 − 使用 for-in 循环遍历从索引 1 到 n-1 的每个数组元素。

  • 步骤 4 − 然后运行一个 while 循环并比较当前元素与其前驱元素。

  • 步骤 5 − 如果已排序数组中的元素大于当前元素，则移动到下一个元素。否则将最小元素向右移动。

  • 步骤 6 − 将当前值插入结果数组。

  • 步骤 7 − 返回已排序数组。

  • 步骤 8 − 创建一个数组，调用函数并将其传递到其中。

  • 步骤 9 − 打印输出。

示例

在以下 Swift 程序中，我们将使用插入排序以降序对数组进行排序。为此，我们将创建一个数组，然后将其传递到函数中。然后函数创建原始数组的副本。然后它遍历数组的元素，从索引 1 开始，对于每个元素，它将把其值存储在 initialVal 中。然后它开始一个 while 循环，该循环将每个小于 initialVal 的元素向右移动一个位置。此循环将持续到 initialVal 中存在的元素小于 initialVal 为止。之后，函数将 initialVal 插入到已排序数组的正确位置，最后将返回已排序数组。

import Foundation
import Glibc

func sorting(arr:[Int]) -> [Int] {
   var resultantArray = arr
    
   for x in 1..<resultantArray.count{
      let initialVal = resultantArray[x]
      var y = x-1
        
      // Moving elements that are smaller than initialVal
      // one position on the right
      while y >= 0 && resultantArray[y] < initialVal{
         resultantArray[y+1] = resultantArray[y]
         y -= 1
      }
      resultantArray[y+1] = initialVal
   }
   return resultantArray
}

var mArr = [3, 1, 9, 4, 2, 10, 5]
var res = sorting(arr:mArr)

print(res)

输出

[10, 9, 5, 4, 3, 2, 1]

结论

这就是我们如何使用插入排序以降序对数组进行排序。插入排序是最简单的排序算法，但它仅适用于小型数据集。它不适用于较大的数据集。插入排序的最坏情况时间复杂度为 O(N2)，其余时间复杂度为 O(N)

更新于: 2023 年 5 月 10 日

867 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告