对一个数组进行排序你该不会只会用库函数的sort函数吧？没关系，看完这篇，分分钟带你学废八种排序
1.冒泡排序
冒泡排序（Bubble Sort）,这是排序算法里面最简单的一个，这个名字由来就是把越大的元素经过慢慢的交换慢慢“浮”到最上面，就好像碳酸饮料中的二氧化碳一样最终会上浮到顶端，所以取名“冒泡排序”。
动图演示：
可以看出来，数组的长度是多少，就需要进行比较几趟，每一趟结束最大的元素都会“浮”上去
程序源代码：
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length; 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;
}
}
}
}
这算代码大家应该都可以写出来，但是从上图可以看出来，在执行到绿色部分的时候，数组就已经有序了，不用进行后面的比较了，所以，我们对代码进行优化，当数组有序的时候就不再往下执行了，优化代码如下：
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length; i++) {
boolean flg = true;
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;
flg = false;
}
}
if (flg){
break;
}
}
}
首先就是在循环之前定义一个boolean类型的变量为true，如果循环过程中元素之间进行了交换，就讲这个值置为false。因此，我们就可以通过这个boolean类型的变量来判断是否进行了元素的交换，如果没有交换，则boolean类型这个变量依然为true，此时数组有序了就可以直接跳出循环，否则继续排序。
2.插入排序
插入排序（Insertion Sort）也是一种简单直观的排序算法，插入排序的基本思想是：每步将一个待排序的记录，按照其元素的大小插入到已经排好序的数组的适当位置中，直到元素全部插入。
动图演示：
插入排序就是让待插入元素“找”到适合自己的位置，然后进行插入“归位”，直到数组遍历完成。
程序源代码：
public static void insertSort(int[] array){
for (int i = 1;i < array.length;i++){
int tmp = array[i];
int j = i-1;
for (;j >= 0;j--){
if (array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
3.希尔排序
希尔排序（Shell Sort）属于插入排序的一种，又称为“缩小增量排序”，相比于直接插入排序，希尔排序更为高效。希尔排序的主要思想：将元素按下标的一定增量分为若干个组，每组分别进行直接插入排序，然后将组数减小，随着组数的减少，每组包含的元素也越来越多，当组数减为1时，算法便终止。
演示：
程序源代码：
public static void shellSort(int[] array){
int[] arr = {
5,3,1};
for (int i = 0; i < arr.length; i++) {
shell(array,arr[i]);
}
}
public static void shell(int[] array,int gap){
for (int i = gap;i < array.length;i++){
int tmp = array[i];
int j = i-gap;
for (;j >= 0;j = j-gap){
if (array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
}
为什么要用希尔排序呢？因为将数组分为若干个组，数据量小，插入所需的时间复杂度就会减小，希尔排序的分组根据什么确定呢？如上述代码中，就是根据数组元素的多少而决定，组数从最开始的5先减小为3，最后减小为1。
4.选择排序
选择排序（Selection Sort）是一种很简单直观的排序算法。选择排序的主要思想是：第一次从待排序的数组元素中选择最小（或者最大）的一个元素，放在序列的起始位置，再从数组元素中找到最小（或者最大）的元素放在已经排好序的后面，直到数组元素全部已经排序。
动图演示：
程序源代码：
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
for (int j = i+1;j < array.length;j++){
if (array[j] < array[i]){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
从代码量就能够看出来，选择排序的代码较少，思想也比较简单，容易理解。选择排序法，没有突破时间复杂度为O(n²)的瓶颈，但是性能上略优于冒泡排序法
什么？？你觉得排序太简单了，别着急，重头戏在后面！！！
5.堆排序
堆排序（HeapSort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆的操作：
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。
堆中定义以下几种操作：
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
程序源代码：
public static void heapSort(int[] array){
//1、建大堆
createHeap(array);
//2、排序
int end = array.length-1;
while (end > 0){
int temp = array[0];
array[0] = array[end];
array[end] = temp;
adjust(array,0,end);
end--;
}
}
public static void createHeap(int[] array){
//p是每个子树的根节点
for (int p = (array.length-1-1)/2;p >= 0;p--){
adjust(array,p,array.length);
}
}
public static void adjust(int[] array,int parent,int len){
int child = 2*parent + 1;
while (child < len){
if (child+1 <len && array[child] < array[child+1]){
child++;
}
if (array[child] > array[parent]){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = 2*parent + 1;
}else{
break;
}
}
}
总结一下堆排序的流程：
1.首先将无序的数组构造一个大根堆（新插入的元素与其父类节点的值进行比较）
2.固定一个最大值，将剩余的数重新构造一个大根堆，重复此过程。
6.快速排序（重要）
快速排序（QuickSort）简称快排，是对冒泡排序算法的一种改进。
顾名思义快速排序最大的优点就是速度比较快，是我们后续工作中用到最多的一种排序。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
首先定义两个指针low指向起始位置，high指向最后一个元素的位置,然后指定初始位置基数key，作为坑low寻找比基数key大的数字，找到后将low的数据赋给high，low成为一个坑，然后hight寻找比基数key小的数字，找到将hight的数据赋给low，high成为一个新坑，循环这个过程，直到low指针与high指针相遇，然后将key返回给那个坑（最终：key的左边都是比key小的数，key的右边都是比key大的数），然后进行递归操作。
动图演示：
程序源代码：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void quick(int[] array,int low,int high){
if (low >= high){
return;
}
int par = partion(array,low,high);
quick(array,low,par-1);
quick(array,par+1,high);
}
public static int partion(int[] array,int start,int end){
int tmp = array[start];
while (start < end){
while (start < end && array[end] >= tmp){
end--;
}
if (start >= end){
array[start] = tmp;
break;
}else{
array[start] = array[end];
}
while (start < end && array[start] <= tmp){
start++;
}
if (start >= end){
array[start] = tmp;
break;
}else{
array[end] = array[start];
}
}
return start;
}
这样我们就实现了对数组的快速排序，但是，我们还觉得这个速度不够快，还能怎样进行优化呢？
这里我们采用了两种优化方法：
第一种是三数取中，构造一个三数取中的函数，将数组的第一个元素low，中间那个元素mid和最后一个元素三个元素进行比较，取中间那个数为基准（key）。
第二种是直接插入法，构造一个直接插入的函数，当数据量较少的时候就可以使用直接插入的方法。
优化后的代码：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void quick(int[] array,int low,int high){
if (low >= high){
return;
}
//优化2、直接插入排序
if (low + high +1 <100){
insertSort2(array,low,high);
return;
}
//优化1、三数取中
int mid = (low + high)>>>1;
medianOfThree(array,low,mid,high);
int par = partion(array,low,high);
quick(array,low,par-1);
quick(array,par+1,high);
}
public static int partion(int[] array,int start,int end){
int tmp = array[start];
while (start < end){
while (start < end && array[end] >= tmp){
end--;
}
if (start >= end){
array[start] = tmp;
break;
}else{
array[start] = array[end];
}
while (start < end && array[start] <= tmp){
start++;
}
if (start >= end){
array[start] = tmp;
break;
}else{
array[end] = array[start];
}
}
return start;
}
//三数取中函数
public static void medianOfThree(int[] array,int low,int mid,int high){
//array[mid] <= array[low] <= array[high]
if (array[mid] > array[low]){
int tmp = array[low];
array[low] = array[mid];
array[mid] = tmp;
}
//array[mid] <= array[low]
if (array[low] > array[high]){
int tmp = array[low];
array[low] = array[high];
array[high] = tmp;
}
//array[low] <= array[high]
if (array[mid] > array[high]){
int tmp = array[mid];
array[mid] = array[high];
array[high] = tmp;
}
//array[mid] <= array[high]
}
//对区间数据进行直接插入排序
public static void insertSort2(int[] array,int start,int end){
for (int i = start;i <= end;i++){
int tmp = array[i];
int j = i-1;
for (;j >= start;j--){
if (array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
总结一下，快速排序之所以快，因为和冒泡排序比起来每次的交换是跳跃式的，每次排序的时候设置一个基准，将小于基准的元素都放在基准的左边，将大于基准的元素都放在基准的右边。
7.归并排序（重要）
归并排序（Merge Sort）是建立在归并操作上的一种有效，比较稳定的排序算法。先将数组分为若干个子序列，将子序列先进行排序，再将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。如果将两个有序表合并成一个有序表，称为二路归并。归并排序就是用空间换取时间的实列。
- 核心思想：分治
程序源代码：
public static void margeSort(int[] array){
margeSortRec(array,0,array.length-1);
}
public static void margeSortRec(int[] array,int low,int high){
if (low >= high){
return;
}
int mid = (low + high)>>>1;
margeSortRec(array,low,mid);
margeSortRec(array,mid+1,high);
marge(array,low,mid,high);
}
public static void marge(int[] array,int low,int mid,int high){
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int[] tmpArray = new int[high-low+1];
int k = 0;
while (s1 <= e1 && s2 <= e2){
if (array[s1] < array[s2]){
tmpArray[k++] = array[s1++];
}else{
tmpArray[k++] = array[s2++];
}
}
while (s1 <= e1){
tmpArray[k++] = array[s1++];
}
while (s2 <= e2){
tmpArray[k++] = array[s2++];
}
for (int i = 0;i < tmpArray.length;i++){
array[i + low] = tmpArray[i];
}
}
总结一下，归并排序主要就是用到递归的思维，要注意的是哪个先比较完了之后，那么剩下的就不需要比较，直接把后面的直接移上去就好了，这个需要提前判断一下。
8.计数排序
计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法，当然这是一种牺牲空间换取时间的做法。
程序源代码：
public static int[] countSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//这里k的大小是要排序的数组中，元素大小的极值差+1
int k=max-min+1;
int c[]=new int[k];
for(int i=0;i<a.length;++i){
c[a[i]-min]+=1;//优化过的地方，减小了数组c的大小
}
for(int i=1;i<c.length;++i){
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}
我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是O(nlogn)。
各种排序方式的复杂度及稳定性比较
转载：https://blog.csdn.net/m0_56793367/article/details/117475163