初級排序算法(選擇,冒泡,插入,希爾)
===
### 選擇排序
1. 找到數組中最小的那個元素
2. 將它和數組第一個元素交換位置(如果第一個元素就是最小元素,那末它就和自己交換)
3. 在剩下的元素中找到最小的元素,將它與數組的第二個元素交換位置
4. 如此往復,直到整個數組排序完成
- 運行時間和輸入無關
- 數據移動是最少的
- 時間復雜度O(n^2)
- 空間復雜度O(1)
~~~
func TestOne(t *testing.T) {
rand.Seed(time.Now().UnixNano())
data := []int{}
for i:=0;i<10;i++{
intn := rand.Intn(999)
data = append(data, intn)
}
fmt.Println(data)
len := len(data)
//end := len - 1
s := 0
for s<len{
min := data[s]
st := s
for ;st<len;st++{
if data[st] < min {
min,data[st] = data[st],min
}
}
data[s] = min
s += 1 // 每移動一遍 就向前推動一格
}
fmt.Println(data)
}
~~~
### 冒泡排序
1. 比較相鄰的元素.如果第一個比第二個大,就交換他們兩個
2. 對每一個相鄰元素作同樣的工作,從開始第一對到結尾最后一對.這步作完后,最后的元素會是最大的數
3. 針對所有元素重復以上步驟,除了最后一個
4. 持續每次對越少的元素重復上面的步驟,直到沒有任何一對數字需要比較
~~~
func main() {
data := make([]int,10)
rand.Seed(time.Now().UnixNano())
for i:=range data{
data[i] = rand.Intn(999)
}
fmt.Println(data)
Asort(data)
}
func Asort(data []int) {
for i:=range data{
for j:=1;j<len(data)-i;j++{
if data[j] < data[j-1] {
data[j],data[j-1] = data[j-1],data[j]
}
}
}
fmt.Println(data)
}
~~~
### 插入排序
1. 從第一個元素開始,該元素可以認為已經被排序
2. 取出下一個元素,在已經排序的元素序列中,從后向前掃描
3. 如果該元素(已排序)大于新元素,將該元素移到下一位置
4. 重復步驟三,直到找到以排序的元素下雨或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復步驟2~5
~~~
func TestCRPX(t *testing.T) {
data := make([]int,10)
rand.Seed(time.Now().UnixNano())
for i:=range data{
data[i] = rand.Intn(999)
}
fmt.Println(data)
// 插入排序
for i:=range data {
for j:=i;j>0;j--{
if data[j]<data[j-1] {
data[j],data[j-1] = data[j-1],data[j]
}
}
}
fmt.Println(data)
}
~~~
