冒泡排序

前言

冒泡排序是十大经典排序之一，它的时间复杂度为O(n^2),在最好的情况下能达到O(n)。

基本思想：

1. 从数组的第一个元素开始，依次比较相邻的两个元素，如果它们的顺序错误（升序为左大于右，降序为左小于右），则进行交换。
2. 经过一轮遍历后，最大（或最小）的元素会被交换到数组的末尾（或开头）。
3. 对除了已排好序的部分外的所有元素重复执行步骤 1 和步骤 2，直到整个数组有序。

js代码演示

function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    let hasSort = true // 外循环，引入标志位
    // 找到最大的元素放置到数组的尾部
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        hasSort = false // 满足交换条件，更改标志位
      }
    }
    if (hasSort) break; // 已经排序完成，退出循环
  }
  return arr
}

// 交换元素的位置
function swap(arr, i, j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

代码解析：冒泡排序的代码比较简单，这里我们加入了标志位 hasSort 默认为 true,代表是否已经完成了排序。每次外循环开始的时候我们都默认已经完成了排序，如果内部循环满足交换两个元素的条件，则将它设置为 false，需要继续比较元素，进行排序。如果外循环的标志没有动过，说明它的子数组是有序的，无须交换，那么下次外循环就不需要进行。

其实这代代码还可以继续优化，我们留意到操作步骤的最后一步，每次排序结束，最后一个元素总是最大的，即大数下沉策略。当交换时，可以利用变量 swapPos 记录交换的位置。在内部循环结束后，将最后一个交换元素的位置赋值给k,这样就可以节省一下轮内循环时，从位置k到n-1的比较“开销”，代码如下

function bubbleSort2(arr) {
    let n = arr.length, k = n - 1, swapPos = 0
    for (let i = 0; i < n; i++) {
        let hasSort = true
        for (let j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1)
                swapPos = j // 记录交换位置,下一次内循环只用比较索引从 j 到 k -1 的元素
            }
        }
        if (hasSort) break
        k = swapPos
    }
    return arr
}

鸡尾酒排序，也称为双向冒泡排序（Cocktail Sort），是对冒泡排序的一种改进。它通过在每一轮遍历时交替地进行从左到右和从右到左的扫描和比较，来实现元素的排序。类似于“摇晃”一杯鸡尾酒的过程，因此得名为鸡尾酒排序。

基本思想：

1. 首先，从左到右遍历数组，比较相邻的两个元素，如果它们的顺序错误，则进行交换，将较大的元素移到右侧。
2. 然后，从右到左遍历数组，比较相邻的两个元素，如果它们的顺序错误，则进行交换，将较小的元素移到左侧。
3. 重复以上步骤，直到没有发生交换为止。这意味着数组已经排序完成。

同样的，如果我们需要优化代码，需要加入标志位判断是否已经完成排序，同时记录满足交换条件时的索引，下次内循环就可以排除那些不需要比较的元素了。

function cocktailSort(array) {
  let left,right,index,i
  left = 0 // 数组的起始索引
  right = array.length - 1 // 数组索引的最大值
  index = left // 临时变量

  // 判断数组中是否有多个元素
  while (left < right) {
    let isSorted = false
    // 每一次进入while循环，都会找出相应范围内最大最小的元素并分别放到相应的位置
    // 大的排到后面
    for (let i = left; i < right; i++) { // 从左到右扫描，找出较大的元素
      if (array[i] > array[i + 1]) { 
        swap(array, i, i + 1)
        index = i // 记录当前索引
        isSorted = true
      }
    }
    right = index // 记录最后一个交换的位置
    // 小的排到前面
    for (let i = right; i > left; i--) {
      if (array[i] < array[i - 1]) { // 从右到左扫描，找出较小的元素
        swap(array, i, i - 1)
        index = i
        isSorted = true
      }
    }
    left = index // 记录最后一个交换的位置
    if (!isSorted) { // 没有需要排序的元素了，退出循环
      break
    }
  }
  return arr
}

我们可以这样理解，有left、right两个指针，分别指向数组的起点和终点。第一步的时候，从左往右扫描，如果找到较大的元素，将元素的索引赋值给right,相当于right指针左移到满足交换条件的元素索引处。第二步的时候，从右往左扫描，如果找到较小的元素，将元素的索引赋值给left，相当于left指针右移到满足交换的元素的索引处。当左右两个指针碰撞（数组中只有一个元素），排序结束，左边都是排序好的较小的元素，右边都排序好的较大的元素。这样整个数组就排序完成了。

go代码演示：

// 冒泡排序
func bubbleSort2(arr []int) []int {
	n, k, swapPos := len(arr), len(arr)-1, 0
	for i := 0; i < n; i++ {
		hasSort := true //  外循环，引入标志位
		for j := 0; j < k; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				hasSort = false // 满足交换条件，更改标志位
				swapPos = j
			}
		}
		if hasSort { // 已经排序完，退出循环
			break
		}
		k = swapPos
	}
	return arr
}

// 鸡尾酒排序
func cocktailSort(arr []int) []int {
	var i int
	left, right := 0, len(arr)-1
	index := left // 临时变量
	// 判断数组中是否有多个元素
	for left < right {
		isSort := false                // 标志位，如果内循环没有发生交换元素，退出循环
		for i = left; i < right; i++ { // 从左往右扫描，找出较大的元素
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
				isSort = true
				index = i
			}
		}
		right = index
		for i = right; i > left; i++ { // 从右向左扫描，找出较小的元素
			if arr[i] < arr[i-1] {
				arr[i], arr[i-1] = arr[i-1], arr[i]
				isSort = true
				index = i
			}
		}
		left = index
		if !isSort {
			break
		}
	}
	return arr
}