提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

15分钟写不出快速排序的不考虑？！

2023-02-18 16:23:10 时间

快排思想：

快速排序首先选取一个数组元素作为基准（pivot），将小于pivot的放在左边，把大于pivot的放在右边，分割成两部分。再对其左右两部分进行排序。快排使用二分的思想将一个串分成两个子串，具体步骤如下：

  • 在数组中挑一个元素作为基准pivot；
  • 分区操作：将所有小于基准值的元素放到基准前面，所有大于基准值的元素放到后面，相同元素放到任一边。操作完成后，基准位于数列的中间位置；
  • 使用递归分别将小于基准和大于基准的子数组排序。

代码实现：

Python版 

def quick_sort(nums):
    n = len(nums)

    def patition(left, right):
        if left >= right:
            return nums  # 设置递归终止条件
        pivot = left  # 先将最左元素初始化为基准
        i = left
        j = right
        while i < j:
            while i < j and nums[j] > nums[pivot]:
                j -= 1  # 右侧指针向前移动遍历
            while i < j and nums[i] <= nums[pivot]:
                i += 1  # 左侧指针向后移动遍历
            nums[i], nums[j] = nums[j], nums[i]  # 指针指向的元素互换
        nums[pivot], nums[j] = nums[j], nums[pivot]  # 交换基准元素
        patition(left, j - 1)  # 递归基准左侧子串
        patition(j + 1, right)  # 递归基准右侧子串
        return nums
    return patition(0, n-1)


nums = [5, 4, 2, 3, 1]
print(quick_sort(nums))
# [1, 2, 3, 4, 5]

Golang版 

package main

import "fmt"

func quickSort(nums[]int) []int {
  if len(nums) < 2{  //如果数字长度小于2直接返回
    return nums
  }else {
    pivot := nums[0]  //将数组中第一个数初始化为基准
    var less []int
    var greater []int
    for _, value := range nums[1:]{ //从基准的下一位开始遍历
      if value <= pivot{
        less = append(less, value)  //存放比基准值小的半区
      } else {
        greater = append(greater, value)  //存放比基准值大的半区
      }
    }
    var res []int  //存放排序后的结果集
    res = append(res, quickSort(less)...)  
    res = append(res, pivot)
    res = append(res, quickSort(greater)...)
    return res
  }

}

func main()  {
  nums := []int{0, 9, 8, 4, 1, 6, 5}
  res := quickSort(nums)
  fmt.Println(res)
  //[0 1 4 5 6 8 9]
}

这里的 ‘...’ 是Golang的语法糖，如果不加三个点会有如下报错：

'...'有两种用法：

  • 第一种是为了解决图中的问题，将slice打散进行传递，即将quickSort处理后的结果元素打散后一个个append进res数组中，使代码更加简洁。
  • 第二种常用于函数有多个不定参数的情况，可以接受多个不确定数量的参数。
package main

import "fmt"

func test1(args ...string)  { //可以接受任意个string参数
  for _, v := range args{
    fmt.Println(v)
  }
}

func main() {
  var res = []string{
    "abc",
    "123",
    "jkl",
    "89ui",
  }
  test1(res...)
}

本例中如果不加'...'也会有“Cannot use 'res' (type []string) as the type string”这样的报错。

相关文章