**算法笔记Visualgo 排序算法**

• 1.*冒泡排序*
• 2.*选择排序*
• 3.*插入排序*
• 4.*归并排序*
• 5.*快速排序*
• 6.*随机快速排序*

1.冒泡排序

给定一个N个元素的数组，冒泡排序将：

1.如果元素大小关系不正确，交换这两个数（在本例中为a> b），
2.比较一对相邻元素（a，b），
3.重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
4.到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。
不用多说，让我们在小例子阵列[29,10,14,37,14]上尝试Bubble Sort。

如果您想象较大的项目“起泡”（也就是“浮动到数组的右侧”），则应该能想象到一个“气泡式”动画。

分析：

比较和交换需要一个以常量为界的时间，我们称之为c。
（标准）Bubble Sort中有两个嵌套循环。
外循环正好运行N次迭代。 但内部循环运行变得越来越短：

当 i = 0，（N-1）次迭代（比较和可能交换）时。
当 i = 1，（N-2）次迭代时，…
当 i =（N-2）时，1次迭代,
当 i=（N-1），0迭代.
因此，总迭代次数=（N-1）+（N-2）+ … + 1 + 0 = N *（N-1）/ 2（推导）。
总时间= c * N *（N-1）/ 2 = O（N ^ 2）

2.选择排序

给定 N 个项目和 L = 0 的数组，选择排序将：
1.在 [L … N-1] 范围内找出最小项目 X 的位置，
2.用第 L 项交换X，
3.将下限 L 增加1并重复步骤1直到 L = N-2。

别犹豫，让我们在上面的同一个小例子数组上尝试Selection Sort。
在不失普遍性的情况下，我们也可以实现反向的选择排序：找到最大项目 Y 的位置并将其与最后一个项目交换。

3.插入排序

插入排序类似于大多数人安排扑克牌的方式。

1.从你手中的一张牌开始，
2.选择下一张卡并将其插入到正确的排序顺序中，
3.对所有的卡重复上一步。
不用多说，让我们在小例子阵列[40,13,20,8]上尝试Insertion Sort。

4.归并排序

我们将在接下来的几张幻灯片中讨论两种（加一半）基于比较的排序算法：

归并排序，
快速排序和它的随机版本（只有一个变化）。
这些排序算法通常以递归方式实现，使用分而治之的问题解决范例，并且运行在合并排序和O（N log N）时间的O（N log N）时间中，以期望随机快速排序。

给定一个N个项目的数组，归并排序将：

1.将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组，
2.将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程…，
3.最后一步：归并2个N / 2元素的排序数组（为了简化讨论，我们假设N是偶数）以获得完全排序的N个元素数组。

这只是一般的想法，在我们可以讨论归并排序的真正形式之前，我们需要更多的细节。

额外数组：

void merge(int a[], int low, int mid, int high) {
  // subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
  int N = high-low+1;
  int b[N]; // 讨论: 为什么我们需要一个临时的数组 b?
  int left = low, right = mid+1, bIdx = 0;
  while (left <= mid && right <= high) // 归并
    b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
  while (left <= mid) b[bIdx++] = a[left++]; // leftover, if any
  while (right <= high) b[bIdx++] = a[right++]; // leftover, if any
  for (int k = 0; k < N; k++) a[low+k] = b[k]; // copy back
}

[1,5,19,20,2,11,15,17]
其前半部分已经排序[1,5,19,20]，
其下半部分也已经排序[2 ，11,15,17]。

void mergeSort(int a[], int low, int high) {
  // 要排序的数组是 a[low..high]
  if (low < high) { // base case: low >= high (0 or 1 item)
    int mid = (low+high) / 2;	
    mergeSort(a, low  , mid ); // 分成一半
    mergeSort(a, mid+1, high); // 递归地将它们排序
    merge(a, low, mid, high); // 解决: 归并子程序
  }
}

分析：
在归并排序中，大部分工作是在解决/归并的步骤中完成的，因为分解步骤并没有真正执行任何操作（视为O（1））。
当我们称之为归并的（a，低，中，高）时候，我们处理k =（高 - 低+ 1）项。 最多会有 k-1 个比较。 从原始数组 a 到临时数组 b 有 k 个移动，而另一个 k 移回。 总的来说，归并子例程内的操作次数 <3k-1 = O（k）。
重要的问题是这个归并子程序被调用了多少次？

无论输入的原始顺序如何，归并排序中最重要的部分是其O（N log N）性能保证。 就这样，没有任何敌手测试用例可以使归并排序对于任何N个元素数组运行比O（N log N）更长的时间。
因此，归并排序非常适合分类非常大量的输入，因为O（N log N）比前面讨论的O（N2）排序算法增长得慢得多。
归并排序也是一个稳定的排序算法。 讨论：为什么？
然而，归并排序有几个不太好的部分。 首先，从零开始实施起来并不容易（但我们不必这样做）。 其次，它在归并操作期间需要额外的O（N）存储，因此不是真正的存储效率和不到位。

5.快速排序

快速排序是另一个分而治之排序算法（另一个在这个可视化页面中讨论的是归并排序）。
我们将看到，这种确定性的，非随机化的快速排序的版本可能在对手输入中具有O（N2）的很差的时间复杂度，之后再继续随机化的和可用的版本。

划分步骤：
选择一个项目 p（称为枢轴点）
然后将 a[i…j] 的项目分为三部分：a [i…m-1]，a [m] 和 a[m + 1…j]。
a [i…m-1]（可能为空）包含小于 p 的项目。
a [m] 是枢轴点 p，例如：指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。
a [m + 1…j]（可能为空）包含大于或等于 p 的项目。 然后，递归地对这两部分进行排序。

解决步骤：不要惊讶…我们什么都不做！
如果您将其与归并排序进行比较，您会发现快速排序的 D＆C 步骤与归并排序完全相反。

最初，S1 和 S2 区域都是空的，即除了指定的枢轴点 p 之外的所有项目都在未知区域中。
然后，对于未知区域中的每个项目 a [k]，我们将 a[k] 与 p 进行比较, 并决定两种情况中的一个：
1.如果 a [k]≥p，则将 a[k] 放入 S2 或
2.否则，将 a[k] 放入 S1 中。
接下来的两张幻灯片将会详细阐述了这两种情况。
最后，我们交换a[i]和 a[m] 来将枢纽 p 放在 S1 和 S2 的中间。

int partition(int a[], int i, int j) {
  int p = a[i]; // p 是枢纽
  int m = i; // S1 和 S2 一开始是空的
  for (int k = i+1; k <= j; k++) { // 探索未知的区域
    if (a[k] < p) { // case 2
      m++;
      swap(a[k], a[m]); // C++ STL algorithm std::swap
    } // 注意：在情况1的时候我们什么不做: a[k] >= p
  }
  swap(a[i], a[m]); // 最后一步, 用a[m]交换枢纽
  return m; // 返回枢纽的指数, 用于快速排序（Quick Sort）
}

void quickSort(int a[], int low, int high) {
  if (low < high) {
    int m = partition(a, low, high); // O(N)
    // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
    quickSort(a, low, m-1); // 递归地将左子阵列排序
    // a[m] = pivot 在分区后就被排序好了
    quickSort(a, m+1, high); // 然后将右子阵列排序
  }
}

在示例数组[27,38,12,39,27,16]上尝试Quick Sort。
我们将详细说明第一个分区步骤如下：
我们设置 p = a [0]= 27。
我们设置 a[1] = 38作为 S2的一部分，因此S1 = {} 和 S2 = {38}。
我们用 a [2] = 12 交换 a[1] = 38，所以 S1 = {12} 和 S2 = {38}。
我们设置 a[3] = 39，然后 a [4] = 27 作为 S2 的一部分，因此 S1 = {12} 和 S2 = {38,39,27}。
我们用 a[5] = 16 交换 a[2] = 38，所以S1 = {12,16} 和 S2 = {39,27,38}。 我们用 a [2] = 16 交换 p = a [0] = 27，所以 S1 = {16,12}，p = {27} 和 S2 = {39,27,38}。
在此之后，a[2] = 27 保证被排序，现在快速排序递归地将左侧排序为 a[0…1]，然后递归地将右侧排序为 a[3…5]。

分析：

首先，我们分析跑一次分区的成本。
在内部分区（a，i，j）中，只有一个for循环遍历（j-i）次。 由于j可以和 N-1一样大，i 可以低至0，所以分区的时间复杂度是O（N）。
类似于归并排序分析，快速排序的时间复杂度取决于分区（a，i，j）被调用的次数。
当数组a已经按照上面的例子升序时，快速排序将设置p = a [0] = 5，并且将返回m = 0，从而使S1区域为空并且S2区域：除了枢轴之外的其他一切 （N-1项）。

在这种最坏情况的输入场景中，会发生以下情况：

Worst Case analysis of Quick Sort
第一个分区需要O（N）时间，将a分成0,1，N-1个项目，然后向右递归。
第二个花费O（N-1）时间，将a分成0,1，N-2个项目，然后再次向右递归…
直到最后，第N个分区将a分成0,1,1项，并且Quick Sort递归停止。
这是经典的N +（N-1）+（N-2）+ … + 1模式，它是O（N2），类似于本幻灯片中的分析…

当分区总是将数组分成两个相等的一半时，就会发生快速排序的最佳情况，如归并排序。
当发生这种情况时，递归的深度只有O（log N）。

在实践中，这很少见，因此我们需要设计一个更好的方法：随机快速排序。

6.随机快速排序

随机快速排序

除了执行分区算法之外，它与快速排序相同，它随机选择 a[i…j] 之间的枢轴，而不是始终选择 a[i]（或 a[i…j]之间的任何其他固定索引）。