排序算法记录（冒泡+快排+归并）

前言

冒泡 + 快排 + 归并，这三种排序算法太过经典，但又很容易忘了。虽然一开始接触雀氏这些算法雀氏有些头大，但时间长了也还好。主要是回忆这些算法干了啥很耗时间。

如果在笔试时要写一个o(nlogn)的排序算法，如果不能立刻写出 快排或者归并，未免有些太浪费时间了。

故写这篇文章用于记录

tip: 一下内容均实现升序排序

冒泡排序

所谓冒泡，就是每一轮都排出一个最大的元素，把他丢在末尾。

如上图所示，5个元素的数组我们需要5轮遍历，每次遍历可以排出一个当前遍历区域内最大的元素

而确定最大元素的方法起始也很简单。每一次遍历，我们都和其前一个元素对比，也就是比较arr[j - 1]，arr[j]。如果 arr[j - 1] > arr[j]，则交换，否则不变。这样的比较方式让算法趋向于将大的元素向右边送，直到将最大的元素送到最右侧

当第一轮排序完成后，第二轮排序的范围则被缩小。因为已知最大元素在最右侧，那么无需遍历最右侧元素。

第三轮同理，无需遍历倒数第二个元素。以此类推

import java.util.*;public class Main {public static void main(String[] args) {// 冒泡int N;Scanner sc = new Scanner(System.in);N = sc.nextInt();int[] arr = new int[N];for (int i = 0; i < N; ++i) {arr[i] = sc.nextInt();}// sort 核心for (int i = 0; i < N; ++i) {for (int j = 1; j < N - i; ++j) {if (arr[j - 1] > arr[j]) {int tmp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = tmp;}}}// printfor (int i = 0; i < N; ++i) {System.out.print(arr[i]);if (i < N - 1) System.out.print(" ");}}
}

快速排序

所谓快速排序，和俄罗斯套娃很像。我们想要快速排序俄罗斯套娃，可以做如下操作：

1. 选出一个基准娃
2. 遍历所有娃，小的放左边，大的放右边
3. 如果两侧的娃不用排序，则终止
4. 对基准娃左右两侧的娃娃们做1，2，3操作

快排也是类似的

不同的是，俄罗斯套娃是将别的元素摆放到基准娃的两侧；快排是通过交换左右两侧元素，定位到base的位置

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] arr = new int[N];for (int i = 0; i < N; ++i) {arr[i] = sc.nextInt();}// quickSortquickSort(arr, 0, N - 1);// printfor (int i = 0; i < N; ++i) {System.out.print(arr[i]);if (i < N - 1) System.out.print(" ");}}public static void quickSort(int[] arr, int lef, int rig) {if (lef >= rig) return;int base = arr[lef];int lp = lef, rp = rig;while (lp < rp) {// 右指针寻找到<base的数for (; rp > lp && arr[rp] >= base; --rp);arr[lp] = arr[rp];// 左指针寻找到>base的数for (; rp > lp && arr[lp] <= base; ++lp);arr[rp] = arr[lp];}arr[lp] = base;quickSort(arr, lef, lp - 1);quickSort(arr, lp + 1, rig);}
}

tip: 快排有一些注意点需要强调

1. 递归终止条件，快排起始也是递归，是递归就需要终止条件。本题递归的终止条件就是lef >= rig，排序范围左侧端点不在右侧端点左边
2. for (; rp > lp && arr[rp] >= base; --rp); 这个for相当于右侧小人，寻找 小于 base的数。因为是寻找小于，因此循环条件是 >= base就一直寻找
3. 如果base是数组第一个元素，那么先走动的必须是右侧小人。因为数组最左侧元素，我们用base进行备份，先走右侧小人覆盖最左侧元素不会丢失base信息

归并排序

归并排序就有点蛋疼了，虽然代码极少（相对来说），但思维量如果不熟悉分治的情况下还是比较大的。

本文并非专业的介绍文章，感兴趣的读者可以详细阅读这篇文章

归并排序大致思路如下：

1. 往死里拆分数组，具体拆分的方式就是对半拆
2. 当拆分到不能再拆，局部合并

其中，mergeSort干的任务是对lef ~ right范围内的数组归并排序，merge属于归并排序中，并的部分。

因为递归的原因，上层递归栈merge数组，以mid为临界区域，left ~ mid，mid + 1 ~ right这两段数组，内部元素都是局部递增的。这个原因很简单，因为递归的特性，回溯到上层栈，底层栈一定把功能实现好。

这有点类似于甩锅，我排序全部数组太累了，于是找两个小弟，一个归并排序左边，一个排序右边。我不许用关心小弟怎么排序，我只需要知道，等小弟回来（回溯），我就只需要排序两个有序数组

所以要实现merge的功能，起始就是对两段有序数组进行排序

假设两段数组分别是arr1, arr2（实际上只有arr，为了方便叙述，我们说成两段）具体的排法是双指针遍历。

对于arr1, arr2。谁的元素大，谁就把元素按序存储到tmp中。

import java.util.*;public class Main {private static int[] tmp;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] arr = new int[N];tmp = new int[N];for (int i = 0; i < N; ++i) {arr[i] = sc.nextInt();}// mergemergeSort(arr, 0, N - 1);// printfor (int i = 0; i < N; ++i) {System.out.print(arr[i]);if (i < N - 1)System.out.print(" ");}sc.close();}public static void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, right);}}public static void merge(int[] arr, int left, int right) {int mid = (left + right) / 2;        int lp = left, rp = mid + 1, k = left;while (lp <= mid && rp <= right) {if (arr[lp] < arr[rp]) tmp[left++] = arr[lp++];else tmp[left++] = arr[rp++]; }while (lp <= mid) tmp[left++] = arr[lp++]; // 左区间没迭代完while (rp <= right) tmp[left++] = arr[rp++]; // 右区间没迭代完for (; k <= right; ++k) arr[k] = tmp[k]; // copy}
}

另外，值得一提的是，归并是上述三种排序中最快的。冒泡，快排都没有AC