golang算法练习：排序

r囧r小猫 2021-11-29 19:24 283阅读 0赞

## 需求 ##

排序操作，列举常见的几种排序模型:冒泡、选择、插入、快排

备注：需求和运行输出结果均已在代码中注释

#### 冒泡 ####

代码：

package main
    
    import "fmt"
    
    /* 思路： 从第一个元素开始循环，与其相邻的元素两两比较，若左边元素大于右边元素，则两者互换位置，保持右边的元素比左边元素大的排序原则 分两层循环，外层循环的成员是所有元素，内层循环是成员右边的元素 */
    
    func main() { 
    	arr := [7]int{ 9, 11, 4, 7, 15, 12, 6}
    	fmt.Println("排序前:", arr)
    	for i := 0; i < len(arr); i++ { 
    		for j := i + 1; j < len(arr); j++ { 
    			if arr[i] > arr[j] { 
    				arr[i], arr[j] = arr[j], arr[i]
    			}
    		}
    	}
    	fmt.Println("排序后:", arr)
    }

#### 选择 ####

代码:

package main
    
    import (
    	"fmt"
    )
    
    /* 思路： 假设arr有n个元素 第1次循环，从第0位元素开始，依次与arr[1..n-1]元素进行比较，取出最小的元素，与arr[0]的位置互相交换 第2次循环，从第1位元素开始，依次与arr[2..n-1]元素进行比较，取出最小的元素，与arr[1]的位置互相交换 . . 第n-1次循环，就剩最后2个元素arr[n-2, n-1]，n-2位元素与arr[n-1]元素进行比较，取出最小的元素，与arr[n-2]的位置互相交换 剩下最后一个元素，就是最大的元素，循环结束。 核心思想：每次循环确定一个小元素的位置，n个元素，外层循环n-1次 */
    
    func main() { 
    	arr := [7]int{ 9, 11, 4, 7, 15, 12, 6}
    	for i := 0; i < len(arr); i++ { 
    		minIndex := i
    		for j := i + 1; j < len(arr); j++ { 
    			if arr[j] < arr[minIndex] { 
    				minIndex = j
    			}
    		}
    		arr[i], arr[minIndex] = arr[minIndex], arr[i]
    	}
    	fmt.Println("排序后:", arr)
    }

#### 插入 ####

代码：

package main
    
    import "fmt"
    
    /* 思路： 假设arr有n个元素，无序的， 新建一个newArr数组，这个数组要求有序(假设从小至大)，默认只放入arr[0]这一个元素，arr后面的元素，依次比较，按照合理的位置插入newArr数组中 最后组合成新的完整有序的newArr */
    
    func main() { 
    	arr := [7]int{ 9, 11, 4, 7, 15, 12, 6}
    	newArr := [7]int{ }
    	newArr[0] = arr[0]
    	/* newArr首位元素与arr首元素相等无需比较，因此arr从第1位开始取出元素与newArr中所有的进行比较，即arr[i]中的元素,与newArr[0..i-1] 进行倒序逐个比较，arr[i]大则插入比较元素newArr[j]的右边，arr[i]小则继续向左移动。在选择插入合适位置时，如果插入之后再来移动其右 边的元素，复杂度高，因此： 1.若比较元素newArr[j] > arr[i]大，则提前将j的下一位newArr[j+1]赋值成newArr[j]，相当于变相地将newArr[j]往后移动一位，给前方提前预留一个位置出来，合适的时候给arr[i]插入 2.若newArr[j] < arr[i]，则说明arr[i]已经找到了合适的位置，即j的下一位newArr[j+1]，将newArr[j+1]赋值为arr[i],本次循环完成,进入下一次循环 */
    	for i := 1; i < len(arr); i++ { 
    		for j := i - 1; j >= 0; j-- { 
    			if arr[i] < newArr[j] { 
    				newArr[j+1] = newArr[j]
    				// 如果是arr[i]比newArr[0]还小，则arr[i]成为新的newArr[0]
    				if j == 0 { 
    					newArr[0] = arr[i]
    				}
    			} else { 
    				newArr[j+1] = arr[i]
    				break
    			}
    		}
    	}
    	fmt.Println(newArr)
    }

#### 快排1 ####

package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    func QuickSort(left int, right int, array *[8000000]int) { 
    	/* params: ;left: 左下标 ;right: 右下表 ;array: 无序数组 思路总结: 1.在数组内部进行顺序调换，这一点与冒泡的思路一致 2.选取位于中间位置的元素作为一个中间值进行比较，找到一个大于它的元素和一个小于它的元素，两个进行位置交换 3.左右双方向递归，保证数组内的每个元素都能找到比自身大和比自身小的元素，进行位置互换。这样，每个元素都出现在它合适的位置(即保证左边比 小，右边比自身大，也就完成了排序) */
    
    	l := left
    	r := right
    	// pivot 是中轴， 支点
    	pivot := array[(left+right)/2]
    	temp := 0
    
    	//for 循环的目标是将比 pivot 小的数放到 左边
    	// 比 pivot 大的数放到 右边
    	for l < r { 
    		//从 pivot 的左边找到大于等于pivot的值
    		for array[l] < pivot { 
    			l++
    		}
    		//从 pivot 的右边边找到小于等于pivot的值
    		for array[r] > pivot { 
    			r--
    		}
    		// 1 >= r 表明本次分解任务完成, break
    		if l >= r { 
    			break
    		}
    		//交换
    		temp = array[l]
    		array[l] = array[r]
    		array[r] = temp
    		//优化
    		if array[l] == pivot { 
    			r--
    		}
    		if array[r] == pivot { 
    			l++
    		}
    	}
    	// 如果 1== r, 再移动下
    	if l == r { 
    		l++
    		r--
    	}
    	// 分为两段，向左递归
    	if left < r { 
    		QuickSort(left, r, array)
    	}
    	// 分为两段，向右递归
    	if right > l { 
    		QuickSort(l, right, array)
    	}
    }
    
    func main() { 
    
    	// arr := [9]int {-9,78,0,23,-567,70, 123, 90, -23}
    	// fmt.Println("初始", arr)
    
    	var arr [8000000]int
    	for i := 0; i < 8000000; i++ { 
    		arr[i] = rand.Intn(900000)
    	}
    
    	//fmt.Println(arr)
    	start := time.Now()
    	//调用快速排序
    	QuickSort(0, len(arr)-1, &arr)
    	end := time.Since(start).Seconds()
    	fmt.Println("main..")
    	fmt.Printf("快速排序法耗时%f秒", end) // 快速排序法耗时1.279648秒
    	//fmt.Println(arr)
    
    }

#### 快排2 ####

package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    func sort(arr, orderArr []int) (subOrderArr []int) { 
    	/* params: ;arr: 无序数组 ;orderArr: 有序数组 思路总结: 1.创建一个默认的无序数组arr，一个空的有序数组orderArr，作为参数传给递归函数体 2.每次选取一个无序数组中的元素，作为参照的中间值，小于它的放到一个临时无序数组(leftSlice)，大于它的也放到一个临时无序数组(rightSlice) 3.将新的无序数组(leftSlice/rightSlice)和现有的有序数组作为参数，递归传递给函数体本身。递归打破的条件是临时无序数组为空或只有 1个元素，就说明本次递归中的无序数组无需再对比了，拼接入现有的orderArr中，同一递归层级内，拼接顺序永远保持:左侧+中间值+右侧，拼接完成 后返回给递归上一级，进入下一步。 4.用递归思想将数组分割成多个以两个值为一组的单位，进行单位内部的比较，再串成一个完整的数组。递归最内层，就是值最小的一组组合。 Tips: 递归函数编写思路: 1.需要提取出共同的参数条件，递归函数执行条件，递归打破条件 2.若变量在递归过程需要作为参数被继承且反复使用，则一定要将该参数同时作为返回值返回，并在递归栈的上一层接收返回值重新给变 量赋值，否则回到上一层递归后，该变量的变化不会生效。 */
    
    	//fmt.Println("递归前", orderArr)
    	midValue := arr[0]
    
    	var leftSlice []int
    	var rightSlice []int
    	for _, i := range arr { 
    		if i < midValue { 
    			leftSlice = append(leftSlice, i)
    		}
    		if i > midValue { 
    			rightSlice = append(rightSlice, i)
    		}
    	}
    	//fmt.Println("中间值:", midValue, "leftSlice:", leftSlice, "rightSlice:", rightSlice)
    	if len(leftSlice) > 1 { 
    		//fmt.Println("进入左侧递归")
    		orderArr = sort(leftSlice, orderArr)
    	} else { 
    		// 当无序数组元素数量为0或1时，直接合并它
    		orderArr = append(orderArr, leftSlice...)
    		//fmt.Println("本次递归左侧最小:", leftSlice[0], "已加入有序数组", orderArr)
    	}
    
    	orderArr = append(orderArr, midValue)
    	//fmt.Println("加入中间值:", midValue, orderArr)
    
    	if len(rightSlice) > 1 { 
    		//fmt.Println("进入右侧递归")
    		orderArr = sort(rightSlice, orderArr)
    	} else { 
    		// 当无序数组元素数量为0或1时，直接合并它
    		orderArr = append(orderArr, rightSlice...)
    		//fmt.Println("本次递归右侧最小:", rightSlice[0], "已加入有序数组", orderArr)
    	}
    
    	//fmt.Println("递归后:", orderArr)
    	return orderArr
    }
    
    func main() { 
    	arr := make([]int, 8000000)
    	for i := 0; i < 8000000; i++ { 
    		tmp := rand.Intn(900000)
    		arr = append(arr, tmp)
    	}
    
    	orderArr := make([]int, len(arr))
    	start := time.Now()
    	orderArr = sort(arr, orderArr)
    	//fmt.Println(orderArr)
    	end := time.Since(start).Seconds()
    	fmt.Printf("快速排序法耗时%f秒", end) // 快速排序法耗时2.116863秒
    }

### 总结 ###

时间复杂度对比:  
冒泡:O(n^2)  
选择:O(n^2)  
插入:O(n^2)  
快排:O(nlogn)

冒泡和选择排序复杂度基本一致，插入排序在最差情况下复杂度与前两者一致，但平均复杂度低于前两者，快排要快上不少，基于快排1稍稍改动了一下思路，实现的快排2，思路方面个人认为快排2更便于理解，同时更贴近递归的深度优先理念，深入到最内层先找到最小的元素。