go语言实现快速排序,快速排序 golang

golang 写个快速排序

快速排序是大多数语言内置 sort 函数的默认实现方式，简单可分为两路排序和三路排序，我在相关资料中，发现两路排序也有多种实现方式。

我们提供的服务有：成都网站设计、网站建设、微信公众号开发、网站优化、网站认证、临高ssl等。为数千家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的临高网站制作公司

两路快排的逻辑

这个名词来自于 b 站的评论，这个快排思路很容易理解，非常适合入门

大体上和第一个版本差不多，但是函数更加简洁了，

这个版本是所有快速排序中，看起来比较难以理解，只有一个指针，从左到右滑动，设计非常巧妙。

这边测试了四种情况，中间值最优。

用了3个指针，表示小于，等于，大于三个部分，从而减少相等的数在其中来回交换。

由此可见快速排序是一种不稳定的排序，对于数据本身是有要求，对于 pivot 如何取也是有要求，属于经验取值了，如果对于源数据是逆序的情形，快排会退化成冒泡。

2021年03月18日22:24 更新

排序算法（go实现）

时间：

平均O(n 2 ) 　最差O(n 2 ) 　 最好O(n)

空间：

O(1)

它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

时间：

平均O(n 2 ) 　最差O(n 2 ) 　 最好O(n 2 )

空间：

O(1)

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

时间：

平均O(n 2 ) 　最差O(n 2 ) 　 最好O(n)

空间：

O(1)

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

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

我们可以通过双指针在O(n)的时间复杂度内获取合适的 j

我们设立两个指针 i 和 j，同时设置一个标志值 arr[low]，一般来说，标志值取数组第一个元素

上述算法结束之后，j 所在的位置即为我们寻找的 j

4.3 时间空间复杂度

时间：

平均O(nlog 2 n) 　最差O(n 2 ) 　 最好O(nlog 2 n)

空间：

O(1)

算法思想参考自：

Go语言基础语法（一）

本文介绍一些Go语言的基础语法。

先来看一个简单的go语言代码：

go语言的注释方法：

代码执行结果：

下面来进一步介绍go的基础语法。

go语言中格式化输出可以使用 fmt 和 log 这两个标准库，

常用方法：

示例代码：

执行结果：

更多格式化方法可以访问中的fmt包。

log包实现了简单的日志服务，也提供了一些格式化输出的方法。

执行结果：

下面来介绍一下go的数据类型

下表列出了go语言的数据类型：

int、float、bool、string、数组和struct属于值类型，这些类型的变量直接指向存在内存中的值；slice、map、chan、pointer等是引用类型，存储的是一个地址，这个地址存储最终的值。

常量是在程序编译时就确定下来的值，程序运行时无法改变。

执行结果：

执行结果：

Go 语言的运算符主要包括算术运算符、关系运算符、逻辑运算符、位运算符、赋值运算符以及指针相关运算符。

算术运算符：

关系运算符：

逻辑运算符：

位运算符：

赋值运算符：

指针相关运算符：

下面介绍一下go语言中的if语句和switch语句。另外还有一种控制语句叫select语句，通常与通道联用，这里不做介绍。

if语法格式如下：

if ... else ：

else if：

示例代码：

语法格式：

另外，添加 fallthrough 会强制执行后面的 case 语句，不管下一条case语句是否为true。

示例代码：

执行结果：

下面介绍几种循环语句：

执行结果：

执行结果：

也可以通过标记退出循环：

--THE END--

编写 快速排序的非递归算法

终于编写出来了，我写了两种，你看看：下面是代码：

/*非递归算法1

递归算法的开销很大，所以在下编了一个非递归的，算法描述如下：

A non-recursive version of quick sort using stack:

There are 2 stacks, namely one which stores the start of

a subarray and the other which stores the end of the

subarray.

STEP 1: while the subarray contains more than one element

,i.e. from Do {

SUBSTEP 1. pivot=Partion(subarray);

SUBSTEP 2. keep track of the right half of the current

subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo

SUBSTEP 3. go on to deal with the left half of

the current subarray i.e. to=pivot-1

}

STEP 2: if(neither of the stacks is empty)

Get a new subarray to deal with from the stacks.

i.e. start=pop(stackFrom); to=pop(stackTo);

STEP 3: both stacks are empty, and array has

been sorted. The program ends.

*/*/

void UnrecQuicksort(int q[],int low,int high)

{stack s1;br/stacks2;br/ s1.push(low);br/ s2.push(high);br/ int tl,th,p;br/ while(!s1.empty() !s2.empty())br/ {tl=s1.top();th=s2.top();br/ s1.pop();s2.pop();br/ if(tl=th) continue;br/ p=partition(q,tl,th);br/ s1.push(tl);s1.push(p+1);br/ s2.push(p-1);s2.push(th);br/ }

}

/*非递归算法2

要把递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最

多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n

，也就是说快速排序需要的附加存储开销为O（log2n）。

*/

void UnrecQuicksort2(int q[],int low,int high)

{int *a;br/ int top=0,i,j,p;br/ a=new int[high-low+1];br/ if(a==NULL) return;br/ a[top++]=low;br/ a[top++]=high;br/ while(top0)br/ {i=a[--top];br/ j=a[--top];br/ while(j {p=partition(q,j,i);br/ if(p-j {//先分割前部,后部进栈br/a[top++]=p+1;br/ a[top++]=i;br/ i=p-1;br/ }

else

{//先分割后部,前部进栈

a[top++]=j;

a[top++]=p-1;

j=p+1;

}

}

}

}

/*打印输出*/

void display(int p[],int len)

{for(int i=0;i cout}

/*测试*/

int _tmain(int argc, _TCHAR* argv[])

{int a[]={49,65,97,12,23,41,56,14};

quicksort(a,0,7);

//UnrecQuicksort(a,0,7);

//UnrecQuicksort2(a,0,7);

display(a,8);

return 0;

}

GO语言学习系列八——GO函数(func)的声明与使用

GO是编译性语言，所以函数的顺序是无关紧要的，为了方便阅读，建议入口函数 main 写在最前面，其余函数按照功能需要进行排列

GO的函数 不支持嵌套，重载和默认参数

GO的函数 支持 无需声明变量，可变长度，多返回值，匿名，闭包等

GO的函数用 func 来声明，且左大括号 { 不能另起一行

一个简单的示例：

输出为：

参数：可以传0个或多个值来供自己用

返回：通过用 return 来进行返回

输出为：

上面就是一个典型的多参数传递与多返回值

对例子的说明：

按值传递：是对某个变量进行复制，不能更改原变量的值

引用传递：相当于按指针传递，可以同时改变原来的值，并且消耗的内存会更少，只有4或8个字节的消耗

在上例中，返回值 (d int, e int, f int) { 是进行了命名，如果不想命名可以写成 (int,int,int){ ,返回的结果都是一样的，但要注意:

当返回了多个值，我们某些变量不想要，或实际用不到，我们可以使用 _ 来补位，例如上例的返回我们可以写成 d,_,f := test(a,b,c) ，我们不想要中间的返回值，可以以这种形式来舍弃掉

在参数后面以 变量 ... type 这种形式的，我们就要以判断出这是一个可变长度的参数

输出为：

在上例中， strs ...string 中， strs 的实际值是b,c,d,e,这就是一个最简单的传递可变长度的参数的例子，更多一些演变的形式，都非常类似

在GO中 defer 关键字非常重要，相当于面相对像中的析构函数，也就是在某个函数执行完成后，GO会自动这个；

如果在多层循环中函数里，都定义了 defer ,那么它的执行顺序是先进后出；

当某个函数出现严重错误时， defer 也会被调用

输出为

这是一个最简单的测试了，当然还有更复杂的调用，比如调试程序时，判断是哪个函数出了问题，完全可以根据 defer 打印出来的内容来进行判断，非常快速，这种留给你们去实现

一个函数在函数体内自己调用自己我们称之为递归函数，在做递归调用时，经常会将内存给占满，这是非常要注意的，常用的比如，快速排序就是用的递归调用

本篇重点介绍了GO函数(func)的声明与使用，下一篇将介绍GO的结构 struct