注：本篇仅用来自己学习，大量内容来自菜鸟教程（地址：1.0 十大经典排序算法 | 菜鸟教程）
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。【冒泡、插入、选择、快速、归并排序面试中出现概率极高】
1.冒泡排序
冒泡排序（Bubble Sort) 是一种简单直观的排序。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
算法步骤：
- 比较相邻的元素，如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素进行同样工作，直到最后的元素是最大的数。
- 重复上述工作，直到数字是有序的。
实现代码：
public class BubbleSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1; i < arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。 boolean flag = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false; } } if (flag) { break; } } return arr; } }
2.选择排序
选择排序是一种简单直观的排序算法，其基本思想是每次从待排序的元素中选择最小（或最大）的元素，放置到已排序序列的末尾（或开头），直到所有元素都排序完成为止。
算法步骤：
- 在未排序的序列中找出最小（大）元素，存放在排序序列的起始位置。
- 接着从剩余未排序的序列中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复上述步骤，直到所有元素均排序完毕。
实现代码：
public class SelectionSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 总共要经过 N-1 轮比较 for (int i = 0; i < arr.length - 1; i++) { int min = i; // 每轮需要比较的次数 N-i for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } return arr; } }
3.插入排序
插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素逐个插入到已经排序的序列中的合适位置，直到整个序列都排好序为止。
算法步骤：
- 将第一个元素视为已排序序列，其余元素为待排序序列。
- 从第二个元素开始，逐个将待排序序列中的元素插入到已排序序列中的合适位置。
- 对于每一个待排序元素，从其前一个元素开始，依次向前比较，直到找到合适的插入位置。
- 插入元素后，已排序序列长度加一，待排序序列长度减一。
- 重复以上步骤，直到所有元素都被插入到已排序序列中，排序完成。
代码实现：
public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp; } } return arr; } }
4.希尔排序
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
算法步骤：
- 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现：
public static void shellSort(int[] arr) { int length = arr.length; int temp; for (int step = length / 2; step >= 1; step /= 2) { for (int i = step; i < length; i++) { temp = arr[i]; int j = i - step; while (j >= 0 && arr[j] > temp) { arr[j + step] = arr[j]; j -= step; } arr[j + step] = temp; } } }
5.归并排序
归并排序是一种分治算法，它将一个待排序的序列分成两个子序列，分别对两个子序列进行排序，然后将两个已排序的子序列合并成一个有序序列。
算法步骤：
- 分解：将待排序的序列分解为两个子序列，直到每个子序列只包含一个元素。
- 解决：递归地对每个子序列进行排序。
- 合并：将两个已排序的子序列合并成一个有序序列。
代码实现：
public class MergeSort { // 归并排序算法 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, mid, right); } }
// 合并两个已排序的子序列 public static void merge(int[] arr, int left, int mid, int right) { // 计算左右子序列的长度 int n1 = mid - left + 1; int n2 = right - mid; // 创建临时数组存储左右子序列的元素 int[] L = new int[n1]; int[] R = new int[n2]; // 将元素复制到临时数组中 for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; }
// 合并两个子序列 int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; }
// 将左子序列剩余的元素复制到原始数组中 while (i < n1) { arr[k] = L[i]; i++; k++; } // 将右子序列剩余的元素复制到原始数组中 while (j < n2) { arr[k] = R[j]; j++; k++; } } }
6.快速排序
快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
- 从数列中挑出一个元素，称为 "基准"（pivot）。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现：
public class QuickSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); return quickSort(arr, 0, arr.length - 1); } private int[] quickSort(int[] arr, int left, int right) { if (left < right) { int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; } private int partition(int[] arr, int left, int right) { // 设定基准值（pivot） int pivot = left; int index = pivot + 1; for (int i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
十大排序算法（java实现）(二)：https://developer.aliyun.com/article/1534520
