博客首页：痛而不言笑而不语的浅伤

欢迎关注点赞 收藏 ⭐留言 欢迎讨论！

本文由痛而不言笑而不语的浅伤原创，CSDN首发！

系列专栏：《学习经验》

首发时间：2022年5月10日

❤：热爱Java学习，期待一起交流！

作者水平有限，如果发现错误，求告知，多谢！

有问题可以私信交流！！！

目录

一、排序的概述

排序的分类

优点及缺点

如何选择排序算法

8种排序之间的关系:

二、插入排序

分类

直接插入排序

希尔排序

三、交换排序

分类

冒泡排序法:

快速排序:

四、选择排序

分类

直接选择排序

堆排序

五、归并排序

使用方法

六、基数排序

使用方法：

总结:

按平均的时间性能来分

按平均的空间性能来分

排序方法的稳定性能

一、排序的概述

排序的分类

 分为5大类：

        1.插入排序(直接插入排序、希尔排序)。

        2.交换排序(冒泡排序、快速排序)。

        3.选择排序(直接选择排序、堆排序)。

        4.归并排序。

        5.分配排序(箱排序、基数排序)。

优点及缺点

        所需辅助空间最多:归并排序

        所需辅助空间最少:堆排序

        平均速度最快:快速排序

        不稳定:快速排序，希尔排序，堆排序。

如何选择排序算法

        1.数据的规模;

        2.数据的类型;

        3.数据已有的顺序。

        一般来说，当数据规模较小时，应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。考虑数据的类型，比如如果全部是正整数，那么考虑使用桶排序为最优。考虑数据已有顺序，快排是一种不稳定的排序(当然可以改进)，对于大部分排好的数据，快排会浪费大量不必要的步骤。数据量极小，而起已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。

8种排序之间的关系:

二、插入排序

分类

1.直接插入排序。

2.希尔插入排序。

直接插入排序

说明

        将一个记录插入到已经排序好的有序表中。

        1.sorted数组的第0个位置没有放数据。

        2.从sorted第二个数据开始处理。

        如果该数据比它前面的数据要小，说明该数据要往前面移动。

用法

a.首先将该数据备份放到sorted的第0位置当哨兵。

b.然后将该数据前面那个数据后移。

c.然后往前搜索，找插入位置。

d.找到插入位置之后讲第0位置的那个数据插入对应位置。

O(n*n),当待排记录序列为正序时，时间复杂度提高至O(n)。

实例:

希尔排序

1.先将整个待排记录序列分割成若干个子序列分别进行直接插入排序。

2.待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

实例:

插入排序Java代码:

public class InsertionSort{

//插入排序:直接插入排序，希尔排序

public void straightInsertionSort(double[]sorted){

int sortedLen=sorted.length;

for(intj=2;j=0;k--){

if(sorted[k]>sorted[0]){

sorted[k+1]=sorted[k];

}else{

insertPos=k+1;

break;

}

}

sorted[insertPos]=sorted[0];

}

}

}

public void shellInertionSort(double[] sorted, int inc){

int sortedLen=sorted.length;

for(intj=inc+1:j=0;k-=inc){

if(sorted[k]>sorted[0]){

sorted[k+inc]=sorted[k];//数据结构课本上这个地方没有给出判读出错:

if(k-inc<=0){

insertPos=k;

}

}else{

insertPos=k+inc;

break;

}

}

sorted[insertPos]=sorted[0];

}

}

}



public void shellInsertionSort(double[] sorted){

int[]incs={7,5,3,1};

int num=incs.length;

int inc=0;

for(int j=0;j

public class bubbleSort {

public bubbleSortO(){

int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};

int temp=0;

for(int i=0;ia[j+1]){

temp=a[i];

a[i]=a[j+1];

a[j+1]=temp;

}

}

}

for(int i=0;i

public class quickSort {

int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};

public quickSortO{ quick(a);

for(int i=0;i=tmp){

high--;

}

list[low]=list[high];//比中轴小的记录移到低端

while(low0){//查看数组是否为空

quickSort(a2,0,a2.length-1);

}

}

}

public class selectSort {

public selectSort(){

int a[]={1,54,6,3,78,34,12,45};

int position=0;

for(int i=0;i

importjava.util.Arrays;

public class HeapSort {

int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};

public HeapSort(){

heapSort(a);

}

public void heapSort(int[]a{

System.outprintln(\"开始排序\");

int arraylength=a.length;//循环建堆

for(int i=0;i=0;i--){

//K保存正在判断的节点

int k=i;

//如果当前k节点的子节点存在

while(k*2+1<=lastIndex){

//k节点的左子节点的索引

int biggerIndex=2*k+1;

//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在

if(biggerIndex

public class MergeSort {

private double[]bridge;//辅助数组

public void sort(double[] obj){

if(obj==null){

throw new NullPointerException(\"The param can not be null!\");

}

bridge=new double[obj.length];//初始化中间数组

mergeSort(obj,,obj.length-1);//归并排序

bridge =null;

}

private void mergeSort(double[] obj,int left,int right){

if(left

public class RadixSort {

private int keyNum=-1;

private Vector> util;

public void distribute(double []sorted,int nth){

if(nth<=keyNum && nth>0){

util=new Vector>();

for(intj=0;j<10;j++){

Vector temp=new Vector();

util.add(temp);

}

for(int j=0;j=nth){

return CharactergetNumericValue(nncharAt(len nth));

}else{

return 0;

}

}

public void collect(double[]sorted){

int k=0;

for(int j=0;j<10;j++){

int len=util.get(j).size();

if(len>0){

for(int i=0;imax){

max=sorted [j];

}

}

return Integer.toString((int)max).length();

}

public void radixSort(double[] sorted){

if(keyNum==-1){

keyNum= getKeyNum(sorted);

}

for(int i=1;i<=keyNum;i++){

distribute(sorted,i);

collect(sorted);

}

}

public static void main(String[]args){

Random random=new Random(6);

int arraysize=21;

double[]sorted=new double[arraysize] ;

System.outprint(\"Before Sort:\");

for(intj=0;j