冒泡、插入、选择排序

下面我们来理一下时间复杂度为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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
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);
}
}