2020-11-19 排序算法一（冒泡和快排多种实现）

主流的排序算法

• 时间复杂度为O(n^2):
  冒泡排序
  选择排序
  插入排序
  希尔排序（介于O(n^2)与O(nlogn)之间的）

• 时间复杂度为O(nlogn):
  快速排序
  归并排序
  堆排序

• 时间复杂度为线性的：
  计数排序
  桶排序
  基数排序

稳定排序和不稳定排序：有些序列中，可能存在相同的数，如果排序前后他们的先后顺序没有变化，则稳定。

冒泡排序

• 乞丐版：双重循环，滴水不漏；

  function bubble1(list: number[]) {
    console.log(list);
    for (let i = 0; i < list.length - 1; i++) {
      for (let j = 0; j < list.length - 1 - i; j++) {
        let tem = 0;
        if (list[j] > list[j+1]) {
          tem = list[j];
          list[j] = list[j+1];
          list[j+1] = tem;
        }
      }
    }
    console.log(list);
  }
  

• 白银版：isSorted标记，循环过程中判断有没有位置交换，如果没有，则直接退出了。

  function bubble2(list: number[]) {
    console.log(list);
    for (let i = 0; i < list.length - 1; i++) {
      let isSorted = true;
      for (let j = 0; j < list.length - 1 - i; j++) {
        let temp = 0;
        if (list[j] > list[j+1]) {
          temp = list[j];
          list[j] = list[j+1];
          list[j+1] = temp;
          isSorted = false;
        }
      }
      if (isSorted) {
        break;
      }
    }
    console.log(list);
  }
  

• 黄金版：界定有序区，避免无效对比，isSorted配合sortBorder，发生位置交换就记下该位置索引，最后一次交换的位置一定是有序区的边界。

  function bubble3(list: number[]) {
    console.log(list);
    let lastIndex = list.length - 1;
    let sortBorder = lastIndex;
    for (let i = 0; i < list.length - 1; i++) {
      let isSorted = true;
      for (let j = 0; j < sortBorder; j++) {
        let temp = 0;
        if (list[j] > list[j+1]) {
          temp = list[j];
          list[j] = list[j+1];
          list[j+1] = temp;
          lastIndex = j;
          isSorted = false;
        }
      }
      sortBorder = lastIndex;
      if (isSorted) {
        break;
      }
    }
    console.log(list);
  }
  

鸡尾酒排序（终极版冒泡）

上面的算法都有一个问题，那就是对比方向是从左到右，而且我们比较的是右数大于左数就移动，那么最大的数可以一次遍历就移动到边缘，但是对于较小数，我们只交换过一次位置，就不再处理了。就导致我们需要遍历n-1次，才能达到目的。

从左向右可以一次处理最大值，那么最小值就可以考虑从右到左，一次处理，将其移动到最小端边缘。
鸡尾酒排序的过程就类似于钟摆，先从左到右，然后再从右到左...只要有一轮没有发生过位置变化，则说明已经有序。

  function bubble4(list: number[]) {
    console.log(list);
    for (let i = 0; i < list.length / 2; i++) {
      let temp = 0;
      let isSorted = true;
      // 从左向右
      for (let j = 0; j < list.length - i - 1; j++) {
        if (list[j] > list[j+1]) {
          temp = list[j];
          list[j] = list[j+1];
          list[j+1] = temp;
          isSorted = false;
        }
      }
      if (isSorted) {
        break;
      }
      isSorted = true;
      for (let j = list.length - i - 1; j > i; j--) {
        if (list[j] < list[j-1]) {
          temp = list[j];
          list[j] = list[j-1];
          list[j-1] = temp;
          isSorted = false;
        }
      }
      if (isSorted) {
        break;
      }
    }
    console.log(list);
  }

快速排序

冒泡排序的时间复杂度达到了O(n^2)，快速排序呢？我们先来看一下快速排序的核心概念：

• 找到一个基准元素；
• 遍历元素与基准元素对比，小于基准元素的往左排，大于的往右排。这样在单次遍历后就依据基准元素形成了两个数列；
• 将两个数列分别当作一个数列，进行上两步操作，循环往复，直至无法再分；
• 最后将其拼接起来就形成了有序的数列。

这就是典型的分治法，由于需要遍历所有对象，所有复杂度暂时为O(n)，又由于每次分一半，相当于一个长度为n的数列需要分割logn次，所以最终快速排序时间复杂度为O(nlogn)。

基准元素

如何找一个合适的基准元素呢？根据上面的过程，我们可以得出，这个基准数如果是数列的中位数，那非常不错，我们每次分割的数列长度会近乎相等，时间复杂度也完美契合O(nlogn)。但是当我们选中的基准数为数列的最大值或者最小值呢？这时分割后只会存在一个队列，导致我们可以分割n次，时间复杂度退化成了O(n^2)。

技巧：一般来说，我们会寻找一个随机数，让其与数列首位的值进行交换，然后将其当作基准数，大多数情况下这样是可以保证我们的分治法得到发挥，但也存在极小概率使得我们选择了一个极值作为基准数。因此快速排序的时间复杂度并不是完全固定的。

元素交换

• 双边循环法
  • 1、找到基准元素pivot（默认为第一个元素list[0]），遍历过程中，存在两个指针，一个left（初始值为0），一个right（初始值为list.length - 1）；
  • 2、在left < right的条件（因为等于则说明该次遍历完成）下，-①-从right开始，判断right指针的元素是否大于pivot，如果大于，则right指针左移（right--），直到right元素小于等于pivot，此时目标移至left指针，如果left指针元素小于等于pivot（初始肯定是等于的），则left指针右移（left++），直至left指针元素大于pivot，此时，left指针元素大于pivot，而right指针元素小于pivot，由于我们想要数列从左往右呈现从小到大的顺序，所以交换left和right指针的值。再从上述的-①-处开始判断。直到left指针与right指针重合，此时交换指针元素和pivot元素位置。
  • 3、第二步完成后，我们得到了一个以pivot值为分界线，左侧小于pivot，右侧大于pivot的数列，根据分治法，我们将左侧和右侧分别再当成一个数列进行1、2步，直到左侧右侧数列不可再分。

  • 4、递归进行，将结果拼接起来，即可形成一个有序数列。
    第2步过程如图

    
    来源于漫画算法

function quickSort(list: number[]) {
  if (list.length <= 1) {
    return list;
  }
  // 找到一个随机基准数并放到数列首位
  const pivotIndex = Math.floor(Math.random() * list.length);
  const pivot = list[pivotIndex];
  list[pivotIndex] = list[0];
  list[0] = pivot;
  // 初始化左右指针
  let leftIndex = 0;
  let rightIndex = list.length - 1;
  while (leftIndex != rightIndex) {
    // 右侧指针对比并向左移动
    while (leftIndex < rightIndex && list[rightIndex] > pivot) {
      rightIndex--;
    }
    // 左侧指针对比并向右移动
    while (leftIndex < rightIndex && list[leftIndex] <= pivot) {
      leftIndex++;
    }
    // 左右指针都运动一次后交换对应元素
    if (leftIndex < rightIndex) {
      list[leftIndex] = list[leftIndex] ^ list[rightIndex];
      list[rightIndex] = list[leftIndex] ^ list[rightIndex];
      list[leftIndex] = list[leftIndex] ^ list[rightIndex];
    }
  }
  // 遍历结束将基准元素放置数列中间
  list[0] = list[leftIndex];
  list[leftIndex] = pivot;
  if (list.length < 3) {
    return list;
  }
  const leftList = list.slice(0, leftIndex);
  const rightList = list.slice(leftIndex+1);
  // 递归获取结果
  return [...quickSort(leftList), pivot, ...quickSort(rightList)];
}

• 单边循环法
  该方法比较简单
  • 1、找一个基准数pivot，一般直接取第一个即可，也可以随机找一个，然后放置到数列首位；
  • 2、定义一个mark指针，从一个方向进行遍历，遇到比pivot小的数，mark右移一位，代表比pivot 小的数多一个，然后交换mark位置的值和当前遍历的值，这是为了保证mark位置及左边的元素一定是小于pivot的，因为我们遇到比pivot大的数是按兵不动的。
  • 3、当数列遍历完成后，交换mark位置的值和pivot。形成一个以pivot为基准，左小右大的数列。
  • 4、分治法，递归左右数列得到结果。

      // 单边循环法
function quickSortSingleSide(list: number[]) {
  if (list.length <= 1) {
    return list;
  }
  let mark = 0;
  // 基准元素定第一个元素
  const pivot = list[mark];
  for (let i = mark+1; i < list.length; i++) {
    // 从第二个元素开始遍历，如果小于pivot，则指针右移一位，代表比基准数小的数多一位
    if (list[i] < pivot) {
      mark++;
      // 将小于基准数的数与mark的位置的数进行交换（保证mark位置及左边的元素一定小于pivot）
      const markValue = list[mark];
      list[mark] = list[i];
      list[i] = markValue;
    }
  }
  // 交换pivot和mark位置的数，形成以pivot为界限的左小右大有序数列
  list[0] = list[mark];
  list[mark] = pivot;
  return [...quickSortSingleSide(list.slice(0, mark)), pivot, ...quickSortSingleSide(list.slice(mark+1))];
}

栈替换递归

我们说过，大多数递归操作，都可以用栈来替换其实现，每次递归，相当于往栈内压入了一个方法的执行域，而当方法返回时，就相当于出栈。

数组实现栈：

function sortByStack(list: number[]) {
  // 定义存放栈为数组
  const stack: {start: number, end: number}[] = [];
  // 定义栈顶元素
  const root = { start: 0, end: list.length - 1 };
  // 入栈
  stack.push(root);
  // 遍历条件为栈内有元素
  while (stack.length > 0) {
    // 执行一次遍历，需要将栈顶出栈
    const stackPop = stack.pop();
    // 获取该次遍历得到的mark标记位置
    const pivotIndex = getPivotIndex(list, stackPop.start, stackPop.end);
    // 如果mark左侧还有多于1个元素，那么说明左侧的元素还可以再遍历，将其压入栈内
    if (stackPop.start < pivotIndex - 1) {
      stack.push({
        start: stackPop.start,
        end: pivotIndex - 1
      });
    }
    // 如果mark右侧还有多于1个元素，那么说明右侧的元素还可以再遍历，将其压入栈内
    if (stackPop.end > pivotIndex + 1) {
      stack.push({
        start: pivotIndex + 1,
        end: stackPop.end
      });
    }
  }
  return list;
}
// 直接在此方法内修改数列元素的位置，并返回mark位置索引
function getPivotIndex(list: number[], start: number, end: number): number {
  const pivot = list[start];
  let mark = start;
  for (let i = start + 1; i <= end; i++) {
    if (list[i] < pivot) {
      mark++;
      const markValue = list[mark];
      list[mark] = list[i];
      list[i] = markValue;
    }
  }
  list[start] = list[mark];
  list[mark] = pivot;
  return mark;
}

链表实现栈

一直用数组实现，虽然数组比较直观，但是链表也不是吃素的，需要注意的是：

• 入栈操作相当于添加头节点
• 出栈操作相当于去除头节点

function sortByLinkList(list: number[]) {
  const root = { start: 0, end: list.length - 1 };
  // 头节点
  let linkList: any = {
    data: {
      start: root.start,
      end: root.end
    },
    next: null
  };
  // 头节点不为空则继续遍历
  while (linkList.data) {
    console.log("链表", linkList);
    // 获取头节点
    const linkListEnd = linkList.data;
    // 表头出栈
    linkList = linkList.next || {};
    const pivotIndex = getPivotIndex(list, linkListEnd.start, linkListEnd.end);
    if (linkListEnd.start < pivotIndex - 1) {
      const newLinkList = {
        data: {
          start: linkListEnd.start,
          end: pivotIndex - 1
        },
        next: linkList
      };
      // 每次入栈相当于往表头插入新的节点，将其变为头节点
      linkList = newLinkList;
    }
    if (linkListEnd.end > pivotIndex + 1) {
      const newLinkList = {
        data: {
          start: pivotIndex + 1,
          end: linkListEnd.end
        },
        next: linkList
      };
      // 每次入栈相当于往表头插入新的节点，将其变为头节点
      linkList = newLinkList;
    }
  }
  return list;
}

下节见吧！