数据结构和算法（排序）

2019-04-17

介绍下常用的排序算法，如 冒泡排序、快速排序等

  • 比较排序
    • 交换
      • 冒泡排序（Bubble Sort）
      • 快速排序（Quick Sort）
    • 插入
      • 简单插入排序
      • 希尔排序
    • 选择
      • 简单选择排序
      • 堆排序
    • 归并
      • 二路归并排序
      • 多路归并排序
  • 非比较排序
    • 计数排序
    • 桶排序
    • 基数排序

冒泡排序（Bubble Sort）

算法描述

  • 比较相邻的元素。如果第一个比第二个大，就交换它们的位置
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾最后一对，这样最后的元素就是最大的数
  • 针对所有的元素重复以上的步骤，除了最后一个
  • 重复步骤 1~3，直到排序完成

动画演示

golang 实现

func BubbleSort(s []int) []int {
	len := len(s)

	// 控制循环次数
	for i := 0; i < len-1; i++ {
		// 控制每次循环
		for j := 1; j < len-i; j++ {
			if s[j-1] > s[j] {
				s[j-1], s[j] = s[j], s[j-1]
			}
		}
	}

	return s
}

算法改进，设置交换变量

func BubbleSort(s []int) []int {
	len := len(s)

	// 控制循环次数
	for i := 0; i < len-1; i++ {
		// 算法改进，设置交换变量
		exchange := false

		// 控制每次循环
		for j := 1; j < len-i; j++ {
			if s[j-1] > s[j] {
				s[j-1], s[j] = s[j], s[j-1]

				// 发生了交换操作
				if !exchange {
					exchange = true
				}
			}
		}

		// 打印每次循环后的结果
		fmt.Printf("第 %d 次循环结果：%v\n", i+1, s)

		// 如果上一轮没有发生交换数据，证明已经是有序的了，结束排序
		if !exchange {
			break
		}
	}

	return s
}

快速排序（Quick Sort）

算法描述

  • 从数列中跳出一个基准
  • 重新排序数列，比基准大的放基准后面，比基准小的放基准前面
  • 递归的对比基准小的数列和比基准大的数列进行排序

动画演示

golang 实现

func QuickSort(s []int) []int {
	if len(s) <= 1 {
		return s
	}

	mid := s[0] // 基准
	head, tail := 0, len(s)-1

	for i := 1; i <= tail; {
		if s[i] > mid {
			s[tail], s[i] = s[i], s[tail]
			tail--
		} else {
			s[head], s[i] = s[i], s[head]
			head++
			i++
		}
	}

	QuickSort(s[:head])
	QuickSort(s[head+1:])

	return s
}