使用快速排序算法对数组进行升序排序的 Swift 程序

Swift 中的快速排序算法是一种基于分治法的排序算法。在这种排序中，我们首先通过选择一个基准元素将数组划分为子数组。这里的划分方式是这样的：将最小的元素放置在基准元素的左侧，将最大的元素放置在基准元素的右侧。现在，使用相同的方法对左右子数组也进行划分。这个过程持续进行，直到所有子数组都只包含一个元素。此时，数组元素已排序，我们将其合并到一个数组中，并在输出中显示它们。因此，我们现在使用快速排序算法对数组进行升序排序。

算法

  • 步骤 1 − 创建一个函数，使用快速排序算法对数组进行升序排序。

  • 步骤 2 − 在函数内部，首先检查数组的长度。如果它包含 0 或 1 个元素，则返回已排序的数组。

  • 步骤 3 − 从给定数组的中间选择基准元素。

  • 步骤 4 − 筛选小于基准元素的元素

  • 步骤 5 − 筛选等于基准元素的元素

  • 步骤 6 − 筛选大于基准元素的元素

  • 步骤 7 − 现在递归地对子数组进行排序，并使用 + 运算符将它们连接到单个数组中。

  • 步骤 8 − 调用函数并将数组传递给它。

  • 步骤 9 − 打印已排序的数组。

示例

在以下示例中，我们将创建一个名为 quickSortAlgo() 的函数。此函数将数组作为输入，并借助快速排序算法将给定数组排序为升序。然后，我们首先从数组中选择中间元素作为基准元素。然后将数组划分为三个子数组，包含以下元素：小于基准元素的元素、大于基准元素的元素以及等于基准元素的元素。现在，我们递归地将快速排序应用于 lessEle 和 greaterEle，然后使用 + 运算符连接所有已排序的子数组，最后以降序显示已排序的数组。

import Foundation
import Glibc

// Function to sort the array in ascending order using quick sort 
func quickSortAlgo(arr: [Int]) -> [Int] {

   // Array is already sorted if it has 0 or 1 elements
   guard arr.count > 1 else { return arr } 
    
   // Select a pivot element in the middle
   let pivotEle = arr[arr.count/2] 
    
   // Filter the elements that are less than the pivot
   let lessEle = arr.filter { $0 < pivotEle } 
    
   // Filter the elements that are equal to the pivot element
   let equalEle = arr.filter { $0 == pivotEle } 
    
   // Filter the elements that are greater than the pivot element
   let greaterEle = arr.filter { $0 > pivotEle } 
    
   // Now recursively sort the sub-arrays and concatenate them into the single array
   return quickSortAlgo(arr: lessEle) + equalEle + quickSortAlgo(arr: greaterEle) 
}

let arr = [3, 6, 1, 8, 1, 56, 23, 12, 5]
let resultantArr = quickSortAlgo(arr: arr)
print("Sorted Array:", resultantArr)

输出

Sorted Array: [1, 1, 3, 5, 6, 8, 12, 23, 56]

结论

因此，这就是我们如何使用快速排序算法对数组进行升序排序。在这里，我们使用 filter(_:) 方法来实现快速排序，但您也可以使用其他方法。快速排序由于其分治法而轻松地解决了问题，但它具有最坏情况下的时间复杂度，即 O(n2)。它适用于大型数据集，但对于小型数据集来说不是一个好的选择。

更新于: 2023年4月24日

552 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告