专栏首页陶士涵的菜地[Go] Golang练习项目-快速排序的GO语言实现

[Go] Golang练习项目-快速排序的GO语言实现

快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有很多种,所以快速排序具有很多版本。

总是选择第一个元素作为基准 pivot; 总是选择最后一个元素作为基准;(本文后续的实现就是依次为例) 随机的选择一个元素作为基准; 选择最中间的元素作为基准;

快速排序的关键是划分 partion() 。每一趟划分,我们就可以将作为 pivot 的值 x 放到排序数组的正确位置,并且将所有比 x 小的放到 x 的左边,所有比 x 大的元素放到 x 的右边。

package tools
//划分
func partition(arr *[]int,left int,right int)int{
	privot:=(*arr)[right]
	i:=left-1
	for j:=left;j<right;j++{
		if (*arr)[j]<privot{
			i++
			temp:=(*arr)[i]
			(*arr)[i]=(*arr)[j]
			(*arr)[j]=temp
		}
	}
	temp:=(*arr)[i+1]
	(*arr)[i+1]=(*arr)[right]
	(*arr)[right]=temp
	return i+1
}
//递归
func QuickSort(arr *[]int,left int,right int){
	if left>= right{
		return
	}
	privot:=partition(arr,left,right)
	QuickSort(arr,left,privot-1)
	QuickSort(arr,privot+1,right)
}  

测试用例:

package tools

import (
	"testing"
)

func TestQuickSort(t *testing.T) {
	arr:=[]int{1,8,3,9,4,5,4,7}
	t.Log(arr)
	QuickSort(&arr,0,len(arr)-1)
	t.Log(arr)
}

go test -v sorts_test.go sorts.go

文章转载自公众号(景寓)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [PHP] 算法-快速排序的PHP实现

    陶士涵
  • [PHP] 算法-把数组排成最小的数的PHP实现

    陶士涵
  • [Go] Golang练习项目-GO语言实现快速排序-第一个数作为基准更容易理解

    1. 第一个数作为基准数,找到所有比基准数小的放在左边 ,找所有比基准数大的放右边

    陶士涵
  • 排序算法之快速排序

    快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。

    dejavu1zz
  • 排序算法算法对比

    排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

    朱晓霞
  • Data Structure_Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • [PHP] 算法-快速排序的PHP实现

    陶士涵
  • 浙大版《C语言程序设计(第3版)》题目集 习题3-1 比较大小

    C you again 的博客
  • 常见排序算法及golang 实现

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有...

    程序员养成日记

扫码关注云+社区

领取腾讯云代金券