该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。
JavaSE集合（已写）
JavaEE框架（未写）
虚拟机JVM运行时区域及垃圾回收（已写）
Java并发（未写）
计算机网络（已写）
八大经典排序算法原理及实现（已写）
一、冒泡排序
1.1 冒泡排序原理
冒泡排序算法应该是大家第一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：
- 第一轮从下标为 0 到 n-1 的元素.即（0，n-1）,依次比较相邻两个元素，把最大（或最小）的数移动到最右边位置，即下标为 n-1处
- 第二轮再从下标为 0 到 n-2 的元素.即（0，n-2），依次比较相邻两个元素，把最大（或最小）的数移动到 最右边-1 位置，即下标为 n-2 处
- 一值重复 n躺 即可达到排序效果
int[] bubbleSort(int[] arr){
// 因为需要重复n躺，所以 i < arr.length
for(int i = 0; i < arr.length; i++){
// 这里由于是将最大或最小的数放在右边，所以 j < arr.length - i
for(int j = 1; j < arr.length - i; j++){
// 如果前第一个数大于后一个数，则交换
if(a[j-1] > a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
return arr;
}
1.2 冒牌时间复杂度分析
- 这里嵌套两层 for 循环，外层循环 n 次；
- 内层最多时循环 n - 1次、最少循环 0 次，平均循环(n-1)/2；
- 所以循环体内总的比较交换次数为：n*(n-1) / 2 = (n^2-n)/2
按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)
冒泡排序及其复杂度分析
1.3 冒泡排序空间复杂度分析
空间复杂度就是在交换元素时那个临时变量所占的内存
- 最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
- 最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(N);
- 平均的空间复杂度为O(1)
1.4 冒泡排序算法的改进
给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：
6,1,2,3,4
1,2,3,4,6 此时 i = 0；
1,2,3,4,6 此时 i = 1；
1,2,3,4,6 此时 i = 2；
1,2,3,4,6 此时 i = 3；
我们发现第一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？
- 给定一个 整数型标识符 flag ,当某次外层循环中，内循环里没有发生相邻元素的交换，则表示当前数组已排序成功，直接跳出外层循环。
- 所以最好的情况时间复杂度为O(N)
// 改进的冒泡排序算法
int[] bubbleSort(int[] arr){
int flag ;
for(int i = 0; i < arr.length; i++){
flag = 0;
for(int j = 1; j < arr.length - i; j++){
if(a[j-1] > a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
flag = 1;
}
}
// flag = 0 ,则表示内层循环中，没有发生相邻元素的交换，即已排序，直接跳出外层循环
if(flag == 0)
break;
}
return arr;
}
1.4 稳定性分析
- 稳定性：排序后对于那些值相同的元素其相对位置没有发生变化
冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法
二、插入排序
插入排序是对冒泡排序的一种改进
2.1插入排序原理
插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
（图片来自这里）
int[] insertionSort(int[] a){
for (int i = 0; i < a.length-1; i++) {
// 第i+1个元素插入到前i个已排序数中
for(int j = i + 1; j >= 0; j--) {
if(a[j] < a[j-1]){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
return a;
}
2.2 时间复杂度分析
- 如上代码。两次for循环，第一层是循环 n 次；
- 第二层循环中，最好循环 1 次，最坏循环 n 次，平均循环（n-1）/2次
- 所以总的循环体内比较的平均次数为（n^2-n）/ 2，按照时间复杂度的计算规则，其平均时间时间复杂度为O(N)
2.3 空间复杂度分析
空间复杂度就是在交换元素时那个临时变量所占的内存
- 最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
- 最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
- 平均的空间复杂度为O(1)
2.4 插入排序的优化
插入排序的优化，有两种方案：
- 希尔插入排序
- 二分插入排序
文章后面会给出这两种排序算法
2.5 插入排序的稳定性
由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化
三、选择排序
3.1 选择排序原理
其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面
- 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
- 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
- 依次类推下去......
```
int[] selectionSort(int[] a,int n) {
for (int i = 0; i < a.length; i++) {
int min = a[i]; //每次循环默认第i个元素为最小值
int num = i; // num 用来记录未排序元素里面的最小值下标
for(int j = i+1; j < a.length; j++){
if(a[j] < min){
min = a[j];
num = j;
}
}
// num != i，则表示已在无排序元素里选到比a[i]更小的值
if(num != i){
a[num] = a[i];
a[i] = min;
}
}
return a;
}
```
3.2 选择排序时间复杂度
- 外层循环 n 次；
- 内层循环中，最坏循环 n-1 次，最好循环 0 次，平均循环 (n-1)/2 次
- 整个循环体中循环 (n^2 - n) / 2 次，所以平均时间复杂度为 O(N)
3.3 选择排序空间复杂度
空间复杂度就是在交换元素时那个临时变量所占的内存
- 最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
- 最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
- 平均的空间复杂度为O(1)
3.4 选择排序的优化
3.5 选择排序的稳定性
选择排序是不稳定的，比如 3 6 3 2 4，第一次外层循环中就会交换第一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化
四、希尔排序
希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法
4.1 希尔排序算法原理
其原理是将序列分割成若干子序列（由相隔某个增量的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：
- 以 32 43 24 18 49 28 10 59 18 41 序列为例
- 第一次 gap = 10 / 2 = 5；则从第6个元素开始，依次与前面相距间隔为5的元素比较
32 43 24 18 49 28 10 59 18 41 —> 28 43 24 18 49 32 10 59 18 41
28 43 24 18 49 32 10 59 18 41 —> 28 10 24 18 49 32 43 59 18 41
28 10 24 18 49 32 43 59 18 41 —> 28 10 24 18 49 32 43 59 18 41
28 10 24 18 49 32 43 59 18 41 —> 28 10 24 18 49 32 43 59 18 41
28 10 24 18 49 32 43 59 18 41 —> 28 10 24 18 41 32 43 59 18 49
- 这样第一趟就得到 28 10 24 18 41 32 43 59 18 49 的序列，后面再缩小 gap = gap / 2 = 2，同上述步骤一样依次与前面相距间隔为 2 的元素就行比较
int[] shellSort(int[] A, int n){
int gap = n/2;// 初始步长
while(gap > 0){
// 从数组下标为 gap的元素开始排序
for(int i = gap; i < n; i++){
// 每个元素只与自己组内的元素进行直接排序，组内相邻元素比较
for(int j = i-gap; j>=0 ; j -= gap){
if (A[j] > A[j+gap]) {
int temp = A[j+gap];
A[j+gap] = A[j];
A[j] = temp;
}
}
}
gap /= 2;
}
return A;
}
4.2 希尔排序时间复杂度分析
希尔排序的效率取决于增量值gap的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N1.3)，当然最好肯定是O(N)，最坏是O(N2)
4.3 希尔排序空间复杂度分析
空间复杂度就是在交换元素时那个临时变量所占的内存
- 最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
- 最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
- 平均的空间复杂度为O(1)
4.4 希尔排序的优化
4.5 希尔排序的稳定性
希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的
五、堆排序
5.1 什么是堆？
理解堆排序，就必须得先知道什么是堆？
- 堆一般指的是二叉堆，顾名思义，二叉堆是完全二叉树或者近似完全二叉树
二叉树的特点：
- 父结点的键值总是小于（大于）任何一个子结点
- 每一个结点的左子树和右子树都是一个二叉堆
当父节点的值总是大于子结点时为最大堆；反之为最小堆，下图就为一个二叉堆
5.1.1 堆的存储
一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)
5.1.2 堆调整
怎么将给定的数组序列按照堆的性质，调整为堆？
// 从节点i开始调整，n为节点总数 从0开始计算 i 的子节点为 2*i+1 和 2*i+2,父节点为(i-1)/2
void heapAdjust(int[] data, int i, int n) {
int temp = data[i];
int childLeft = 2 * i + 1;
int childRight = 2 * i + 2;
while (childLeft < n) {
// 先从两个子节点中选择最小的
if (childRight < n && data[childRight] < data[childLeft])
childLeft++;
// 如果子节点大于父节点，则退出
if (data[childLeft] >= temp)
break;
// 如果子节点小于父节点，则交换
else {
data[i] = data[childLeft];
i = childLeft;
childLeft = 2 * i + 1;
childRight = 2 * i + 2;
}
}
data[i] = temp;
}
5.2 建立堆
这里以建立最小堆为示例，
很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A[4] = 50的结点开始做堆调整，即从（n/2 - 1）位置处向上开始做堆调整：
// 建立最小堆
for (int i = n / 2 - 1; i >= 0; i--) {
// 调用堆调整函数
heapAdjust(A, i, n);
}
5.3 堆排序
- 堆排序其实就是将序列建立堆之后，将堆顶元素和堆尾第 n-i 位置元素交换，再做 (0,n-i) 堆调整；
- 循环 n 次之后，即完成排序;
- 由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序
for (int i = 1; i < n; i++) {
// 调换第一个数和最后一个数
swap(A, 0, n - i);
// 调整堆
heapAdjust(A, 0, n - i);
}
5.4 堆排序整个完整代码：
int[] heapSort(int[] A, int n) {
// 首先建立最小堆，父节点若大于等于0，则调整堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapAdjust(A, i, n);
}
for (int i = 1; i < n; i++) {
// 调换第一个数和最后一个数
swap(A, 0, n - i);
// 调整堆
heapAdjust(A, 0, n - i);
}
return A;
}
// 从节点i开始调整，n为节点总数 从0开始计算 i的子节点为 2*i+1 和 2*i+2,父节点为(i-1)/2
void heapAdjust(int[] data, int i, int n) {
int temp = data[i];
int childLeft = 2 * i + 1;
int childRight = 2 * i + 2;
while (childLeft < n) {
// 先从两个子节点中选择最小的
if (childRight < n && data[childRight] < data[childLeft])
childLeft++;
// 如果子节点大于父节点，则退出
if (data[childLeft] >= temp)
break;
// 如果子节点小于父节点，则交换
else {
data[i] = data[childLeft];
i = childLeft;
childLeft = 2 * i + 1;
childRight = 2 * i + 2;
}
}
data[i] = temp;
}
void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
5.5 堆排序的时间复杂度
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。
5.6 堆排序的空间复杂度
空间复杂度就是在交换元素时那个临时变量所占的内存
- 最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
- 最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
- 平均的空间复杂度为O(1)
5.7 堆排序的优化
5.8 堆排序的稳定性
由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换，使得第一个5和第三个5的相对位置发生变化
六、归并排序
6.1 归并排序的原理
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
- 顾名思义，我们先看看递归操作，其目的是为了将序列一直划分到 n 个子序列，再将相邻两个子序列进行合并
// 划分序列
void sort(int[] data, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// 递归划分序列
sort(data, left, middle);
sort(data, middle + 1, right);
// 合并
merge(data, middle, left, right);
}
}
-
递归理解可以看这张图：
-
再看合并操作，将两个已排序的两个数组合并到一个数组里。着了采用了一个临时数组来存储元素，所以会导致该排序算法的空间复杂度为O(N)
// 合并相邻两个数组 void merge(int[] data, int middle, int left, int right) { int leftIndex = left; // 定义左边数组的第一个下标 int rightIndex = middle + 1; // 定义右边数组的第一个下标 int[] tempArray = new int[right - left + 1]; // 定义一个暂时存储的数组 int tempIndex = 0; // 定义暂存数组的下标 while (leftIndex <= middle && rightIndex <= right) { if (data[leftIndex] <= data[rightIndex]) { tempArray[tempIndex++] = data[leftIndex++]; } else { tempArray[tempIndex++] = data[rightIndex++]; } } // 剩下的直接放入 while (leftIndex <= middle) { tempArray[tempIndex++] = data[leftIndex++]; } while (rightIndex <= right) { tempArray[tempIndex++] = data[rightIndex++]; } // 返回数组给data int temp = 0; while ((left + temp) <= right) { data[left + temp] = tempArray[temp]; temp++; } }
6.2 归并排序时间复杂度分析
- 因为不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )
6.3 归并排序空间复杂度分析
- 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)
- 以时间换空间：网上很多blog分享空间复杂度只有O(1)的归并排序法；因为传统的归并排序所消耗的空间主要是在归并函数（把两个有序的函数合并成一个有序的函数），所以如果要让空间复杂度为 O(1) ，那么也只能在归并函数中做文章了。其主要思想就是借助于快速排序（其实就是相当于归并函数被快速排序函数替换了）；这样的方法虽然可以减少内存的消耗，但是却会在时间上带来损失，因为这样时间复杂度却变成了 O(n^2) 了；所以这种方法并不是一个两全其美的idea；
6.4 归并排序的稳定性
- 归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法
七、快速排序
快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面挖坑填数方法后，能快速写出、快速排序。
7.1 快速排序原理
- 先从序列中选取一个数做为基准数；
- 再遍历原序列，大于这个基准数的放在右边，小于这个基准数的方法在左边
- 再对左右两边分别进行上述两个步骤，直到各个区间只有一个数
其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式挖坑填数分治法
7.2 挖坑填数分治法
对于序列： 72 6 57 88 60 42 83 73 48 85
- 初始时，i = 0; j = 9; X = a[i] = 72
- 由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
- 从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
数组变为：48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：
- 从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
- 从i开始向后找，当i=5时，由于i==j退出。
- 此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了
挖坑填数法总结
- i =L; j = R; 将基准数挖出形成第一个坑a[i]。
- j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
- i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
- 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
public int[] quickSort(int[] A, int n) {
// write code here
sort(A, 0, n - 1);
return A;
}
void sort(int[] data, int left, int right) {
if(left < right){
int i = left;
int j = right;
int x = data[i];// data[i]即 data的第一个坑
while(i < j){
// 先从右到左找小于 x 的数来填坑 data[i]
while(i < j && data[j] >= x)
j--;
if (i < j) {
// data[j] 填入到 坑中，且data[j]形成新坑
data[i++] = data[j];
}
// 再从左到有找大于 x 的数来填坑 data[j]
while(i < j && data[i] < x)
i++;
if (i < j) {
// data[j] 填入到 坑中，且data[i]形成新坑
data[j--] = data[i];
}
}
// 当 i=j 时，退出while循环，此时将 x 填入到坑data[i]中
data[i] = x;
sort(data, left, i-1);
sort(data, i+1, right);
}
}
7.3 快速排序时间复杂度
- 在最优的情况下，快速排序算法的时间复杂度为O(NlogN)
- 在最坏的情况下，待排序的序列为正序或者逆序，快速排序算法的时间复杂度为O(N)
7.4 快速排序空间复杂度
空间复杂度，主要是递归造成的栈空间的使用:
- 最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn);
- 最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n);
- 平均情况，空间复杂度也为O(logn)。
7.5 快速排序的优化
快速排序的优化主要在于基准数的选取
7.6 快速排序的稳定性
快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定
八、二分排序
8.1 二分查找排序原理
前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
具体步骤，设数组为a[0…n]：
- 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始）
- 从无序区中取出第一个元素，即a[i]，使用二分查找算法在有序区中查找要插入的位置索引j。
- 将a[j]到a[i-1]的元素后移，并将a[i]赋值给a[j]。
- 重复步骤2~3，直到无序区元素为0个。
static void binarySort(int[] arr, int n){
for (int i = 1; i < n; i++){
int temp = arr[i];
int low = 0; // 有序区域最小位置
int high = i-1; // 有序区域最大位置
int mid = -1;
// 二分查找插入位置
while (low <= high){
mid = low + (high - low)/ 2;
if (temp >= arr[mid]) { // 相等的元素也是插在后面
low = mid + 1;
}else {
high = mid - 1;
}
}
// 向后移动数据
for (int j = i - 1; j >= low; j--)
arr[j+1] = arr[j];
arr[low] = temp; // 插入temp
}
}
8.2 二分插入排序的时间复杂度
二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：
- 最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n 。即O(log2n)
- 最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)
- 渐进时间复杂度（平均时间复杂度）：O(n^2)
8.3 二分插入排序的空间复杂度
- 从实现原理可知，二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)
8.4 二分插入排序的稳点性
二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的
各个排序算法的比较
各个算法的联系
最后感谢以下内容
白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序
