一、替换排序
所谓替换，就是序列中任意两个元素进行比拟，依据比拟后果来替换各自在序列中的地位，以此达到排序的目标。
- 冒泡排序
冒泡排序是一种简略的替换排序算法，以升序排序为例，其核心思想是：
从第一个元素开始，比拟相邻的两个元素。如果第一个比第二个大，则进行替换。
轮到下一组相邻元素，执行同样的比拟操作，再找下一组，直到没有相邻元素可比拟为止，此时最初的元素应是最大的数。
除了每次排序失去的最初一个元素，对残余元素反复以上步骤，直到没有任何一对元素须要比拟为止。
用 Java 实现的冒泡排序如下
public void bubbleSortOpt(int[] arr) {if(arr == null) {throw new NullPoniterException();
}
if(arr.length < 2) {return;}
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {for(int j = 0; j < arr.length - i - 1; j++) {if(arr[j] > arr[j + 1]) {temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}- 疾速排序
疾速排序的思维很简略，就是先把待排序的数组拆成左右两个区间，右边都比两头的基准数小，左边都比基准数大。接着左右两边各自再做同样的操作，实现后再拆分再持续，始终到各区间只有一个数为止。
举个例子，当初我要排序 4、9、5、1、2、6 这个数组。个别取首位的 4 为基准数，第一次排序的后果是：
2、1、4、5、9、6
可能有人感觉奇怪，2 和 1 替换下地位也能满足条件，为什么 2 在首位？这其实由理论的代码实现来决定，并不影响之后的操作。以 4 为分界点，对 2、1、4 和 5、9、6 各自排序，失去：
1、2、4、5、9、6
不必管右边的 1、2、4 了，将 5、9、6 拆成 5 和 9、6，再排序，至此后果为：
1、2、4、5、6、9
为什么把快排划到替换排序的领域呢？因为元素的挪动也是靠替换地位来实现的。算法的实现须要用到递归（拆分区间之后再对每个区间作同样的操作）
用 Java 实现的疾速排序如下
public void quicksort(int[] arr, int start, int end) {if(start < end) {
// 把数组中的首位数字作为基准数
int stard = arr[start];
// 记录须要排序的下标
int low = start;
int high = end;
// 循环找到比基准数大的数和比基准数小的数
while(low < high) {
// 左边的数字比基准数大
while(low < high && arr[high] >= stard) {high--;}
// 应用左边的数替换右边的数
arr[low] = arr[high];
// 右边的数字比基准数小
while(low < high && arr[low] <= stard) {low++;}
// 应用右边的数替换左边的数
arr[high] = arr[low];
}
// 把标准值赋给下标重合的地位
arr[low] = stard;
// 解决所有小的数字
quickSort(arr, start, low);
// 解决所有大的数字
quickSort(arr, low + 1, end);
}
}二、插入排序
插入排序是一种简略的排序办法，其根本思维是将一个记录插入到曾经排好序的有序表中，使得被插入数的序列同样是有序的。依照此法对所有元素进行插入，直到整个序列排为有序的过程。
- 间接插入排序
间接插入排序就是插入排序的粗犷实现。对于一个序列，选定一个下标，认为在这个下标之前的元素都是有序的。将下标所在的元素插入到其之前的序列中。接着再选取这个下标的后一个元素，持续反复操作。直到最初一个元素实现插入为止。咱们个别从序列的第二个元素开始操作。
用 Java 实现的算法如下：
public void insertSort(int[] arr) {
// 遍历所有数字
for(int i = 1; i < arr.length - 1; i++) {
// 以后数字比前一个数字小
if(arr[i] < arr[i - 1]) {
int j;
// 把以后遍历的数字保存起来
int temp = arr[i];
for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
// 前一个数字赋给后一个数字
arr[j + 1] = arr[j];
}
// 把长期变量赋给不满足条件的后一个元素
arr[j + 1] = temp;
}
}
}- 希尔排序
某些状况下间接插入排序的效率极低。比方一个曾经有序的升序数组，这时再插入一个比最小值还要小的数，也就意味着被插入的数要和数组所有元素比拟一次。咱们须要对间接插入排序进行改良。
怎么改良呢？后面提过，插入排序对曾经排好序的数组操作时，效率很高。因而咱们能够试着先将数组变为一个绝对有序的数组，而后再做插入排序。
希尔排序能实现这个目标。希尔排序把序列按下标的肯定增量（步长）分组，对每组别离应用插入排序。随着增量（步长）缩小，始终到一，算法完结，整个序列变为有序。因而希尔排序又称放大增量排序。
一般来说，首次取序列的一半为增量，当前每次减半，直到增量为一。
用 Java 实现的算法如下：
public void shellSort(int[] arr) {
// gap 为步长，每次减为原来的一半。for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 对每一组都执行间接插入排序
for (int i = 0 ;i < gap; i++) {
// 对本组数据执行间接插入排序
for (int j = i + gap; j < arr.length; j += gap) {// 如果 a[j] < a[j-gap]，则寻找 a[j] 地位，并将前面数据的地位都后移
if (arr[j] < arr[j - gap]) {
int k;
int temp = arr[j];
for (k = j - gap; k >= 0 && arr[k] > temp; k -= gap) {arr[k + gap] = arr[k];
}
arr[k + gap] = temp;
}
}
}
}
}三、抉择排序
抉择排序是一种简略直观的排序算法，首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位，而后，再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。以此类推，直到所有元素均排序结束。
- 简略抉择排序
抉择排序思维的暴力实现，每一趟从未排序的区间找到一个最小元素，并放到第一位，直到全副区间有序为止。
用 Java 实现的算法如下：
public void selectSort(int[] arr) {
// 遍历所有的数
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
// 把以后遍历的数和前面所有的数进行比拟，并记录下最小的数的下标
for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {
// 记录最小的数的下标
minIndex = j;
}
}
// 如果最小的数和以后遍历的下标不统一，则替换
if (i != minIndex) {int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}- 堆排序
咱们晓得，对于任何一个数组都能够看成一颗齐全二叉树。堆是具备以下性质的齐全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
大顶堆，映射为数组，就是 [50, 45, 40, 20, 25, 35, 30, 10, 15]。能够发现第一个下标的元素就是最大值，将其与开端元素替换，则开端元素就是最大值。所以堆排序的思维能够演绎为以下两步：
反复以上两个步骤，直到没有元素可操作，就实现排序了。
咱们须要把一个一般数组转换为大顶堆，调整的起始点是最初一个非叶子结点，而后从左至右，从下至上，持续调整其余非叶子结点，直到根结点为止。
/**
* 转化为大顶堆
* @param arr 待转化的数组
* @param size 待调整的区间长度
* @param index 结点下标
*/
public void maxHeap(int[] arr, int size, int index) {
// 左子结点
int leftNode = 2 * index + 1;
// 右子结点
int rightNode = 2 * index + 2;
int max = index;
// 和两个子结点别离比照，找出最大的结点
if (leftNode < size && arr[leftNode] > arr[max]) {max = leftNode;}
if (rightNode < size && arr[rightNode] > arr[max]) {max = rightNode;}
// 替换地位
if (max != index) {int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
// 因为替换地位后有可能使子树不满足大顶堆条件，所以要对子树进行调整
maxHeap(arr, size, max);
}
}
/**
* 堆排序
* @param arr 待排序的整型数组
*/
public static void heapSort(int[] arr) {
// 开始地位是最初一个非叶子结点，即最初一个结点的父结点
int start = (arr.length - 1) / 2;
// 调整为大顶堆
for (int i = start; i >= 0; i--) {SortTools.maxHeap(arr, arr.length, i);
}
// 先把数组中第 0 个地位的数和堆中最初一个数替换地位，再把后面的解决为大顶堆
for (int i = arr.length - 1; i > 0; i--) {int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeap(arr, i, 0);
}
}四、归并排序
归并排序是建设在归并操作上的一种无效，稳固的排序算法。该算法采纳分治法的思维，是一个十分典型的利用。归并排序的思路如下：
- 将 n 个元素分成两个各含 n/2 个元素的子序列
- 借助递归，两个子序列别离持续进行第一步操作，直到不可再分为止
- 此时每一层递归都有两个子序列，再将其合并，作为一个有序的子序列返回上一层，再持续合并，全副实现之后失去的就是一个有序的序列
关键在于两个子序列应该如何合并。假如两个子序列各自都是有序的，那么合并步骤就是：
- 创立一个用于寄存后果的长期数组，其长度是两个子序列合并后的长度
- 设定两个指针，最后地位别离为两个曾经排序序列的起始地位
- 比拟两个指针所指向的元素，抉择绝对小的元素放入长期数组，并挪动指针到下一地位
- 反复步骤 3 直到某一指针达到序列尾
- 将另一序列剩下的所有元素间接复制到合并序列尾
用 Java 实现的归并排序如下：
/**
* 合并数组
*/
public static void merge(int[] arr, int low, int middle, int high) {
// 用于存储归并后的长期数组
int[] temp = new int[high - low + 1];
// 记录第一个数组中须要遍历的下标
int i = low;
// 记录第二个数组中须要遍历的下标
int j = middle + 1;
// 记录在长期数组中寄存的下标
int index = 0;
// 遍历两个数组，取出小的数字，放入长期数组中
while (i <= middle && j <= high) {
// 第一个数组的数据更小
if (arr[i] <= arr[j]) {
// 把更小的数据放入长期数组中
temp[index] = arr[i];
// 下标向后挪动一位
i++;
} else {temp[index] = arr[j];
j++;
}
index++;
}
// 解决残余未比拟的数据
while (i <= middle) {temp[index] = arr[i];
i++;
index++;
}
while (j <= high) {temp[index] = arr[j];
j++;
index++;
}
// 把长期数组中的数据从新放入原数组
for (int k = 0; k < temp.length; k++) {arr[k + low] = temp[k];
}
}
/**
* 归并排序
*/
public static void mergeSort(int[] arr, int low, int high) {int middle = (high + low) / 2;
if (low < high) {
// 解决右边数组
mergeSort(arr, low, middle);
// 解决左边数组
mergeSort(arr, middle + 1, high);
// 归并
merge(arr, low, middle, high);
}
}五、基数排序
基数排序的原理是将整数按位数切割成不同的数字，而后按每个位数别离比拟。为此须要将所有待比拟的数值对立为同样的数位长度，数位有余的数在高位补零。
应用 Java 实现的基数排序：
/**
* 基数排序
*/
public static void radixSort(int[] arr) {
// 寄存数组中的最大数字
int max = Integer.MIN_VALUE;
for (int value : arr) {if (value > max) {max = value;}
}
// 计算最大数字是几位数
int maxLength = (max + "").length();
// 用于长期存储数据
int[][] temp = new int[10][arr.length];
// 用于记录在 temp 中相应的下标寄存数字的数量
int[] counts = new int[10];
// 依据最大长度的数决定比拟次数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
// 每一个数字别离计算余数
for (int j = 0; j < arr.length; j++) {
// 计算余数
int remainder = arr[j] / n % 10;
// 把以后遍历的数据放到指定的数组中
temp[remainder][counts[remainder]] = arr[j];
// 记录数量
counts[remainder]++;
}
// 记录取的元素须要放的地位
int index = 0;
// 把数字取出来
for (int k = 0; k < counts.length; k++) {
// 记录数量的数组中以后余数记录的数量不为 0
if (counts[k] != 0) {
// 循环取出元素
for (int l = 0; l < counts[k]; l++) {arr[index] = temp[k][l];
// 记录下一个地位
index++;
}
// 把数量置空
counts[k] = 0;
}
}
}
}六、八种排序算法的总结
排序法 最好情景 均匀工夫 最差情景 稳定度 空间复杂度
冒泡排序 O(n) O(n^2) O(n^2) 稳固 O(1)
疾速排序 O(nlogn) O(nlogn) O(n^2) 不稳固 O(nlogn)
间接插入排序 O(n) O(n^2) O(n^2) 稳固 O(1)
希尔排序 不稳固 O(1)
间接抉择排序 O(n^2) O(n^2) O(n^2) 不稳固 O(1)
堆排序 O(nlogn) O(nlogn) O(nlogn) 不稳固 O(nlogn)
归并排序 O(nlogn) O(nlogn) O(nlogn) 稳固 O(n)
关键词：java 培训