一、冒泡排序
1.1 冒泡排序基础【必会知识】
冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
冒泡排序的步骤是比较固定的：
1>比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2>每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
3>针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。
此处引用网上一张比较经典的gif来展示冒泡排序的整个过程：
冒泡排序的常规实现代码如下：
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
1.2 冒泡排序优化
上个章节介绍了冒泡排序的常规实现，但是这种最简单的排序是存在着不必要的比较动作的。稍微修改上述代码，就可以查看每次比较后的结果：
int[ ] array=new int[ ]{5,2,3,9,4};
for(int i=0;i<array.length-1;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
for(int k=0;k<array.length;k++){
System.out.print(array[k]+" ");
}
System.out.println();
}
}
该代码的输出结果为：
第 1 趟，第 1 次比较后的结果：
2 5 3 9 4
第 1 趟，第 2 次比较后的结果：
2 3 5 9 4
第 1 趟，第 3 次比较后的结果：
2 3 5 9 4
第 1 趟，第 4 次比较后的结果：
2 3 5 4 9
第 2 趟，第 1 次比较后的结果：
2 3 5 4 9
第 2 趟，第 2 次比较后的结果：
2 3 5 4 9
第 2 趟，第 3 次比较后的结果：
2 3 4 5 9
第 3 趟，第 1 次比较后的结果：
2 3 4 5 9
第 3 趟，第 2 次比较后的结果：
2 3 4 5 9
第 4 趟，第 1 次比较后的结果：
2 3 4 5 9
从上面的测试结果可以看出，从第2趟第3次比较后，数组元素已经处于有序状态，此后所有的比较都不必进行。
1.2.1 外循环优化
第一种优化就基于上面的测试结果来进行，如果某次比较过程中，发现没有任何元素移动，则不再进行接下来的比较。具体的做法是在每趟比较时，引入一个boolean型变量isSwap，来判断下次比较还有没有必要进行。示例代码如下：
int[ ] array=new int[ ]{5,2,3,9,4};
for(int i=0;i<array.length-1;i++){
boolean isSwap=false;
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
isSwap=true;
}
System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
for(int k=0;k<array.length;k++){
System.out.print(array[k]+" ");
}
System.out.println();
}
if(!isSwap){
break;
}
}
测试结果如下：
第 1 趟，第 1 次比较后的结果：
2 5 3 9 4
第 1 趟，第 2 次比较后的结果：
2 3 5 9 4
第 1 趟，第 3 次比较后的结果：
2 3 5 9 4
第 1 趟，第 4 次比较后的结果：
2 3 5 4 9
第 2 趟，第 1 次比较后的结果：
2 3 5 4 9
第 2 趟，第 2 次比较后的结果：
2 3 5 4 9
第 2 趟，第 3 次比较后的结果：
2 3 4 5 9
第 3 趟，第 1 次比较后的结果：
2 3 4 5 9
第 3 趟，第 2 次比较后的结果：
2 3 4 5 9
从上面的测试结果可以看出，已经对排序过程进行了优化，因为没有进行第4趟比较。也许有人会有疑问“第2趟比较结束后，数组已经有序了，为什么还要进行第3次比较”？之所以对此有疑问，可能是没太清楚isSwap变量的作用，该变量的作用是“假如本趟比较过程中没有交换发生，则不必进行下一趟比较”，在第2趟比较过程中，发生了交换动作，所以第3趟比较仍会进行。
1.2.2 内循环优化
第一种优化方式比较容易理解，但同时也存在着缺点：某趟比较只要开始，哪怕数组元素已经有序，也要把该趟的所有次比较完。也就是说，第一种优化方式，只能在“趟”的级别上优化。
第二种优化方式，也就是要实现在“次”的级别进行优化，其思路是“记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可”。示例代码为：
int[ ] array = new int[ ]{5,2,3,7,9};
int position = array.length - 1;
for(int i = 0;i<array.length-1;i++){
boolean isSwap = false;
int newPosition = 0;
for(int j = 0;j<position;j++){
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
isSwap = true;
newPosition = j;
}
System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
for(int k = 0;k<array.length;k++){
System.out.print(array[k]+" ");
}
System.out.println();
}
if(!isSwap){
break;
}
position = newPosition;
}
测试结果如下：
第 1 趟，第 1 次比较后的结果：
2 5 3 7 9
第 1 趟，第 2 次比较后的结果：
2 3 5 7 9
第 1 趟，第 3 次比较后的结果：
2 3 5 7 9
第 1 趟，第 4 次比较后的结果：
2 3 5 7 9
第 2 趟，第 1 次比较后的结果：
2 3 5 7 9
从上面的测试结果可以看出，在第2趟进行了1次比较后，数组元素已经处于有序状态，此时便不再进行接下来的比较。
1.2.3 双向遍历
上面的两种优化都是单向遍历比较的，然而在很多时候，遍历的过程可以从两端进行，从而提升效率。因此在冒泡排序中，其实也可以进行双向循环，正向循环把最大元素移动到数组末尾，逆向循环把最小元素移动到数组首部。该种排序方式也叫双向冒泡排序，也叫鸡尾酒排序。
关于此种排序优化，示例代码如下：
static void bubbleSort(int[] array) {
int arrayLength = array.length;
int preIndex = 0;
int backIndex = arrayLength - 1;
while(preIndex < backIndex) {
preSort(array, arrayLength, preIndex);
preIndex++;
if (preIndex >= backIndex) {
break;
}
backSort(array, backIndex);
backIndex--;
}
}
static void preSort(int[] array, int length, int preIndex) {
for (int i = preIndex + 1; i < length; i++) {
if (array[preIndex] > array[i]) {
swap(array, preIndex, i);
}
}
}
static void backSort(int[] array, int backIndex) {
for (int i = backIndex - 1; i >= 0; i--) {
if (array[i] > array[backIndex]) {
swap(array, i, backIndex);
}
}
}
static void swap (int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
1.3 冒泡排序的稳定性、复杂度和适用场景
1.3.1 稳定性
在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。
1.3.2 时间复杂度
如果待排序序列的初始状态恰好是我们希望的排序结果(如升序或降序)，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
冒泡排序最好的时间复杂度为O(n)。
如果待排序序列是反序(如我们希望的结果是升序，待排序序列是降序)的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
冒泡排序的最坏时间复杂度为O(n2)。
综上，因此冒泡排序总的平均时间复杂度为O(n2)。
1.3.3 适用场景
冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。
二、选择排序
2.1 选择排序基础【必会知识】
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为0。
选择排序的步骤：
1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2>再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。
3>重复第二步，直到所有元素均排序完毕。
此处引用网上一张比较经典的gif来展示选择排序的整个过程：
用代码来实现上述过程，示例如下：
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
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;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
2.2 选择排序优化
2.2.1 选择排序优化图示
选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。第一次选择最大值与最小值，过程如下：
2.2.2 选择排序优化实现
示例代码如下：
int left = 0;
int right = len - 1;
while (left < right){
int min = left;
int max = right;
for (int i = left; i <= right; i++){
if (arr[i] < arr[min])
min = i;
if (arr[i] > arr[max])
max = i;
}
int temp = arr[max];
arr[max] = arr[right];
arr[right] = temp;
if (min == right)
min = max;
temp = arr[min];
arr[min] = arr[left];
arr[left] = temp;
left++;
right--;
}
2.3 选择排序的稳定性、复杂度及适用场景
2.3.1 稳定性
在选择排序中，每趟都会选出最大元素与最小元素，然后与两端元素交换，此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。如[5,3,5,2,9]，在array[0]与array[3]元素交换时，序列的稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。
2.3.2 时间复杂度
选择排序的时间复杂度为O(n2)。
2.3.3 适用场景
待排序序列中，元素个数较少时。
三、插入排序
3.1 插入排序基础【必会知识】
插入排序也是一种常见的排序算法，插入排序的思想是：将初始数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。
插入排序的步骤如下：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。
假如有[5,2,3,9,4,7]六个元素，下面就以排序过程中的一个步骤（此时有序部分为[2,3,5,9]，无序部分为[4,7]，接下来要把无序部分的“4”元素插入到有序部分），来展示一下插入排序的运行过程。
- 首先，原始的数组元素是这样的。
其中，浅绿色代表有序部分，黄色代表无序部分。 - 在无序部分中挑出要插入到有序部分中的元素。
- 将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 9，所以9向后移，4向前移。
- 继续将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 5，所以5向后移，4继续向前移。
- 继续将4与3比较。由于4 > 3，所以不再向前比较，插入到当前位置。
- 此时有序部分，由[2,3,5,9]变成[2,3,4,5,9]。
将上述过程用代码实现，示例如下：
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
3.2 插入排序优化
插入排序的优化方式一般有两种：折半插入排序和2-路插入排序。
3.2.1 折半插入排序
该类优化有二分的思想，是在将待排序的元素与有序部分的元素比较时，不再挨个比较，而是用二分折中的方式进行比较，加快比较效率。示例代码如下：
int j,low,mid,high,temp;
for(int i = 1;i<n;i++){
low = 0;
high = i-1;
temp = arr[i];
while(low <= high){
mid = (low+high)/2;
if(arr[mid]>temp){
high = mid-1;
}else{
low = mid+1;
}
}
for(j = i-1;j >= high+1;j--)
{
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
3.2.2 2-路插入排序
该中方式是在折半插入排序的基础上再进行改进的算法，其目的是减少排序过程中移动记录的次数，付出的代价是n个记录的辅助空间。
假设原数组为 arr，另设一个相同类型的数组 tempArr，先将 arr[0] 赋值给 tempArr[0]，并将tempArr[0] 看成是在有序序列中处于中间位置的元素，然后从 arr[1] 起一次插入到 tempArr[1] 之前或之后的有序序列中。
先将待插元素和tempArr[0] 做比较，若小于tempArr[0]，则插入tempArr[0] 之前的有序部分；反之，将其插入tempArr[0] 之后的有序部分中。在实现算法时，可将tempArr看成一个循环数组，并设 first 和last分别指向排序过程中得到的有序序列中的第一个元素和最后一个元素在tempArr中的位置。示例代码如下：
int j, first, last, mid;
int[ ] tempArr =new int[len];
tempArr[0] = arr[0];
first = last = 0;
for(int i = 1; i<len; i++){
if(first > last){
j = len;
}else{
j = 0;
}
mid = ((first+last+j)/2)%len;
if(arr[i] < tempArr[mid]){
j = first;
first = (first-1+len)%len;
while(arr[i] > tempArr[j]){
tempArr[(j-1+len)%len] = tempArr[j];
j = j+1;
}
tempArr[(j-1+len)%len] = arr[i];
}else{
j = last;
last++;
while(arr[i] < tempArr[j]){
tempArr[(j+1)%len] = tempArr[j];
j = (j-1+len)%len;
}
tempArr[(j+1)%len] = arr[i];
}
}
for(int i = 0; i < len; i++){
arr[i] = tempArr[(first+i)%len];
}
3.3 插入排序的稳定性、复杂度和适用场景
3.3.1 稳定性
在使用插入排序时，元素从无序部分移动到有序部分时，必须是不相等(大于或小于)时才会移动，相等时不处理，所以直接插入排序是稳定的。
3.3.2 时间复杂度
在插入排序中，当待排序序列是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n- 1次，时间复杂度为O(n)。
最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n2)。
平均来说，array[1…j-1]中的一半元素小于array[j]，一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是O(n2)。
3.3.3 适用场景
待排序序列的元素个数不多(<=50)，且元素基本有序。
四、快速排序
4.1 快速排序基础【必会知识】
快速排序也是一种较为基础的排序算法，其效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一趟只能选出一个最值，有n个元素最多就要执行n - 1趟比较。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
快速排序的思想是：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
快速排序的步骤如下：
1>先从数列中取出一个数作为基准数。
2>分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3>再对左右区间重复第二步，直到各区间只有一个数。
快排的不同版本，演进过程示例：
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process1(arr, 0, arr.length - 1);
}
public static void process1(int[] arr, int L, int R) {
if (L >= R) {
return;
}
int M = partition(arr, L, R);
process1(arr, L, M - 1);
process1(arr, M + 1, R);
}
public static int partition(int[] arr, int L, int R) {
if (L > R) {
return -1;
}
if (L == R) {
return L;
}
int lessEqual = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R]) {
swap(arr, index, ++lessEqual);
}
index++;
}
swap(arr, ++lessEqual, R);
return lessEqual;
}
public static void quickSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process2(arr, 0, arr.length - 1);
}
public static void process2(int[] arr, int L, int R) {
if (L >= R) {
return;
}
int[] equalArea = netherlandsFlag(arr, L, R);
process2(arr, L, equalArea[0] - 1);
process2(arr, equalArea[1] + 1, R);
}
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) {
return new int[] { -1, -1 };
}
if (L == R) {
return new int[] { L, R };
}
int less = L - 1;
int more = R;
int index = L;
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, index++, ++less);
} else {
swap(arr, index, --more);
}
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
public static void quickSort3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process3(arr, 0, arr.length - 1);
}
public static void process3(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
process3(arr, L, equalArea[0] - 1);
process3(arr, equalArea[1] + 1, R);
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
在选择基准值的时候，越靠近中间，性能越好；越靠近两边，性能越差。第三版随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件。把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N。那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望。
时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。
4.2 快速排序优化
4.2.1 三数取中
该方法指的是选取基准值时，不再取固定位置(如第一个元素、最后一个元素)的值，因为这种固定取值的方式在面对随机输入的数组时，效率是非常高的。但是一旦输入数据是有序的，使用固定位置取值，效率就会非常低。因此此时引入了三数取中，即在数组中随机选出三个元素，然后取三者的中间值做为基准值。
4.2.2 插入排序
当待排序序列的长度分割到一定大小(如 < 10)后，使用插入排序。
4.2.3 相等元素聚集（上个小节中的第二版快排）
在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割。
4.3 快速排序的稳定性、复杂度和适用场景
4.3.1 稳定性
在使用快速排序时，每次元素分堆都要选择基准因子。此时，基准因子两边都有可能出现和基准因子相同的元素，如序列[1,3,2,4,3,4,6,3]，如果选择了array[4]作为基准因子，那么array[1]和array[7]势必会被分到基准因子的同一侧，序列的稳定性被破坏。所以，快速排序是一种不稳定的排序算法。
4.3.2 时间复杂度
快速排序的时间复杂度是O(nlogn)【上小节第三版的时间复杂度】。
4.3.3 适用场景
快速排序的适用场景是：待排序序列元素较多，并且元素较无序。
五、希尔排序
5.1 希尔排序基础
希尔排序又称为缩小增量排序，是对之前介绍的插入排序的一种优化版本，优化的地方在于：不用每次插入一个元素时，就和序列中有序部分中的所有元素进行比较。
该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于序列元素总数）作为间隔，所有距离为increment的元素放在同一个逻辑数组中，在每一个逻辑数组中分别实行直接插入排序。然后缩小间隔increment，重复上述逻辑数组划分和排序工作。直到最后取increment=1，将所有元素放在同一个数组中排序为止。
其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤：
1>选increment，划分逻辑分组，组内进行直接插入排序。
2>不断缩小increment，继续组内进行插入排序。
3>直到increment=1，在包含所有元素的序列内进行直接插入排序。
5.1.1 排序过程图示
1>假如有[5,2,3,9,4,7]六个元素，第一趟取increment的方法是：6/3向下取整+1=3。将整个数据列划分为间隔为3的3个逻辑分组，然后对每一个逻辑分组执行直接插入排序，相当于对整个数组执行了部分排序调整。
2>第二趟将间隔increment= increment/3向下取整+1=2，将整个数组划分为2个间隔为2的逻辑分组，分别进行排序。
3>第3趟继续缩小间隔。间隔缩小为increment= increment/3向下取整+1=1，当增量为1的时候，实际上就是把整个数列作为一个逻辑分组进行插入排序。
5.1.2 排序过程实现
上述图示对应的代码实现，示例如下：
int increment = len;
int temp;
while (increment > 1){
increment = increment/3 + 1;
for (int i = increment; i < len; ++i) {
if (arr[i-increment] > arr[i]) {
temp = arr[i];
int j = i-increment;
while (j >= 0 && arr[j] > temp) {
arr[j+increment] = arr[j];
j -= increment;
}
arr[j+increment] = temp;
}
}
}
从上述代码可以看出，希尔排序的代码与直接插入排序的代码十分相似。因为希尔排序本就是直接插入排序的优化版本，不同的地方就是间隔慢慢减成1，直接插入排序的间隔一直就是1。
5.2 希尔排序优化
由于希尔排序是基于插入排序的，所以在插入排序中也可运用直接插入排序中的优化方式，此处以二分折中的方式来优化希尔排序，示例代码如下：
int increment = len;
int j,temp,low,mid,high;
while (increment > 1){
increment = increment/3 + 1;
for (int i = increment; i < len; ++i) {
low = 0;
high = i-1;
temp = arr[i];
while(low <= high){
mid = (low+high)/2;
if(arr[mid]>temp){
high = mid-1;
}else{
low = mid+1;
}
}
j = i-increment;
while(j >= high+1){
arr[j+increment] = arr[j];
j -= increment;
}
arr[j+increment] = temp;
}
}
5.3 希尔排序的稳定性、复杂度及适用场景
5.3.1 稳定性
希尔排序是直接插入排序的优化版，在排序过程中，会根据间隔将一个序列划分为不同的逻辑分组，在不同的逻辑分组中，有可能将相同元素的相对位置改变。如[2,2,4,1]，按间隔为2，降序排序，前两个元素的相对位置就会改变。因此，希尔排序是不稳定的排序方式。
5.3.2 时间复杂度
希尔排序在最坏情况下的时间复杂度为O(n2)，平均情况下的时间复杂度为O(n1.3)。
5.3.3 适用场景
待排序序列元素较少时。
