go语言插入排序递归,go自定义排序

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

Go语言如何给字符串排序

因为char *strings[]不是指针而是指针数组，那么

temp = strings[top];

strings[top] = strings[seek];

strings[seek] = temp;

这种交换交换的就是主调函数中的数组中的指针，把指向字符串的指针顺序改变了，当然按次序输出就达到排序目的了……

排序算法（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)

算法思想参考自：

插入排序（递归版本）时间复杂度问题

感觉insertion_sort退出有问题，当index=3时，insertion_sort执行，有一个while循环，会使得递归执行2,1的insertion_sort，而对应于2，又会执行1，所以不对。

可以把递归去掉，while index 1, insert(a, --index); 即可

非要递归，要检查退出条件

golang标准库之sort

标准库sort实现了4种排序方法， 插入排序 、 堆排序 、 快排 和 归并排序 ，但是并没有暴露给用户接口。sort包会根据数据选择最优的排序方法(其实只使用了3种， 归并排序 除外)。

用户需要实现以下接口才能使用sort包的排序功能。

对于常用的类型( 整型切片 、 float64切片 、 String切片 )，sort包提供了内置的接口实现

使用举例如下：

举例如下：

插入排序的递归算法

插入排序算法：

C版本的分析如下：

//直接插入排序：从小到大排；

//算法说明：

比如说现在排序进行到第

i位了，那么1

到

i-1位都已经为有序序列了；然后将

r[0]和r[j]依次比较，若是r[j]r[0],那么就依次用前边数据覆盖后边数据，不必担心r[i]会丢掉，因为它被保存在了r[0]中，直到找到满足r[i]r[j]的位置,将r[0]数据写入r[j]处，一次循环结束，进入下次循环；

void

insSort(

int

r[],int

length)

//传数组，和数组大小；

{

//

数组下标从1

开始，

0号位为监视哨；

int

i=0,j=0;

for(i=2;i=length;++i)

{

r[0]=r[i];

//总是用r[0]记录当前数据；

j=i-1;

while(r[0]r[j])

//寻找合适的位置；

{

r[j+1]=r[j];

//依次迭代覆盖；

j=j-1;

}

r[j+1]=r[0];

//晕，终于找到满足条件的地方了，赶紧钻入；

}

}

大功告成！

希望能帮上你。。。