排序算法

1. 快速排序（golang）

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

快速排序又称分区排序，其基本思路是：任取待排序记录序列中的某个记录 (例如取第一个记录) 作为基准, 按照该记录的关键字值的大小, 将整个记录序列划分为左右两个子序列：

1. 左侧子序列中所有记录的关键字值都小于或等于基准记录的关键字值；

2. 右侧子序列中所有记录的关键字值都大于基准记录的关键字值。

   
   
   

这是一个go语言实现快排算法。

package main
import (
    "fmt"
)
func partition(array []int, low, high int) int {
    key := array[low]
    for low < high {
        for low < high && array[high] >= key {
            high--
        }
        array[low] = array[high]
        for low < high && array[low] <= key {
            low++
        }
        array[high] = array[low]
    }
    array[low] = key
    return low
}

func qsort(array []int, low, high int) {
    if low < high {
        m := partition(array, low, high)
        qsort(array, low, m-1)
        qsort(array, m+1, high)
    }
}

func main() {
    var sortArray = []int{3, 41, 24, 1, 11, 45, 2, 3, 64, 21, 69, 19, 36}
    fmt.Println(sortArray, len(sortArray))
    qsort(sortArray, 0, len(sortArray)-1)
    fmt.Println(sortArray)

}
>>
[3 41 24 1 11 45 2 3 64 21 69 19 36] 13
[1 2 3 3 11 19 21 24 36 41 45 64 69]
>>

2. 冒泡排序（python）

起泡排序的基本思路是：设待排序记录序列中的记录个数为 n。最多作 n-1 趟起泡，i = 1, 2, ..., n-1。在第 i 趟中从后向前，j = n-1, n-2, ..., i，顺次两两比较V[j-1]和V[j]。如果发生逆序，即V[j-1]＞V[j]，则交换V[j-1]和V[j]

array=[3,15,8,2,16,3,25,1,87]
print("排序前：",array)
for i in range(len(array)-1):
    flag=0
    for j in range(len(array)-i-1):
        if array[j]>array[j+1]:
            array[j],array[j+1]=array[j+1],array[j]
            flag=1
    if flag==0:
        print("序列已经有序！")
        break
print("排序后：",array)
>>
排序前： [3, 15, 8, 2, 16, 3, 25, 1, 87]
序列已经有序！
排序后： [1, 2, 3, 3, 8, 15, 16, 25, 87]
>>

3. 选择排序

选择排序的基本思想是：每一趟（例如第 i 趟, i = 0, 1, …, n-2) 在后面 n-i 个待排序记录序列中选出关键字值最小的记录，作为有序记录序列的第 i 个记录。待到第 n-2 趟作完，待排序记录只剩下1 个, 就不用再选了

array=[3,15,8,2,16,3,25,1,87]
print("排序前：",array)
for i in range(len(array)-1):
    k=i
    for j in range(i+1,len(array)):
        if array[j]<array[k]:
            k=j
    if k!=i:
        array[i],array[k]=array[k],array[i]
print("排序后：",array)
>>
排序前： [3, 15, 8, 2, 16, 3, 25, 1, 87]
排序后： [1, 2, 3, 3, 8, 15, 16, 25, 87]
>>

4. 直接插入排序

基本方法是：每步将一个待排序的记录，按其关键字值的大小，插入到前面已经排好序的一组记录的适当位置上, 直到记录全部插入为止

array=[3,15,8,2,16,3,25,1,87]
print("排序前：",array)
for i in range(len(array)-1):
    t=array[i+1]
    for j in range(i,-2,-1):
        if array[j]>t:
            array[j+1]=array[j]
        else:
            break
    array[j+1]=t
print("排序后：",array)
>>
排序前： [3, 15, 8, 2, 16, 3, 25, 1, 87]
排序后： [1, 2, 3, 3, 8, 15, 16, 25, 87]
>>

5. 堆排序

def HeapSort(array):
    for i in range(int((len(array)-2)/2) ,-1,-1):
        siftdown(array,i,len(array))#调整为最大堆
    for i in range(len(array)-1,-1,-1):
        array[0],array[i]=array[i],array[0]
        siftdown(array,0,i)#将最大元素置于最后,其余再进行
                           #最大堆排序,使得第一个又为剩余元素中的最大值
                           #再将其置于倒数第二,依次循环则最终为最小堆,最上面最小 

def siftdown(array,start,end):
    i=start
    j=2*i+1
    t=array[i]
    while (j<end):
        if (j+1<end) and array[j+1]>array[j]:
            j=j+1
        if array[j]>t:
            array[i]=array[j]
            i=j
            j=i*2+1
        else:
            break
    array[i]=t
array=[3,15,8,2,16,3,25,1,87]
print("排序前：",array)
HeapSort(array)
print("排序后：",array)

使用堆排序选出序列中最大的5个值：

def top5(array):
    result=[]
    for j in range(5):
        result.append(array[j])
        HeapSort(result)#堆排序成最小堆，最上面为最小值
    for x in range(5,len(array)):
        if array[x]>result[0]:
            result[0]=array[x]
            HeapSort(result)
        else:
            continue
    return result

以上排序算法时间复杂度：

时间复杂度

shell排序：图解排序算法(二)之希尔排序

归并排序：图解排序算法(四)之归并排序