C++实现的快速排序算法

"这篇资源是关于使用C++实现快速排序算法的一个简单示例，已通过编译并可以正常运行。程序包含主函数main、Partition函数和QuickSort函数，用于完成数组的输入、排序以及输出过程。" 快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是采用分治法，通过选取一个基准值（pivot），将待排序的数组分为两部分，一部分的所有元素都小于或等于基准值，另一部分的所有元素都大于基准值。然后对这两部分再分别进行快速排序，直到所有元素都有序。 在这个C++代码中，快速排序的实现主要包含以下几个关键部分： 1. `main`函数：这是程序的入口点，首先定义了一个大小为5的整型数组`a`，然后从用户处获取输入以填充数组。调用`QuickSort`函数对数组进行排序，最后输出排序后的结果。 2. `Partition`函数：这是快速排序的核心，它接收一个数组`a`，以及两个下标`p`和`r`，表示需要处理的子数组范围。函数内部使用双指针技术，`i`从`p`向右移动，`j`从`r`向左移动，当`i`找到第一个大于或等于基准值的元素，`j`找到第一个小于或等于基准值的元素时，交换这两个位置的元素。这个过程会持续到`i`和`j`相遇，此时基准值被放在了正确的位置，返回`j`作为新的分区点。 3. `QuickSort`函数：这是一个递归函数，接收数组`a`、起始下标`p`和结束下标`r`。如果`p`小于`r`，则先调用`Partition`函数确定分区点`q`，然后分别对`p`到`q-1`和`q+1`到`r`的子数组进行递归调用`QuickSort`，实现整个数组的排序。 快速排序的时间复杂度平均为O(n log n)，在最坏情况下（输入数组已经完全有序或逆序）为O(n^2)，但这种情况在实际应用中很少出现。空间复杂度主要取决于递归调用的深度，通常为O(log n)。由于其效率高且易于实现，快速排序在实际编程中被广泛使用。