本文仅自己学习排序算法之后的总结，若有错误，请大家指正！！
排序算法主要分为三个梯队：
冒泡排序；选择排序；插入排序
它们的共同点是：平均时间复杂度都是O(N^2)。
它们之间有什么样的差别呢？
首先，从性能来分析，冒泡排序和插入排序的元素比较交换次数取决于原始数组的有序程度。
如果原始数组本来已经接近有序，只需要较少的比较交换次数即可完成排序。比如下面这个数组，只有7和8是逆序的：
如果原始数组大部分元素无序，则需要较多的比较交换次数。
在此基础上，插入排序的性能略高于冒泡排序。为什么这么说呢？因为冒泡排序每两个元素之间的交换是彼此独立的，比如A和B交换，B和C交换，C和D交换：
而插入排序的元素交换是连续的，比如把B赋值给A，把C赋值给B，把D赋值给C，最后把A赋值给D：
再来说说选择排序，选择排序和前面两者不太一样，它的元素比较交换次数是固定的，和原始数组的有序程度无关。
因此，当原始数组接近有序时，插入排序性能最优；当原始数组大部分元素无序时，选择排序性能最优。
从稳定性上分析：
冒泡排序和插入排序是稳定排序，值相同的元素在排序后仍然保持原本的先后顺序。
选择排序是不稳定排序，值相同的元素在排序后不一定保持原本的先后顺序。
原始的冒泡排序是稳定排序，该算法每一轮要遍历所有的元素，轮转次数和元素数量相当，所以时间复杂度为O(N^2),原始代码如下：
private static void sort(int array[])
{
int tmp = 0;
for(int i = 0; i < array.length; i++){
for(int j = 0; j < array.length - i - 1; j++)
{
if(array[j] > array[j+1])
{
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
public static void main(String[] args){
int[] array = new int[]{5,8,6,3,9,2,1,7};
sort(array);
System.out.println(Arrays.toString(array));
}
选择排序与冒泡排序类似，就不一一编写代码了。
插入排序的代码如下：
public static void sort(int[] array){
for(int i=1;i<array.length;i++){
int insertValue =array[i];
int j=i-1;
//从右向左比较元素的同时，进行元素复制
for(; j>=0&&insertValue<array[j]; j--){
array[j+1]=array[j];
}
//insertValue的值插入适当位置
array[j+1]=insertValue;
}
}
public static void main(String[] args) {
int array[]={12,1,3,46,5,0,-3,12,35,16};
sort(array);
System.out.println(Arrays.toString(array));
}
希尔排序；快速排序；归并排序；堆排序
共同点： 它们的性能比前三种高一个量级，其中希尔排序的平均时间复杂度最快可以达到O（n^1.3），快速排序、归并排序、堆排序的平均时间复杂度是O（nlogn）。
先从性能来分析，虽然快速排序的平均时间复杂度是O（nlogn），但是在极端情况下，最坏时间复杂度是O（n^2）。
而归并排序和堆排序的时间复杂度稳定在O（nlogn）。
三者的时间复杂度同样都是O（nlogn），但是堆排序比前两者的性能略低一些。
原因：二叉堆的父子节点在内存中并不连续。
在访问内存数据时，对于顺序存储的数据，读写效率往往是最高的。根据CPU的空间局部性原理，CPU在每次访问数据的时候，会把内存中相邻的数据也一并存入缓存。这样一来，CPU以后再访问邻近的数据就不需要重新访问内存，而是访问CPU缓存，从而大大提升了程序执行的效率。
在堆排序的过程中，常常需要父子节点之间进行比较和交换，而父子节点在数组中的位置并不是相邻，而是相差两倍左右：
再看快速排序和归并排序，都是按照数组元素的自然顺序依次进行比较和交换操作。
因此，堆排序的平均性能比快速排序和归并排序略低。
至于排序的稳定性，归并排序是稳定排序，快速排序和堆排序是不稳定排序。
此外，快速排序和堆排序是原地排序，不需要开辟额外空间。而归并排序是非原地排序，在操作的时候需要借助额外的辅助数组来完成。
归并排序的代码实现：
static public void mergeSort(int[] array,int start,int end){
if(start<end){
int mid=(start+end)/2;
mergeSort(array,start,mid);
mergeSort(array,mid+1,end);
merge(array,start,end);
}
}
static private void merge(int[] array,int start,int mid,int end){
int[] tempArray new int[end-start+1];
int p1=start,p2=mid+1,p=0;
while(p1<=mid && p2<=end){
if(array[p1]<=array[p2])
tempArray[p++]=array[p1++];
else
tempArray[p++]=array[p2++];
}
while(p1<=mid){
tempArray[p++]=array[p1++];
}
while(p1<=end){
tempArray[p++]=array[p2++];
}
for(int i=0;i<tepArray.length;i++){
array[i+start]=tempArray[i];
}
}
public static void main(String[] args){
int[] array={5,6,2,5,3,5,656,8,6};
mergeSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
希尔排序的代码实现：
public static void sort(int[] array){
int d=array.length;
while(d>1){
d=d/2;
for(int x=0; x<d; x++){
for(int i=x+d; i<array.length; i++){
int temp=array[i];
int j;
for(j=i-d; j>=0&&array[j]>temp; j=j-d){
array[j+d]=array[j];
}
array[j+d]=temp;
}
}
}
public static void main(String[] args){
int[] array={5,3,9,12,6,1,7,2,4,11,8,10};
sort(array);
System.out.println(Arrays.toString(array));
}
这里就不一一列举所有的排序算法的代码实现了，若有的排序算法不清楚，可以针对单个排序算法去学习。
桶排序；基数排序；计数排序
虽然计数排序、桶排序、基数排序同为线性排序算法，但它们的时间复杂度有着很大不同：
计数排序的时间复杂度是O（n+m），其中m是原始数组的整数范围。
桶排序的时间复杂度是O（n），这是在分桶数量是n的前提下。
基数排序的时间复杂度是O（k（n+m）），其中k是元素的最大位数，m是每一位的取值范围。
三种排序算法都属于稳定排序。
计数排序的局限性：
1.当排序的数据中最大最小值差距过大时，并不适用计数排序。
比如给定20个随机整数，范围在0到1亿之间，这时候如果使用计数排序，需要创建长度1亿的数组。不但严重浪费空间，而且时间复杂度也随之升高。
2.当排序元素不是整数，并不适用计数排序。
如果数列中的元素都是小数，比如25.213，或是0.00000001这样子，则无法创建对应的统计数组。这样显然无法进行计数排序。
基数排序：
数组中有若干个字符串元素，每个字符串元素都是由三个英文字母组成：
bda，cfd，qwe，yui，abc，rrr，uee
如何将这些字符串按照字母顺序排序呢？
由于每个字符串的长度是3个字符，我们可以把排序工作拆分成3轮：
第一轮：按照最低位字符排序。排序过程使用计数排序，把字母的ascii码对应到数组下标，第一轮排序结果如下：
第二轮：在第一轮排序结果的基础上，按照第二位字符排序。
需要注意的是，这里使用的计数排序必须是稳定排序，这样才能保证第一轮排出的先后顺序在第二轮还能继续保持。
第三轮：在第二轮排序结果的基础上，按照最高位字符排序。
像这样把字符串元素按位拆分，每一位进行一次计数排序的算法，就是基数排序（Radix Sort）。
基数排序既可以从高位优先进行排序（MSD），也可以从低位优先进行排序（LSD）。
计数排序的代码实现：
public static int[] countSort(int[] array){
int max=array[0];
for(int i==1;i<array.length;i++){
if(array[i]>max){
max=array[i];
}
}
int[] countArray=new int[max+1];
for(int i=0;i<array.length;i++){
countArray[array[i]]++;
}
int index=0;
int[] sortArray=new int[array.length];
for(int i=0;i<countArray.length;i++){
for(intj=0;j<countArray[i];j++){
sortArray[index++]=i;
}
}
return sortArray;
}
最后给出这几种排序的总的时间复杂度，空间复杂度以及稳定性的对比：
本次分享就到这里了，若有错误的地方，请大家指正，大家一起学习，一起进步！
转载：https://blog.csdn.net/qq_43686926/article/details/106127199