go 递归tree关系_快排(golang实现) 递归方法

我会带着你远行 2023-01-01 05:53 151阅读 0赞

递归方法，逻辑简洁清晰。这个算法还是很重要的，需要重点记忆理解，面试经常考手写。据说是与傅里叶变换等并称“20世纪十大算法”。https://blog.csdn.net/v\_JULY\_v/article/details/6127953

快速排序算法的平均时间复杂度是 O(nlogn)，最坏情况时间复杂度是O(n^2)。

package main

import (

"fmt"

)

func main() \{

var arr = \[\]int\{9, 4, 7, 6, 8, 3, 2, 5, 1\}

fmt.Println("before", arr)

quickSort(arr, 0, len(arr)-1)

fmt.Println("after ", arr)

\}

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

\* \\author

\* \\date

\* \\brief 递归快排

\* \\param\[in\]arr：待排序切片 startIndex，endIndex：起始，结束索引

\* \\param\[out\]

\* \\return 输入返回值描述

\* \\ingroup 输入所属组

\* \\remarks

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

func quickSort(arr \[\]int, startIndex, endIndex int) \{

// 递归结束条件：startIndex大等于endIndex的时候

if startIndex >= endIndex \{

return

\}

// 得到基准元素位置

var pivotIndex = partition(arr, startIndex, endIndex)

// 根据基准元素，分成两部分递归排序(分治法)

quickSort(arr, startIndex, pivotIndex-1)

quickSort(arr, pivotIndex+1, endIndex)

return

\}

func partition(arr \[\]int, startIndex, endIndex int) int \{

// 取第一个位置的元素作为基准元素

var pivot = arr\[startIndex\]

var left = startIndex

var right = endIndex

for left != right \{

//控制right指针比较并左移

for left < right && arr\[right\] > pivot \{

right--

\}

//控制right指针比较并右移

for left < right && arr\[left\] <= pivot \{

left++

\}

//交换left和right指向的元素

if left < right \{

arr\[left\], arr\[right\] = arr\[right\], arr\[left\]

\}

\}

//pivot和指针重合点交换

arr\[left\], arr\[startIndex\] = arr\[startIndex\], arr\[left\]

return left

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关 go - 递归

递归递归请参考 [菜鸟教程 - go 递归][- go] 递归并不是我的重点，熟练函数的定义方式才是。如下这段函数的声明方式需要这样被理解：在Factori

逃离我推掉我的手/ 2023年01月07日 03:57/ 0 赞/ 159 阅读

相关 go 递归tree关系_快排(golang实现) 递归方法

递归方法，逻辑简洁清晰。这个算法还是很重要的，需要重点记忆理解，面试经常考手写。据说是与傅里叶变换等并称“20世纪十大算法”。https://blog.csdn.net/v\_

我会带着你远行/ 2023年01月01日 05:53/ 0 赞/ 152 阅读

相关快排的迭代，递归实现及其优化

快排的思想首先快排是一种比较排序。具体思想是选出一个基准值，通过比较找出待排序区间中基准值该放置的位置。实现逻辑：先从数列中取出一个数作为基准

男娘i/ 2022年12月06日 15:54/ 0 赞/ 151 阅读

相关 Data Structure--排序--顺序表(非递归快排) --队列(非递归快排)

非递归快排顺序表实现队列实现顺序表实现在这里利用顺序表实现快排需要包含顺序表对应的接口,具体: [点击此处][Link 1] //划

川长思鸟来/ 2022年11月03日 11:19/ 0 赞/ 179 阅读

相关 rust 双轴快排非递归

rust 双轴快排迭代法思路是用一个Vec当作栈来模拟保存快排的左右边界，思路来自这篇[文章][Link 1]，文章只有普通快排，我改成双轴的实现 partion 函

你的名字/ 2022年10月07日 00:51/ 0 赞/ 180 阅读

相关递归方法

//递归--方法本身自己调用自己，达到一种循环的效果，然后有一个出口,结束程序 public class Learn2 { //在方法中完成

逃离我推掉我的手/ 2022年06月04日 06:49/ 0 赞/ 196 阅读

相关递归算法(golang代码实现)

当一个函数用它自己来定义时就称为是递归的例：f(0)=0且f(x) = 2\f(x-1)+x\x 递归说白了，就是函数自己会调用自己以下用golang实现简单的递归方法

叁歲伎倆/ 2022年06月01日 13:29/ 0 赞/ 199 阅读

相关快排的递归与非递归实现

import java.util.; //快排的实现 public class quikSort{ //(1)递归实现快速排序

àì夳堔傛蜴生んèń/ 2022年05月28日 04:39/ 0 赞/ 213 阅读

相关 Java版快排（递归）

public class Test { private static int Partition(int[] arr, int start, int e

爱被打了一巴掌/ 2022年05月04日 23:54/ 0 赞/ 176 阅读

相关 go中递归

一递归的一个应用场景迷宫问题：A是入口，B是出口，怎样走。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_

水深无声/ 2021年07月24日 13:22/ 0 赞/ 405 阅读