冒泡、插入、选择排序

下面我们来理一下时间复杂度为O（n^2）的排序算法：冒泡排序、插入排序和选择排序

冒泡排序

1. 在0～（N-1）的大小区间中，数组位置0和数组位置1上的进行比较，如果0位置上的大于1位置上的，交换他们的位置，否则不动；紧接着位置1上的和位置2上的进行比较，如果1位置上的大于2位置上的，交换他们的位置，如此反复第一轮下来，数组中最大的那个数会被放到数组的最后面。

2. 将0～（N-1）的区间缩小为0～（N-2），反复上述过程。第二轮下来后，最大的会被放到倒数第二个位置。

3. 以此类推完成后面各轮过程，直到数组区间大小为1，即整个过程结束。

图解流程访问下面链接中的Bubble Sort Data Structure Visualizations

package main

import "fmt"


func less(a int, b int) bool {
	return a<b
}

func exch(a *int, b *int){

	temp := *a
	*a = *b
	*b = temp
}

func bsort(a *[10]int){
	
	count := len(a)
	//fmt.Println(count)
	for i := 0; i < count; i++ {
		for j := i + 1; j < count; j++ {
			if less(a[j], a[i]) {
				exch(&(*a)[j],&(*a)[i])
			}
		}
	}
}

func main(){

	var a = [10]int{3,14,2232,4,54,62,351,422,123,34}
	fmt.Println(a)
	//fmt.Println(count)
	bsort(&a)
	fmt.Println(a)

}

插入排序

1. 数组0位置（a）和数组1位置（b）上的数进行比较，如果后者b比前者a小，将b与a交换位置，紧接着b再和数组-1上的位置进行比较，发现数组越越界，结束第一轮的过程。

2. 将待处理区间的大小缩小为1～（N-1），数组1位置上的数（a）与数组2位置上的数（b
   ）进行比较，同样的，如果后者b比前者a小，就将两个数进行交换，继续拿数组1位置上的数与数0位置上的数进行比较直到不满足后者小于前者，或者数组越界为止。结束第二轮的过程。

3. 反复上面的过程直到待比较区间大小为1停止整个插入排序。

图解流程访问下面链接中的Insertion Sort Data Structure Visualizations

public void sort(Comparable[] a){

    int len = a.length;
    for (int i =0 ; i < len ; i++){
        // 将a[i] 插入到 a[i - 1] , a[i - 2], a[ i - 3]
        for (int j = i ; j >= 1 && less(a[j],a[j-1]) ; j -= 1){
            exch(a,j,j-1);
        }
    }
}

选择排序

1. 在0～（N-1）的比较区间中，从头到尾依次比较找出最小的数，放在位置0上，将区间长度变为1～（N-1）

2. 在1～（N-1）的比较区间中，从头到尾依次比较找出最小的数，放在位置1上，将区间长度变为2～（N-1）

3. 反复上述过程知道比较区间大小为0，结束整个排序过程。

图解流程访问下面链接中的Selection Sort Data Structure Visualizations

public void sort(Comparable[] a){

        int len = a.length;

        for(int i = 0 ; i < len ; i++){
            int min = i;
            for (int j = i + 1 ; j < len  ; j++){
                if( less(a[j],a[min]) ) min = j;
            }
            exch (a,i,min);
        }
    }