排序 | CAI

# 简单排序

# 冒泡排序

每个元素进行冒泡比较，将最大元素移动到最后。一次递减比较元素个数，最终完成排序。

添加 flat 标记，当进行一边循环检测后没有元素进行更改，则证明所有元素已经排序好了，无需再进行后续循环。

// 注意将直接修改传入的数组 elements
function bubble_sort<T>(elements: T[], n: number) {
  // 递减进行循环，因为每次最后一个元素都是已经处理好的数据
  for (let P = n - 1; P >= 0; P--) {
    let flag = 0;
    // 循环移动前后最大值位置
    for (let i = 0; i < P; i++) {
      if (elements[i] > elements[i + 1]) {
        // 交换前后元素
        const swap = elements[i];
        elements[i] = elements[i + 1];
        elements[i + 1] = swap;

        // 修改标记
        flag = 1;
      }
    }
    if (flag === 0) break;
  }
}

let data = [1, 2, 3, 5, 233, 4, 32, 12, 85, 23];

bubble_sort(data, data.length);
console.log(data);

// output: [ 1, 2, 3, 4, 5, 12, 23, 32, 85, 233 ]

# 插入排序

每次取出一个元素循环向后比较，满足条件元素向后移动一个位置，直到最后取出元素插入对应位置为止

// 注意，直接对elements 数组进行排序
function insert_sort<T>(elements: T[], n: number) {
  for (let P = 1; P < n; P++) {
    let tmp = elements[P];
    let i = P;
    // 每次比tmp 元素大的元素都要往后移动一格，直到最后tmp插入正确位置
    for (; i > 0 && elements[i - 1] > tmp; i--) {
      elements[i] = elements[i - 1];
    }
    elements[i] = tmp;
  }
}

let data = [1, 2, 3, 5, 233, 4, 32, 12, 85, 23];

insert_sort(data, data.length);
console.log(data);

// output：[ 1, 2, 3, 4, 5, 12, 23, 32, 85, 233 ]

# 希尔排序

Dm = N /2, Dk = Dk+1 /2

给定一个增量序列，对增量序列索引进行排序。最后增量序列递减至 1 依次排序。

增量序列在插入排序基础上，通过给定增量进行索引值排序，降低了插入序列的遍历次数。

# Hibbard 增量序列

h i = 2 i - 1

# Sedgewick 增量序列

h i = max (9 * 4 j - 9 * 2 j + 1, 4 k - 3 * 2 k + 1)

# 堆排序

将数据构建一个最大堆，每次将最大值与最后一个值替换，这样就排好了一个最大值。依次缩小最大堆规模（每次剔除排好的最大值）。

// 构建最大堆
function buildHeap<T>(elements: T[], length: number) {
  for (let i = length - 1; i > 0; i--) {
    let pIndex = Math.floor(i / 2);
    for (let cIndex = pIndex; pIndex * 2 < length; pIndex = cIndex) {
      cIndex = Math.floor(pIndex * 2);
      if (elements[cIndex] < elements[cIndex + 1] && cIndex + 1 < length)
        cIndex++;
      if (elements[cIndex] > elements[pIndex]) {
        const swap = elements[cIndex];
        elements[cIndex] = elements[pIndex];
        elements[pIndex] = swap;
      }
    }
  }
}

function heap_sort<T>(elements: T[], length: number) {
  // 每次剔除最大值重建堆
  for (let i = length; i > 1; i--) {
    buildHeap(elements, i);
    console.log(elements);
    const tmp = elements[0];
    elements[0] = elements[i - 1];
    elements[i - 1] = tmp;
  }
}

let data: number[] = [1, 2, 3, 8, 12, 28, 123, 80, 50, 43, 68, 100];

heap_sort(data, data.length);
console.log(data);

/* output
[ 123, 100, 68, 80, 50, 28, 8, 2, 12, 43, 3, 1 ]
[ 100, 80, 68, 8, 50, 28, 1, 2, 12, 43, 3, 123 ]
[ 80, 68, 50, 8, 43, 28, 1, 2, 12, 3, 100, 123 ]
[ 68, 50, 43, 8, 12, 28, 1, 2, 3, 80, 100, 123 ]
[ 50, 43, 28, 8, 12, 3, 1, 2, 68, 80, 100, 123 ]
[ 43, 28, 12, 8, 2, 3, 1, 50, 68, 80, 100, 123 ]
[ 28, 12, 3, 8, 2, 1, 43, 50, 68, 80, 100, 123 ]
[ 12, 8, 3, 1, 2, 28, 43, 50, 68, 80, 100, 123 ]
[ 8, 3, 2, 1, 12, 28, 43, 50, 68, 80, 100, 123 ]
[ 3, 2, 1, 8, 12, 28, 43, 50, 68, 80, 100, 123 ]
[ 2, 1, 3, 8, 12, 28, 43, 50, 68, 80, 100, 123 ]
[ 1, 2, 3, 8, 12, 28, 43, 50, 68, 80, 100, 123 ]
*/

# 归并排序

将数据进行二分递归排序，结果合并在一起，最大达到目的。