一、排序算法阐述
算法里边最常用也是最基本的就是排序算法和查找算法了，本文主要讲解算法里边最经典的十大排序算法。在这里我们根据他们各自的实现原理以及效率将十大排序算法分为两大类：
非线性比较类排序：非线性是指算法的时间复杂度不能突破(nlogn)，元素之间通过比较大小来决定先后顺序。
线性非比较类排序：算法的时间复杂度能够突破(nlogn)，并且不通过比较来对元素排序。
二、时间复杂度比较
注意：
时间复杂度：时间复杂度本意是预估算法的执行时间，但实际上一个程序在计算机上执行的速度是非常快的，时间几乎可以忽略不计了，也就是失去了意义，所以这里意思是算法中执行频度最高的代码的执行的次数。反应当n发生变化时，执行次数的改变呈现一种什么样的规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
稳定性：在排序中对于相等的两个元素a,b。如果排序前a在b的前边，排序之后a也总是在b的前边。他们的位置不会因为排序而改变称之为稳定。反之，如果排序后a,b的位置可能会发生改变，那么就称之为不稳定。
三、冒泡排序
1、时间复杂度
最坏情况: O(n^2)
最好情况: O(n)
2、基本思想
即对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大或最小的数移到数组的最后， 总共循环n-1轮，完成对数组排序。每循环一轮，已确定好顺序元素就会减少一个。
3、图片演示
4、代码实现
//BubbleSort O(n^2)
public static int[] bubbleSort(int[] numbers) {
if (numbers == null) {
return new int[]{};
}
int len = numbers.length;
//外层控制循环次数，对于长度为len长度的数，只需循环len - 1次
for (int i = 0; i < len - 1; i++) {
//内层控制循环次数，len - i,所以为了保证arr[j+1]不越界，j<len-i-1
for (int j = 0; j < len - i - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
return numbers;
}四、选择排序
1、时间复杂度
最坏情况: O(n^2)
最好情况: O(n^2)
2、基本思想
选择排序可以说是冒泡排序的改良版，不再是前一个数跟后一个数相比较， 而是在每一次循环内都由一个数去跟 所有的数都比较一次，每次比较都选取相对较小的那个数来进行下一次的比较，并不断更新较小数的下标 这样在一次循环结束时就能得到最小数的下标，再通过一次交换将最小的数放在最前面，通过n-1次循环之后完成排序。 这样相对于冒泡排序来说，比较的次数并没有改变，但是数据交换的次数大大减少。。
3、图片演示
4、代码实现
//SelectSort O(n^2)
public static int[] selectSort(int[] numbers) {
if (numbers == null) return new int[]{};
int len = numbers.length;
for (int i = 0; i < len - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < len; j++) {
if (numbers[minIndex] > numbers[j]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = numbers[minIndex];
numbers[minIndex] = numbers[i];
numbers[i] = temp;
}
}
return numbers;
}五、插入排序
1、时间复杂度
最坏情况: O(n^2)
最好情况: O(n)
2、基本思想
插入排序的思想打牌的人肯定很容易理解，就是见缝插针。 首先就默认数组中的第一个数的位置是正确的，即已经排序。 然后取下一个数，与已经排序的数按从后向前的顺序依次比较， 如果该数比当前位置排好序的数小，则将排好序的数的位置向后移一位。 重复上一步骤，直到找到合适的位置。 找到位置后就结束比较的循环，将该数放到相应的位置
3、图片演示
4、代码实现
//InsertSort O(n^2)
public static int[] insertSort(int[] numbers) {
if (numbers == null) {
return new int[]{};
}
int len = numbers.length;
for (int i = 1; i < len; i++) {//i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次
int j = i;
int target = numbers[j];//取出目标数
while (j > 0 && target < numbers[j - 1]) {//如果目标数比前一个小，就不断向前比较
numbers[j] = numbers[j - 1];//将numbers中j之前元素整体向后移动一位
j--;
}
numbers[j] = target;//直到找到目标数比前一个数要大的时候，该j位置就是目标数要插入的位置
}
return numbers;
}七、希尔排序
1、时间复杂度
最坏情况: O(n^2)
最好情况: O(n)
2、基本思想
希尔排序也称为”缩小增量排序”，原理是先将需要排的数组分成多个子序列，这样每个子序列的元素个数就很少，再分别对每个对子序列进行插入排序。在该数组基本有序后 再进行一次直接插入排序就能完成对整个数组的排序。所以，要采用跳跃分割的策略。这里引入“增量”的概念，将相距某个增量的记录两两组合成一个子序列，然后对每个子序列进行直接插入排序， 这样得到的结果才会使基本有序（即小的在前边，大的在后边，不大不小的在中间）。希尔排序就是 直接插入排序的升级版。
3、图片演示
4、代码实现
//ShellSort O(n^2), 增量版的插入排序
public static int[] shellSort(int[] numbers) {
if (numbers == null) return new int[]{};
int len = numbers.length;
int k = len / 2;
while (k > 0) {
for (int i = k; i < len; i++) {
int j = i;
int target = numbers[j];
while (j >= k && target < numbers[j - k]) {
numbers[j] = numbers[j - k];
j -= k;
}
numbers[j] = target;
}
k /= 2;
}
return numbers;
}八、归并排序
1、时间复杂度
最坏情况: O(nlogn)
最好情况: O(nlogn)
2、基本思想
递归拆分：先把待排序数组分为左右两个子序列，再分别将左右两个子序列拆分为四个子子序列，以此类推直到最小的子序列元素的个数为两个或者一个为止。逐步合并（一定要注意是从下到上层级合并，可以理解为递归的层级返回）：将最底层的最左边的一个子序列排序，然后将从左到右第二个子序列进行排序，再将这两个排好序的子序列合并并排序，然后将最底层从左到右第三个子序列进行排序….. 合并完成之后记忆完成了对数组的排序操作
3、图片演示
4、代码实现
//MergeSort O(nlogn) 归并排序
public static int[] mergeSort(int[] numbers, int left, int right) {
int mid = (left + right) >>> 1;
if (left < right) {
mergeSort(numbers, left, mid);
mergeSort(numbers, mid + 1, right);
mergeNumbers(numbers, left, mid, right);//合并
}
return numbers;
}
private static void mergeNumbers(int[] numbers, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (numbers[i] <= numbers[j]) {
temp[k++] = numbers[i++];
} else {
temp[k++] = numbers[j++];
}
}
while (i <= mid) {
temp[k++] = numbers[i++];
}
while (j <= right) {
temp[k++] = numbers[j++];
}
for (int index = 0; index < temp.length; index++) {
numbers[index + left] = numbers[index];
}
}九、快速排序
1、时间复杂度
最坏情况: O(n^2)
最好情况: O(nlogn)
2、基本思想
快速排序也采用了分治的策略，这里引入了‘基准数’的概念。找一个基准数（一般将待排序的数组的第一个数作为基准数）对数组进行分区，将小于等于基准数的全部放在左边，大于基准数的全部放在右边。重复1，2步骤，分别对左右两个子分区进行分区，一直到各分区只有一个数为止
3、图片演示
4、代码实现
//QuickSort O(n*logn)快速排序
public static int[] quickSort(int[] numbers, int left, int right) {
int basic, i, j, temp;
if (left >= right) {
return new int[]{};
}
basic = numbers[left];
i = left;
j = right;
while (i < j) {
while (numbers[j] >= basic && i < j) {
j--;
}
while (numbers[i] <= basic && i < j) {
i++;
}
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
numbers[left] = numbers[i];
numbers[i] = basic;
quickSort(numbers, left, j - 1);
quickSort(numbers, j + 1, right);
return numbers;
}十、堆排序
1、时间复杂度
最坏情况: O(nlogn)
最好情况: O(nlogn)
2、基本思想
在此之前要先说一下堆的概念，堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。大顶堆：每个结点的值都大于它的左右子结点的值，升序排序用大顶堆。小顶堆：每个结点的值都小于它的左右子结点的值，降序排序用小顶堆。所以，需要先将待排序数组构造成大顶堆的格式，这时候该堆的顶结点就是最大的数，将其与堆的最后一个结点的元素交换。再将剩余的树重新调整成堆，再次首节点与尾结点交换，重复执行直到只剩下最后一个结点完成排序。
3、图片演示
4、代码实现
//HeapSort
public static int[] headSort(int[] numbers) {
if (numbers == null) {
return new int[]{};
}
int len = numbers.length;
//初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(numbers, i, len);
}
//将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
for (int j = len - 1; j > 0; j--) {
swap(numbers, 0, j);
adjustHeap(numbers, 0, j);
}
return numbers;
}
/**
* 整理树让其变成堆
*
* @param arr 待整理的数组
* @param i 开始的结点
* @param j 数组的长度
*/
public static void adjustHeap(int[] arr, int i, int j) {
int temp = arr[i];//定义一个变量保存开始的结点
//k就是该结点的左子结点下标
for (int k = 2 * i + 1; k < j; k = 2 * k + 1) {
//比较左右两个子结点的大小，k始终记录两者中较大值的下标
if (k + 1 < j && arr[k] < arr[k + 1]) {
k++;
}
//经子结点中的较大值和当前的结点比较，比较结果的较大值放在当前结点位置
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {//说明已经是大顶堆
break;
}
}
arr[i] = temp;
}
/**
* 交换数据
*
* @param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1, int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
