初级排序算法(选择,冒泡,插入,希尔)
===
### 选择排序
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)
}
~~~
