排序算法

1. 冒泡排序

冒泡排序是一种非常容易遵循的算法。你需要遍历数组中的每个元素，以查看它是否更大，如果需要，则需要交换它们。你应该多次执行此任务，最终将不需要任何交换操作，也就是完成了排序。

package main
import "fmt"
func main() {
var n = []int{1, 39, 2, 9, 7, 54, 11}
var isDone = false
for !isDone {
isDone = true
var i = 0
for i < len(n) - 1 {
if n[i] > n[i + 1] {
var temp = n[i]
n[i] = n[i + 1]
n[i + 1] = temp
isDone = false
}
i++
}
}
fmt.Println(n)
}

2.插入排序

插入排序是一种著名的排序算法，其工作方式类似于对一副纸牌进行排序。当你遍历数组的各个元素时，可以将其移回正确的位置。

package main
import "fmt"
func main() {
var n = []int{1, 39, 2, 9, 7, 54, 11}
var i = 1
for i < len(n) {
var j = i
for j >= 1 && n[j] < n[j - 1] {
var temp = n[j]
n[j] = n[j - 1]
n[j - 1] = temp
j--
}
i++
}
fmt.Println(n)
}

3.选择排序

选择排序很有趣，但很简单。你需要做的就是简单地将迭代中的当前元素替换为右侧的最小值。这样左侧部分就是排好序的，然后不停的迭代选择，直达最后一个元素。

package main
import "fmt"
func main() {
var n = []int{1, 39, 2, 9, 7, 54, 11}
for i := 0; i < len(n);i++ {
var j = i + 1
var minIndex = i
for j < len(n) {
if n[j] < n[minIndex] {
minIndex = j
}
j++
}
if minIndex != i {
var temp = n[i]
n[i] = n[minIndex]
n[minIndex] = temp
}

}
fmt.Println(n)
}

4. 归并排序

归并排序是一种非常快速的排序算法。在归并排序中，实用的是分而治之的做法。首先，将递归的把数组对半分，直到最后达到1的长度，然后合并它们。要合并两个我们已经对其进行排序的数组，可以实现一个简单的函数，称为merge。

package main

import "fmt"

func merge(fp []int,sp []int) []int{
var n = make([]int, len(fp)+len(sp))
var fpIndex = 0
var spIndex = 0
var nIndex = 0
for fpIndex < len(fp) && spIndex < len(sp){
if fp[fpIndex] < sp[spIndex]{
n[nIndex] = fp[fpIndex]
fpIndex++
} else if sp[spIndex] < fp[fpIndex]{
n[nIndex] = sp[spIndex]
spIndex++
}
nIndex++
}

for fpIndex < len(fp){
n[nIndex] = fp[fpIndex]
fpIndex++
nIndex++
}

for spIndex < len(sp){
n[nIndex] = sp[spIndex]
spIndex++
nIndex++
}

return n
}

func mergeSort(arr []int) []int{
if len(arr) == 1{
return arr
}
var fp = mergeSort(arr[0 : len(arr)/2])
var sp = mergeSort(arr[len(arr)/2:])
return merge(fp,sp)
}

func main(){
var n = []int{1,39,2,9,7,54,11,8}
fmt.Println(mergeSort(n))
}

快速排序

1.基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.步骤

获得待排序数组a

选取一个合适的数字p(一般来说就选取数组或是子数组的第一个元素)作为排序基准

将待排序数组a中比基准p小的放在p的左边，比基准p大的放在p的右边

从第3步获得的两个子数组sub1跟sub2

判断sub1或sub2中是否只有一个元素，如果只有一个元素则返回此元素，否则就将sub1（或是sub2）代回到第1步中继续执行

3.实现

function quick_sort($arr) {
//先判断是否需要继续进行
$length = count($arr);
排序的终止条件
if($length <= 1) {
return $arr;
}
//如果没有返回，说明数组内的元素个数 多余1个，需要排序
//选择一个标尺
//选择第一个元素
$base_num = $arr[0];
//遍历 除了标尺外的所有元素，按照大小关系放入两个数组内
//初始化两个数组
$left_array = array();//小于标尺的
$right_array = array();//大于标尺的
for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
//放入左边数组
$left_array[] = $arr[$i];
} else {
//放入右边
$right_array[] = $arr[$i];
}
}
//再分别对 左边 和 右边的数组进行相同的排序处理方式
//递归调用这个函数,并记录结果
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
//合并左边 标尺 右边
return array_merge($left_array, array($base_num), $right_array);
}