go语言十大排序算法总结

选择排序

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。

选择排序是不稳定的。算法复杂度是O(n ^2 )。

package main

import (
    "fmt"
)

type SortInterface interface {
    sort()
}
type Sortor struct {
    name string
}

func main() {
    arry := []int{6, 1, 3, 5, 8, 4, 2, 0, 9, 7}
    learnsort := Sortor{name: "选择排序--从小到大--不稳定--n*n---"}
    learnsort.sort(arry)

    fmt.Println(learnsort.name, arry)
}

func (sorter Sortor) sort(arry []int) {
    arrylength := len(arry)
    for i := 0; i < arrylength; i++ {
        min := i
        for j := i + 1; j < arrylength; j++ {
            if arry[j] < arry[min] {
                min = j
            }
        }
        t := arry[i]
        arry[i] = arry[min]
        arry[min] = t

    }
}

输出为：

/usr/local/go/bin/go build -i [/Users/liuhanlin/GO/src/go_learn]
成功: 进程退出代码 0.
/Users/liuhanlin/GO/src/go_learn/go_learn  [/Users/liuhanlin/GO/src/go_learn]
选择排序--从小到大--不稳定--n*n--- [0 1 2 3 4 5 6 7 8 9]
成功: 进程退出代码 0.

冒泡排序
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
冒泡排序是稳定的。算法时间复杂度是O(n ^2)
class EbullitionSorter
{
public void Sort(int[] arr)
{
int i, j, temp;
bool done = false;
j = 1;
while ((j < arr.Length) && (!done))//判断长度
{
done = true;
for (i = 0; i < arr.Length - j; i++)
{
if (arr[i] > arr[i + 1])
{
done = false;
temp = arr[i];
arr[i] = arr[i + 1];//交换数据
arr[i + 1] = temp;
}
}
j++;
}
}
}

快速排序
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
class QuickSorter
{
private void swap(ref int l, ref int r)
{
int temp;
temp = l;
l = r;
r = temp;
}
public void Sort(int[] list, int low, int high)
{
int pivot;//存储分支点
int l, r;
int mid;
if (high <= low)
return;
else if (high == low + 1)
{
if (list[low] > list[high])
swap(ref list[low], ref list[high]);
return;
}
mid = (low + high) >> 1;
pivot = list[mid];
swap(ref list[low], ref list[mid]);
l = low + 1;
r = high;
do
{
while (l <= r && list[l] < pivot)
l++;
while (list[r] >= pivot)
r–;
if (l < r)
swap(ref list[l], ref list[r]);
} while (l < r);
list[low] = list[r];
list[r] = pivot;
if (low + 1 < r)
Sort(list, low, r - 1);
if (r + 1 < high)
Sort(list, r + 1, high);
}
}

插入排序
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
直接插入排序是稳定的。算法时间复杂度是O(n ^2) 。

public class InsertionSorter
{
public void Sort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int t = arr[i];
int j = i;
while ((j > 0) && (arr[j - 1] > t))
{
arr[j] = arr[j - 1];//交换顺序
–j;
}
arr[j] = t;
}
}
}

希尔排序
希尔排序基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2