快速排序C++.docx

快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是采用分治法（Divide and Conquer）将一个大问题分解成若干个小问题来解决。在快速排序中，我们选择一个元素作为“基准”（pivot），然后将数组分为两部分：一部分的元素都小于或等于基准，另一部分的元素都大于基准。这个过程称为“划分”。接着，我们对这两部分再分别进行快速排序，直到所有元素都在正确的位置上。 在给出的C++代码中，快速排序的实现包括以下几个关键部分： 1. **交换元素**： `swap`函数用于交换数组中两个元素的位置。通过创建一个临时变量temp存储其中一个元素的值，然后交换两个指针指向的值，实现了元素的交换。 2. **划分数组**： `partition`函数是快速排序的核心。它接收一个数组、起始索引low和结束索引high，选择最后一个元素（arr[high]）作为基准。然后，遍历数组，将小于等于基准的元素移到数组的前面，大于基准的元素移到后面。基准元素会位于正确的位置，即所有小于它的元素之后，所有大于它的元素之前。函数返回基准元素的新位置。 3. **快速排序**： `quickSort`函数实现了快速排序算法。它首先检查low是否小于high，如果是，则调用`partition`函数划分数组，并对划分出的左右两个子数组递归调用`quickSort`进行排序。 4. **打印数组**： `printArray`函数用于在控制台输出数组的所有元素，方便查看排序前后的状态。 5. **主函数**： 在`main`函数中，我们定义了一个包含9个元素的整数数组arr，计算其大小，并调用`quickSort`对其进行排序。排序完成后，再次调用`printArray`打印排序后的数组，验证快速排序的效果。 快速排序的平均时间复杂度为O(n log n)，在最坏的情况下（例如，输入数组已经完全有序或完全无序）时间复杂度为O(n^2)。但由于快速排序在实际应用中的性能通常较好，且其常数因子较小，因此在许多情况下是首选的排序算法。此外，快速排序是原地排序算法，它只需要有限的额外空间，这也是其高效的一个重要原因。