1. 冒泡排序
描述
以从小到大排列为例：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个，接着比较第二个和第三个，直到遍历完一次，最后一个元素就是最大的数
-
按照上述步骤比较可以确定次大数，确定好后位置就在倒数第二个位置，直到遍历count-1次后，所有元素完全有序
BubbleSort
代码
public static void bubbleSort(int[] arr) {
// length个元素，共需length-1次确定无需元素中的最大数
for (int i = 0; i < arr.length - 1; i++) {
// 对无序元素进行比较，相邻元素大数靠后放置
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2. 选择排序
描述
选择排序(Selection-sort)是一种简单直观的排序算法。
工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
image
代码
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) minIndex = j; // 记录最小值下标
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
3. 插入排序
描述
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程
image
3.1 普通插入排序
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int index = i; // 前i个数有序
// 将第i个数与前面数比较，然后选择合适位置插入
while (index > 0 && arr[index] < arr[index - 1]) {
int temp = arr[index];
arr[index] = arr[index - 1];
arr[index - 1] = temp;
index--;
}
}
}
3.2 插入排序优化
public static void insertionSortImprove(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int index = i; // 前i个数有序
int temp = arr[index]; // 建立待插入数的副本
while (index > 0 && temp < arr[index - 1]) {
arr[index] = arr[index - 1];
index--;
}
arr[index] = temp;
}
}
优化后的插入排序减少了元素的交换，从而大大减少执行时间。优化后的插入排序对相对有序的数组排序更佳
4. 希尔排序
5. 归并排序
介绍
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
由于理解相对复杂，故通过图解示意原理
原理
分治思想（Divide and Conquer）:先将问题Divide若干个独立可以解决的子问题，对这些子问题Conquer后合并结果即可。一般步骤如下：
- 分解，将要解决的问题划分成若干规模较小的同类问题；
- 求解，当子问题划分得足够小时，用较简单的方法解决；
- 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
结合排序示意如下：
图示已经很清楚了，可能我们唯一有疑问的是如果输入为奇数怎么办，mid数可以归右侧，也可以归左侧，一般我们可以让mid为
mid = (l + r) /2，此时分为(l,mid)和(mid+1,r)两个序列，依次类推直到每个序列只剩一个元素。
代码
public static void mergeSort(int[] arr) {
// 第一次拆分当然从0,arr.length-1拆分
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int l, int r) {
// 当l==r就只剩一个元素，终止拆分
if (l >= r) {
return;
}
int mid = (l + r) / 2;
// 二分
// 继续拆分左侧
mergeSort(arr, 0, mid);
// 继续拆分右侧
mergeSort(arr, mid + 1, r);
// 拆分结果进行合并
merge(arr, mid, l, r);
}
private static void merge(int[] arr, int mid, int l, int r) {
// 临时数组保存原数组l到r的值
int[] temp = new int[r - l + 1];
for (int i = 0; i < temp.length; i++) {
temp[i] = arr[l + i];
}
int i = l;
int j = mid + 1;
// 对原数组l到r处赋值，保证按从小到大存放
for (int k = l; k <= r; k++) {
// i大于mid,说明mid左侧所有值已赋值完，接下来直接从右侧取值即可,因为左右侧是分别有序的
if (i > mid) {
arr[k] = temp[j - l];
j++;
} else if (j > r) {
arr[k] = temp[i - l];
i++;
} else if (temp[i - l] < temp[j - l]) {
arr[k] = temp[i - l];
i++;
} else {
arr[k] = temp[j - l];
j++;
}
}
}
6. 快速排序
描述
基于分治(D&C)的思想,是冒泡排序的改进型。快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列继续分区,直到剩一个元素，也就是这个分区的边界left = right。
代码实现
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
/**
* 负责以基准元素分区，左侧均小于基准元素值，右侧均大于基准元素值
*
* @param arr
* @param left 分区的左边界
* @param right 分区的右边界
* @return 基准元素在分区后的index
*/
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (right > left) {
while (arr[right] >= pivot && right > left) {
right--;
}
arr[left] = arr[right];
while (arr[left] <= pivot && right > left) {
left++;
}
arr[right] = arr[left];
}
// 退出循环时，left == right,这个元素就是基准元素最终的位置
arr[right] = pivot;
return right;
}
网友评论