冒泡排序：
时间复杂度：O(n^2)
稳定性：稳定
<code>//希尔排序//按间隔分组，每组进行插入排序//长度为10，间隔为10/2=5，按(0,5)(1,6)(2,7)(3,8)(4,9)分组//间隔减小为5/2=2，按(0,2,4,6,8)(1,3,5,7,9)分组//组内插入排序时，各组之间交替比较，以间隔为2举例：先比较0和2，再比较1和3，再比较4，再比较5，依次遍历//直到间隔为1，按(0,1...9)分组func shellSsort(arr []int) { length := len(arr) //按间隔分组 for gap := length / 2; gap > 0; gap /= 2 { //当前各个分组进行插入排序 for i := gap; i < length; i++ { if arr[i] < arr[i-gap] { temp := arr[i] j := i - gap for ; j >= 0 && temp < arr[j]; j -= gap { arr[j+gap] = arr[j] } arr[j+gap] = temp } } }}/<code>简单选择排序：
时间复杂度：O(n^2)
稳定性：不稳定
<code>//归并排序//将两个有序序列合并成一个有序序列//取中间值分左右递归处理func mergeSort(r []int) []int { length := len(r) if length <= 1 { return r } //左右分别处理 num := length / 2 left := mergeSort(r[:num]) right := mergeSort(r[num:]) //左右两边都为有序，进行合并 return merge(left, right)}func merge(left, right []int) (result []int) { l, r := 0, 0 //left或right有一方遍历完则退出循环 for l < len(left) && r < len(right) { if left[l] < right[r] { result = append(result, left[l]) l++ } else { result = append(result, right[r]) r++ } } //left和right均为有序，直接将剩余部分加进序列 //如果上面是left遍历完，left[l:]为[]，right还有剩余值 //如果上面是right遍历完，right[r:]为[], left还有剩余值 result = append(result, left[l:]...) result = append(result, right[r:]...) return}/<code> 直接插入排序：
时间复杂度：O(n^2)
稳定性：稳定
<code>//快速排序//取首位元素为临界值，一遍循环，临界值左边为小数，右边为大数//递归临界值左边和右边func quickSort(arr []int) { length := len(arr) if length <= 1 { return } quick(arr, 0, length-1)}func quick(arr []int, start, end int) { if start >= end { return } i, j := start, end //取首位元素为分界值 temp := arr[i] for i < j { //从右往左找，大的不处理，j-- for i < j && arr[j] >= temp { j-- } //直到遇见第一个小的，跳出上面循环 if i < j { //把小的给i，temp的值没发生变化 arr[i] = arr[j] i++ } //从左往右找，小的不处理，i++ for i < j && arr[i] <= temp { i++ } //直到遇见第一个大的，跳出上面循环 if i < j { //把大的给j，temp的值没发生变化 arr[j] = arr[i] j-- } } //把temp给到i位置 arr[i] = temp //递归i的左边，0到i-1 quick(arr, start, i-1) //递归i的右边，i+1到right quick(arr, i+1, end)}/<code>希尔排序：
时间复杂度：O(n^1.5)
稳定性：不稳定
<code>//堆排序//升序使用大顶堆，降序使用小顶堆，以大顶堆为例//顶堆是上下比较大小，父结点与其孩子比较，同一父结点的左右大小无限制，二叉搜索树是左右比较大小，不要搞混//先调整序列为大顶堆(序列默认是一棵二叉树，把该二叉树调整为大顶堆)//处理大顶堆：首尾交换，末位最大，去掉末位，调整剩下序列为大顶堆，循环处理func heapSort(arr []int) []int { length := len(arr) //调整序列为大顶堆 for i := length/2 - 1; i >= 0; i-- { //从最后一个非叶子结点开始，从右往左，从下往上，length/2-1为最后一个非叶子结点 adjustHeap(arr, i, length) } //处理大顶堆 //大顶堆左右无序，上下有序 for i := length - 1; i > 0; i-- { //首位最大，首尾交换，把最大放在队尾 arr[0], arr[i] = arr[i], arr[0] //去掉队尾最大元素，所以队列长度length-1，即为i，把剩余i个元素调整为大顶堆 //此时只有刚交换的首位不符合大顶堆条件，没必要像上面循环所有非叶子结点，只需从首位开始调整，所以i=0 adjustHeap(arr, 0, i) } return arr}//调整二叉树为大顶堆func adjustHeap(arr []int, i, length int) { //非叶子结点i的左右孩子 left := 2*i + 1 right := 2*i + 2 //默认i为最大 max := i //存在左孩子且左孩子大，最大指向left，因为右孩子可能更大，所以暂不交换 if left < length && arr[left] > arr[max] { max = left } //存在右孩子且右孩子更大，最大指向right if right < length && arr[right] > arr[max] { max = right } //最大发生过改变，交换 if max != i { arr[i], arr[max] = arr[max], arr[i] //最后一层非叶子结点，递归时不发生交换操作； //假如二叉树深度为4，最后一层非叶子结点为第三层，处理第二层发生交换时，需要递归处理第三层是否被影响了 adjustHeap(arr, max, length) }}/<code> 归并排序：
时间复杂度：O(nlogn)
稳定性：稳定
<code>//基数排序//分配式排序，桶子法，非负数，共0-9，10个桶子//首次循环根据元素个位数，将元素分配至对应桶子里，0进0号桶，9进9号桶//按桶子排序，再次循环，根据元素十位数再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位数 d := maxBit(arr) //用mod和dev求对应位数上的数值 mod, dev := 10, 1 //循环位数 for i := 0; i < d; i++ { //10个桶子 temp := [10][]int{} //遍历序列 for j := 0; j < length; j++ { //先求余，再求商 //个位数值：x%10/1；十位数值：x%100/10 bucket := arr[j] % mod / dev //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //为arr排序时的下标 k := 0 //排序arr for m := 0; m < 10; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //为下一位做准备 mod *= 10 dev *= 10 }}//基数排序//分配式排序，桶子法，存在负数，共0-19，20个桶子//首次循环根据元素个位数，将元素分配至对应桶子里，-9进1号桶，-1进9号桶，0进10号桶，1进11号桶，19进19号桶//按桶子排序，再次循环，根据元素十位数再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位数 d := maxBit(arr) //用mod和dev求对应位数上的数值 mod, dev := 10, 1 //循环位数 for i := 0; i < d; i++ { //10个桶子 temp := [20][]int{} //遍历序列 for j := 0; j < length; j++ { //先求余，再求商，下标不为负，+10保证为非负数 //个位数值：x%10/1+10；十位数值：x%100/10+10 bucket := (arr[j] % mod / dev)+10 //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //为arr排序时的下标 k := 0 //排序arr for m := 0; m < 20; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //为下一位做准备 mod *= 10 dev *= 10 }}//元素的最大位数func maxBit(arr []int) int { length := len(arr) d := 1 p := 10 for i := 0; i < length; i++ { for arr[i] >= p { d++ p *= 10 } } return d}/<code>快速排序：
时间复杂度：O(nlogn)
稳定性：不稳定
<code>//快速排序//取首位元素为临界值，一遍循环，临界值左边为小数，右边为大数//递归临界值左边和右边func quickSort(arr []int) { length := len(arr) if length <= 1 { return } quick(arr, 0, length-1)}func quick(arr []int, start, end int) { if start >= end { return } i, j := start, end //取首位元素为分界值 temp := arr[i] for i < j { //从右往左找，大的不处理，j-- for i < j && arr[j] >= temp { j-- } //直到遇见第一个小的，跳出上面循环 if i < j { //把小的给i，temp的值没发生变化 arr[i] = arr[j] i++ } //从左往右找，小的不处理，i++ for i < j && arr[i] <= temp { i++ } //直到遇见第一个大的，跳出上面循环 if i < j { //把大的给j，temp的值没发生变化 arr[j] = arr[i] j-- } } //把temp给到i位置 arr[i] = temp //递归i的左边，0到i-1 quick(arr, start, i-1) //递归i的右边，i+1到right quick(arr, i+1, end)}/<code>堆排序：
时间复杂度：O(nlogn)
稳定性：不稳定
<code>//堆排序//升序使用大顶堆，降序使用小顶堆，以大顶堆为例//顶堆是上下比较大小，父结点与其孩子比较，同一父结点的左右大小无限制，二叉搜索树是左右比较大小，不要搞混//先调整序列为大顶堆(序列默认是一棵二叉树，把该二叉树调整为大顶堆)//处理大顶堆：首尾交换，末位最大，去掉末位，调整剩下序列为大顶堆，循环处理func heapSort(arr []int) []int { length := len(arr) //调整序列为大顶堆 for i := length/2 - 1; i >= 0; i-- { //从最后一个非叶子结点开始，从右往左，从下往上，length/2-1为最后一个非叶子结点 adjustHeap(arr, i, length) } //处理大顶堆 //大顶堆左右无序，上下有序 for i := length - 1; i > 0; i-- { //首位最大，首尾交换，把最大放在队尾 arr[0], arr[i] = arr[i], arr[0] //去掉队尾最大元素，所以队列长度length-1，即为i，把剩余i个元素调整为大顶堆 //此时只有刚交换的首位不符合大顶堆条件，没必要像上面循环所有非叶子结点，只需从首位开始调整，所以i=0 adjustHeap(arr, 0, i) } return arr}//调整二叉树为大顶堆func adjustHeap(arr []int, i, length int) { //非叶子结点i的左右孩子 left := 2*i + 1 right := 2*i + 2 //默认i为最大 max := i //存在左孩子且左孩子大，最大指向left，因为右孩子可能更大，所以暂不交换 if left < length && arr[left] > arr[max] { max = left } //存在右孩子且右孩子更大，最大指向right if right < length && arr[right] > arr[max] { max = right } //最大发生过改变，交换 if max != i { arr[i], arr[max] = arr[max], arr[i] //最后一层非叶子结点，递归时不发生交换操作； //假如二叉树深度为4，最后一层非叶子结点为第三层，处理第二层发生交换时，需要递归处理第三层是否被影响了 adjustHeap(arr, max, length) }}/<code> 基数排序：
时间复杂度：O(d(n+r))
稳定性：稳定
<code>//基数排序//分配式排序，桶子法，非负数，共0-9，10个桶子//首次循环根据元素个位数，将元素分配至对应桶子里，0进0号桶，9进9号桶//按桶子排序，再次循环，根据元素十位数再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位数 d := maxBit(arr) //用mod和dev求对应位数上的数值 mod, dev := 10, 1 //循环位数 for i := 0; i < d; i++ { //10个桶子 temp := [10][]int{} //遍历序列 for j := 0; j < length; j++ { //先求余，再求商 //个位数值：x%10/1；十位数值：x%100/10 bucket := arr[j] % mod / dev //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //为arr排序时的下标 k := 0 //排序arr for m := 0; m < 10; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //为下一位做准备 mod *= 10 dev *= 10 }}//基数排序//分配式排序，桶子法，存在负数，共0-19，20个桶子//首次循环根据元素个位数，将元素分配至对应桶子里，-9进1号桶，-1进9号桶，0进10号桶，1进11号桶，19进19号桶//按桶子排序，再次循环，根据元素十位数再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位数 d := maxBit(arr) //用mod和dev求对应位数上的数值 mod, dev := 10, 1 //循环位数 for i := 0; i < d; i++ { //10个桶子 temp := [20][]int{} //遍历序列 for j := 0; j < length; j++ { //先求余，再求商，下标不为负，+10保证为非负数 //个位数值：x%10/1+10；十位数值：x%100/10+10 bucket := (arr[j] % mod / dev)+10 //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //为arr排序时的下标 k := 0 //排序arr for m := 0; m < 20; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //为下一位做准备 mod *= 10 dev *= 10 }}//元素的最大位数func maxBit(arr []int) int { length := len(arr) d := 1 p := 10 for i := 0; i < length; i++ { for arr[i] >= p { d++ p *= 10 } } return d}/<code>元旦快乐！
分享到:
閱讀更多 南方有嘉木1993 的文章
