堆排序及其以后的方法没有看

• 十大经典排序算法（动图演示）
• 比较型排序与非比较型排序算法的总结

1 算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线 性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运 行，因此也称为线性时间非比较类排序。

1.2 算法复杂度

1.3 相关概念

• 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
• 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

2 冒泡排序（Bubble Sort）

三分钟彻底理解冒泡排序：N 个数字要排序完 成，总共进行 N-1 趟排序，每 i 趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内 层控制每一趟的循环次数。

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它 们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字 由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.1 算法描述

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

2.2 动图展示

2.3 代码实现

#include <iostream>
using namespace std;

const int len = 13; // 用来统一数组下标

void BubbleSort(int array[], int len)
{
  for (int i = 0; i < len - 1; i++) // 遍历无序列表
  {
    for (int j = 0; j < len - i - 1; j++) // 寻找最大项，不稳定时后移，然后逐步和邻位交换位置
      if(array[j] > array[j + 1])
      {
        int temp = array[j + 1];
        array[j + 1] = array[j];
        array[j] = temp;
      }
  }
}

int main()
{
  int array[len] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  BubbleSort(array, len);
  for (int i = 0; i < len; i++)
    cout << array[i] << endl;
  return 0;
}

3 简单选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素 ，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末 尾。以此类推，直到所有元素均排序完毕。

3.1 算法描述

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为 R[1..n]（内层 for 循环），有序区为空；
• 第 i 趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为 R[1..i-1]和 R(i..n）。该趟排序从当前无序 区中-选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 交换，使 R[1..i]和 R[i+1..n)分别变为记 录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；
• n-1 趟结束，数组有序化了。

3.2 动图展示

3.3 代码实现

#include <iostream>
using namespace std;

const int len = 13; // 用来统一数组下标

void SelectSort(int array[], int len)
{
  for (int i = 0; i < len - 1; i++){ // 遍历无序列表
    int minIndex = i, min = array[i]; // 假设最小项和最小索引
    for (int j = i + 1; j < len; j++) // 寻找无序列表最小的数
      if(array[minIndex] > array[j])
      {
        minIndex = j; // 将最小数的索引保存
        min = array[j]; // 将最小数的保存
      }
    array[minIndex] = array[i]; // 将i位置原来的值，移动到无序列表
    array[i] = min; // 将最小值移动到有序列表
  }
}

int main()
{
  int array[len] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  SelectSort(array, len);
  for (int i = 0; i < len; i++)
    cout << array[i] << endl;
  return 0;
}

4 简单插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于 未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

4.1 算法描述

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤 2~5。

4.2 动图演示

4.3 代码实现

#include <iostream>
using namespace std;

const int len = 13; // 用来统一数组下标

void InsertionSort(int array[], int len)
{
  for (int i = 1; i < len; i++)
  {
    int target = array[i];
    int j = i - 1; // 默认已排序的元素
    while (j >= 0 && array[j] > target) // 在已排序好的队列中从后向前扫描
    {
      array[j + 1] = array[j];  // 已排序的元素大于新元素，将该元素移到下一个位置
      j--; // 再比较前一个元素，判断是否还需要向前移动
    }
    array[j + 1] = target;
  }
}

int main()
{
  int array[len] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  InsertionSort(array, len);
  for (int i = 0; i < len; i++)
    cout << array[i] << endl;
  return 0;
}

#include <iostream>
using namespace std;

const int len = 13; // 用来统一数组下标

void InsertionSort(int array[], int len)
{
  for (int i = 1; i < len; i++)
  {
    // 获取当前项
    int target = array[i], min = 4e10, pos = -1;
    // 比较当前项和有序数组每一项，确定插入位置
    // 如果当前项比有序数组每一项都大，直接跳出此次循环
    // 如果当前项大小在有序数组之中，找到插入位置
    for (int j = 0; j < i; j++)
      if(array[j] > target && array[j] < min)
      {
        min = array[j];
        pos = j;
      }
    // 插到合适的位置
    if (pos != -1)
    {
      // 有序数组中，将比 当前项 大的项逐一往后移
      for (int j = i; j > pos; j--)
        array[j] = array[j - 1];
      // 把目标值插入到找到的pos位置
      array[pos] = target;
    }
  }
}

int main()
{
  int array[len] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  InsertionSort(array, len);
  for (int i = 0; i < len; i++)
    cout << array[i] << endl;
  return 0;
}

let arr = [8, 94, 15, 88, 55, 76, 21, 39];

function insertSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var temp = arr[i];
    var j = i - 1; //默认已排序的元素
    while (j >= 0 && arr[j] > temp) {
      //在已排序好的队列中从后向前扫描
      arr[j + 1] = arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置
      j--; // 再比较前一个元素，判断是否还需要向前移动
    }
    arr[j + 1] = temp;
  }
  return arr;
}

console.log(insertSort(arr));

4.4 算法分析

插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程 中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

5 希尔排序（Shell Sort）

1959 年 Shell 发明，第一个突破 O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于 ，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

5.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。 仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

5.2 动图演示

5.3 代码实现

#include <iostream>
#include <math.h>
using namespace std;

const int len = 13; // 用来统一数组下标

void ShellSort(int array[], int len)
{
  for (int gap = ceil(len / 2); gap > 0; gap = ceil(gap / 2))
    for(int i = gap; i < len; i++)
    {
      int j = i;
      int current = array[i];
      while (j - gap >= 0 && current < array[j - gap])
      {
        array[j] = array[j - gap];
        j = j - gap;
      }
      array[j] = current;
    }
}

int main()
{
  int array[len] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  ShellSort(array, len);
  for (int i = 0; i < len; i++)
    cout << array[i] << endl;
  return 0;
}

function shellSort(arr) {
  var len = arr.length;
  for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
    for (var i = gap; i < len; i++) {
      var j = i;
      var current = arr[i];
      while (j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = current;
    }
  }
  return arr;
}
console.log(shellSort([311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410]));

5.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序 列的算法是《算法（第 4 版）》的合著者 Robert Sedgewick 提出的。

6 归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典 型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两 个有序表合并成一个有序表，称为 2-路归并。

6.1 算法描述

• 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

6.2 动图演示

6.3 代码实现

JS 实现归并排序

#include <iostream>
using namespace std;

const int len = 13; // 用来统一数组下标

// 对array数组下标范围在[start， end] 的元素进行排序
void MergeSort(int *array, int start, int end)
{
  // 递归中止条件
  if (start == end - 1)
    return;
  // 对2个子数组分开排序
  int mid = (start + end) / 2;
  MergeSort(array, start, mid);
  MergeSort(array, mid, end);
  // 分配临时空间存放合并元素
  int *tmp = new int[end - start];
  // 依次取出子数组的元素，进行合并
  int left_idx = start, right_idx = mid, i = 0;
  while (left_idx < mid && right_idx < end)
  {
    if (array[left_idx] < array[right_idx])
      tmp[i++] = array[left_idx++];
    else
      tmp[i++] = array[right_idx++];
  }
  // 如果有子数组元素没有取完，则全部并入临时空间
  while (left_idx < mid)
    tmp[i++] = array[left_idx++];
  while (right_idx < end)
    tmp[i++] = array[right_idx++];
  // 从临时空间复制会返回数组中
  for (int i = 0, idx = start; i < end - start; i++, idx++)
    array[idx] = tmp[i];
  // 释放临时空间
  delete[] tmp;
}

int main()
{
  int array[len] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  for (int i = 0; i < len; i++)
    cout << array[i] << " ";
  cout << endl;
  MergeSort(array, 0, len - 1);
  for (int i = 0; i < len; i++)
    cout << array[i] << " ";
  cout << endl;
  return 0;
}

5 归并排序代码

#include <iostream>
using namespace std;

void Merge(int array[], int start1, int end1, int start2, int end2)
{
  int n1 = end1 - start1 + 1, n2 = end2 - start2 + 1;
  int arr_left[n1], arr_right[n2];
  for(int i = 0; i < n1; i++)
    arr_left[i] = array[start1 + i];
  for(int j = 0; j < n2; j++)
    arr_right[j] = array[start2 + j];
  int left = 0, right = 0;
  int pos = start1;
  while (left < n1 && right < n2)
  {
   if(arr_left[left] < arr_right[right])
   {
     array[pos] = arr_left[left];
     left++;
   }
   else
   {
     array[pos] = arr_right[right];
     right++;
   }
    pos++;
  }
  while (left < n1)
  {
    array[pos] = arr_left[left];
    left++;
    pos++;
  }
  while (right < n2)
  {
    array[pos] = arr_right[right];
    right++;
    pos++;
  }
}

void MergeSort(int array[], int start, int end)
{
  if(start < end)
  {
    int mid = start + (end - start) / 2;
    // 将数组左边和右边，分别递归调用
    MergeSort(array, start, mid);
    MergeSort(array, mid + 1, end);
    // 合并
    Merge(array, start, mid, mid + 1, end);
  }
}


int main()
{
  int len = 13;
  int array[13] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};

  // 手动输入数据
  // int len;
  // cin >> len;
  // int array[len];
  // for(int i = 0; i < len; i++)
  //   cin >> array[i];

  MergeSort(array, 0, len - 1);
  for (int i = 0; i < len; i++)
    cout << array[i] << endl;
  return 0;
}

function mergeSort(arr) {
  var len = arr.length;
  if (len < 2) {
    return arr;
  }
  var middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  var result = [];
  console.log(left, right);
  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
  return result;
}
console.log(mergeSort([311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410]));

6.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的 多，因为始终都是 O(nlogn）的时间复杂度。代价是需要额外的内存空间。

7 快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关 键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

7.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以 到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

7.2 动图演示

7.3 代码实现

#include <iostream>
using namespace std;

void QuickSort(int * array, int len)
 {
  if(len == 1)
    return;
  // 按照最坏的可能，为2个子数组分配空间
  int * left = new int[len], * right = new int[len];
  // 设置两个子数组长度的初值（为0）
  int left_idx = 0, right_idx = 0;
  // 1.拆分
  int key = array[0];
  for(int i = 0; i < len; i++)
  {
    if(array[i] < key)
      left[left_idx++] = array[i];
    if(array[i] > key)
      right[right_idx++] = array[i];
  }
  // 2.对子数组进行排序
  QuickSort(left, left_idx);
  QuickSort(right, right_idx);
  // 3.合并子数组
  int idx = 0;
  for(int i = 0; i < left_idx; i++)
    array[idx++] = left[i];
  array[idx++] = key;
  for(int i = 0; i < right_idx; i++)
    array[idx++] = right[i];
  // 释放临时空间
  delete[] left;
  delete[] right;
 }

8 堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时 满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

8.1 算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到 有序区的元素个数为 n-1，则整个排序过程完成。

8.2 动图演示

8.3 代码实现

function mergeSort(arr) {
  var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
  function buildMaxHeap(arr) {
    // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len / 2); i >= 0; i--) {
      heapify(arr, i);
    }
  }
  function heapify(arr, i) {
    // 堆调整
    var left = 2 * i + 1,
      right = 2 * i + 2,
      largest = i;
    if (left < len && arr[left] > arr[largest]) {
      largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
      largest = right;
    }
    if (largest != i) {
      swap(arr, i, largest);
      heapify(arr, largest);
    }
  }
  function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length - 1; i > 0; i--) {
      swap(arr, 0, i);
      len--;
      heapify(arr, 0);
    }
    return arr;
  }
}

9 计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一 种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

9.1 算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。

9.2 动图演示

9.3 代码实现

function countingSort(arr, maxValue) {
  var bucket = newArray(maxValue + 1),
    sortedIndex = 0,
    arrLen = arr.length,
    bucketLen = maxValue + 1;

  for (var i = 0; i < arrLen; i++) {
    if (!bucket[arr[i]]) {
      bucket[arr[i]] = 0;
    }
    bucket[arr[i]]++;
  }

  for (var j = 0; j < bucketLen; j++) {
    while (bucket[j] > 0) {
      arr[sortedIndex++] = j;
      bucket[j]--;
    }
  }
  return arr;
}

9.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 k 之间的整数时，时间复杂度是 O(n+k)，空间复杂 度也是 O(n+k)，其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时，计数排序是一个很有效 的排序算法。

10 桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有 可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

10.1 算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

10.2 图片演示

10.3 代码实现

if (arr.length === 0) {
  return arr
}
var i
var minValue = arr[0]
var maxValue = arr[0]
for (i = 1; i < arr.length; i++) {
  if (arr[i] < minValue) {
    minValue = arr[i] // 输入数据的最小值
  } else if (arr[i] > maxValue) {
    maxValue = arr[i] // 输入数据的最大值
  }
}

// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5 // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
var buckets = newArray(bucketCount)
for (i = 0; i < buckets.length; i++) {
  buckets[i] = []
}

// 利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
  buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i])
}

arr.length = 0
for (i = 0; i < buckets.length; i++) {
  insertionSort(buckets[i]) // 对每个桶进行排序，这里使用了插入排序
  for (var j = 0; j < buckets[i].length; j++) {
    arr.push(buckets[i][j])
  }
}

return arr
}

10.4 算法分析

桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度， 因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越 少。但相应的空间消耗就会增大。

11 基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性 是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的 低优先级高的在前。

11.1 算法描述

取得数组中的最大数，并取得位数； arr 为原始数组，从最低位开始取每个位组成 radix 数组；对 radix 进行 计数排序（利用计数排序适用于小范围数的特点）；

11.2 动图演示

11.3 代码实现

var counter = [];
function radixSort(arr, maxDigit) {
  var mod = 10;
  var dev = 1;
  for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for (var j = 0; j < arr.length; j++) {
      var bucket = parseInt((arr[j] % mod) / dev);
      if (counter[bucket] == null) {
        counter[bucket] = [];
      }
      counter[bucket].push(arr[j]);
    }
    var pos = 0;
    for (var j = 0; j < counter.length; j++) {
      var value = null;
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value;
        }
      }
    }
  }
  return arr;
}

11.4 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都 需要 O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要 O(n)的时间复杂度。假如待排数据可以分为 d 个关键字，则基数排序的时间复杂度将是 O(d*2n) ，当然 d 要远远小于 n，因此基本上还是线性级别的。

基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k，因此额外空间需要大概 n 个左右。

快速排序和归并排序比较

快速排序和归并排序都是分制思想的实践。虽然如此，二者在递归实现上是有本质的差异。

归并排序的核心是归并，归并的本质是对有两个序数组的排序合并，所以归并排序首先将排序数组递归等 分切割直到数组中的基本元素（1 个元素），然后归并两个这样的基本单元，并逐渐向上层归并，直到回到排序数 组左右各一半的情况，此时将进行最后一次归并，而左右子数组均已是有序数组。

归并排序的思想：

1. 将序列中待排数字分为若干组，每个数组分为一组；
2. 将若干个组俩俩合并，保证合并后的组是有序的；
3. 重复第二步操作直到剩下一组，排序完成。

快速排序的核心是划分。划分的关键是标杆（pivot），快速排序首先进行划分（这里考虑基本的划分算法， 最简单就是每次取数组最右侧元素），在选取第一个标杆后，将比标杆小的数组都移动到排序数组的左半边，比标 杆大的都返回到标杆的右半边完成初步排序。然后以标杆为界，将数组分成左右两半，进行切割递归执行划分，直 到需要划分的数组大小为 2 个，完成这些基本数组的划分后，整个数组已经被大大小小的标杆插满，此时数组已 经完成排序。

纵观归并排序和快速排序过程可以发现，归并排序的思路是先递归切割，然后依次向上归并，自下而上完成排序； 快速排序则是先划分，再递归切割，然后划分，再切割，切割完成排序完成，自上而下完成排序。

归根到底，归并排序和快速排序在递归和关键操作（归并和划分）执行顺序上的不同，是由归并和划分的本质不同 造成的。归并的前提是两个有序数组，所以需要一直递归向下切割直到找到两个只有 1 个元素的基本数组，然后 就可以归并了，所以必须先递归切割再归并；而快速排序的向下递归切割，必须依赖划分的结果（划分完成一次排 序，然后返回标杆位置），所以必须先划分再递归切割数组。