排序

function sort(arr) {
  let hasChanged = true; // 如果没发生换位，说明已经排好序
  for(let i = 0; hasChanged && i < arr.length - 1; i++) {
    hasChanged = false;

    for(let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        hasChanged = true;
      }
    }
  }
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp
}

function sort(arr) {
  for(let i = 0; i < arr.length; i++) {
    let current = arr[i];

    let j;
    for(j = i - 1; j >= 0 && arr[j] > current; j--) {
      arr[j + 1] = arr[j]
    }

    arr[j + 1] = current;
  }
}

function sort(arr, low, high) {
  if (low >= high) {
    return;
  }

  const middle = low + Math.floor((high - low) / 2);

  sort(arr, low, middle);
  sort(arr, middle + 1, high);

  merge(arr, low, middle, high);
}

function merge(arr, low, middle, high) {
  let arrCopy = [...arr];

  let k = low;
  let i = low;
  let j = middle + 1;

  while(k <= high) {
    if (i > middle) { // 左半边已遍历完
      arr[k++] = arrCopy[j++];
    } else if (j > high) { // 右半边已遍历完
      arr[k++] = arrCopy[i++];
    } esle if (arrCopy[i] <= arrCopy[j]) {
      arr[k++] = arrCopy[i++];
    } else {
      arr[k++] = arrCopy[j++];
    }
  }
}

function sort(arr, low, high) {
  if (low >= high) {
    return;
  }

  let p = partion(arr, low, high);

  sort(arr, low, p);
  sort(arr, p + 1, high);
}

function partion(arr, low, high) {
  let pivot = low; // 支点
  let current = arr[pivot];

  for (let i = low + 1; i <= high; i++) {
    if (arr[i] < current) {
      arr[pivot++] = arr[i];
      arr[i] = arr[pivot];
    }
  }
  arr[pivot] = current;

  return pivot;
}

function sort() {
  const q = new LinkedList();

  for(let v = 0; v < V; v++) {
    if (indegree[v] === 0) { // 入度为 0 的顶点进入队列
      q.add(v);
    }
  }

  while(!q.isEmpty()) {
    let v = q.poll();
    print(v);

    for(let u = 0; u < adj[v].length; u++) {
      indegree[u]--;
      if (indegree[u] === 0) {
        q.add(u);
      }
    }
  }
}