快速排序算法
快速排序是一种常用的排序算法，通过选择一个基准值，将数组分为左右两部分，然后对左右两部分分别进行递归排序，最终得到一个有序数组。
时间复杂度：
最好情况下，每次选择的基准值都能均匀地将数组分为两部分，此时时间复杂度为O(nlogn)。最坏情况下，每次选择的基准值都是当前最大或最小的元素，此时时间复杂度为O(n^2)。平均情况下，时间复杂度为O(nlogn)。
空间复杂度： 快速排序的空间复杂度主要取决于递归调用的栈空间，因此空间复杂度为O(logn)。
代码注释：
如果数组长度小于2，则直接返回数组本身。调用快速排序函数，传入数组指针、左边界和右边界。快速排序函数实现了快速排序的递归过程。partition函数采用三指针法来进行分区操作。随机选择一个基准值curr。初始化指针index和leftIndex为左边界。进入循环，比较当前元素与基准值的大小关系，并根据大小进行元素交换和指针移动。返回最终的左指针leftIndex和右指针rightIndex，作为下一次递归排序的边界。getRandomIntInclusive函数用于生成一个在[min, max]范围内的随机整数。
func main() {nums:=[]int{2,6,3,4,7,1,9,13,8}ansArr:=sortArray(nums)fmt.Println(ansArr)}func sortArray(nums []int) []int {if len(nums) < 2 {return nums}quickSort(&nums, 0, len(nums)-1) // 调用快速排序算法对数组进行排序return nums}func quickSort(nums *[]int, left int, right int) {if left >= right {return}leftIndex, rightIndex := partition(nums, left, right) // 划分数组并获取左右边界索引quickSort(nums, left, leftIndex-1) // 对左子数组进行递归快速排序quickSort(nums, rightIndex, right) // 对右子数组进行递归快速排序}func partition(nums *[]int, leftIndex int, rightIndex int) (int, int) {// 三指针法curr := (*nums)[getRandomIntInclusive(leftIndex, rightIndex)] // 随机选择基准元素index := leftIndex // 当前索引for index <= rightIndex {if (*nums)[index] < curr { // 如果当前元素小于基准元素(*nums)[leftIndex], (*nums)[index] = (*nums)[index], (*nums)[leftIndex] // 交换当前元素与左边界元素leftIndex++ // 左边界索引右移index++ // 当前索引右移continue // 进入下一次循环}if (*nums)[index] == curr { // 如果当前元素等于基准元素index++ // 当前索引右移continue // 进入下一次循环}if (*nums)[index] > curr { // 如果当前元素大于基准元素(*nums)[rightIndex], (*nums)[index] = (*nums)[index], (*nums)[rightIndex] // 交换当前元素与右边界元素rightIndex-- // 右边界索引左移}}return leftIndex, rightIndex // 返回左右边界索引}func getRandomIntInclusive(min int, max int) int {return min + rand.Intn(max-min+1) // 生成指定范围内的随机整数}
如果觉得《912. 升序排序数组》对你有帮助，请点赞、收藏，并留下你的观点哦！
