目录
一、交换排序
（一）冒泡排序
（二）快速排序
二、插入排序
（一）直接插入排序
（二）希尔排序
三、选择排序
（一）简单选择排序
（二）堆排序
四、归并排序
五、基数排序
今天，我来与大家分享最常用的八大排序！
首先，分别有以下排序
一、交换排序
（一）冒泡排序
八大排序中的冒泡排序：
.逻辑上比较简单
.比较相邻两个元素的大小，如果左边的元素大于邮编的元素，则交换两个元素
.交换规则：比较一轮后会把最大的数据放到最后的位置，下一轮会把第二大的元素放到右边第二个位置.....
需要判断的是：
1.什么时候交换位置（当左边元素大于右边元素时交换位置）
2.需要比较多少轮（数据长度-1）
3.每一轮比较多少次（和轮数n有关 递减的关系 数据长度-n-1）
4.时间复杂度：平均情况O(n^2) 最好情况：O(n) 最坏情况:O(n^2) 稳定性:是稳定排序
八大排序中的冒泡排序： .逻辑上比较简单 .比较相邻两个元素的大小，如果左边的元素大于邮编的元素，则交换两个元素 .交换规则：比较一轮后会把最大的数据放到最后的位置，下一轮会把第二大的元素放到右边第二个位置..... 需要判断的是： 1.什么时候交换位置（当左边元素大于右边元素时交换位置） 2.需要比较多少轮（数据长度-1） 3.每一轮比较多少次（和轮数n有关 递减的关系 数据长度-n-1） 4.时间复杂度：平均情况O(n^2) 最好情况：O(n) 最坏情况:O(n^2) 稳定性:是稳定排序
代码实现：
import java.util.Arrays;
public class Bubbing {
public static void main(String[] args) {
int arr[]={2,3,6,7,0,9};
//确定比较的轮数
for (int i=0;iarr[j+1]){
int tem=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tem;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
（二）快速排序
交换排序中的快速排序（快排）
例如，我们先定义一个数组{5,3,1,2,8,9,4}
1.首先我们在序列当中找到一个基准数，一般那第一个数据（元素）作为基准数
2.遍历这个数组将小于基准数的放到基准数的左边，大于基准数的放到基准数右边
3.得到的类似的数组{3,1,2,4,5,8,9}
4.在初始状态下，5在第一个位置，现在5再中间的某个位置
5.确定用递归的方式来实现快速排序
6.怎么实现比对这个逻辑，需要用到两个哨兵（i,j）
7.i,j哨兵分别j向左走，i向右走，直到i==j时停止，将基准数与i位置上的数进行交换
8.如果i！=j 并且i
代码如下：
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr={3,1,2,4,5,8,9};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//参数：需要对那个数组进行排序，还需要两个哨兵，left right
public static void quickSort(int[] arr,int left,int right){
//出口:当left大于right时结束
if(left>right){
return;
}
//定义一个变量来存储基准数
int base=arr[left];
//i,j充当现有数组哨兵
int i=left;
int j=right;
while(i!=j){ //一共分了多少次的子集合，一旦这个循环停了，说明该换基准数了。
//让哨兵往左走，当i==j的时候结束,一定要先走j（先走右边）
while(arr[j]>=base&&i
二、插入排序
（一）直接插入排序
插入排序：直接插入排序
核心思想：将数组中的所有元素依次跟前面的有序元素相比较，如果待排序的元素比正在比较的元素小，那么这个正在排序的元素往前移。
排序的过程：将序列中的第一个元素当做有序的序列。
然后依次拿后面的元素（待排序的元素）和前面已经排序好的元素序列进行比较，
如果待排序元素大于正在比较的元素，则不动。
如果待排序元素小于正在比较的元素，那么正在比较的这个元素小猴哦移动一位。
直到待排序元素遇到比自己小的元素时，将待排序的元素放到正在比较的元素的后面。
代码如下：
import java.util.Arrays;
public class DirectInsert {
public static void main(String[] args) {
int[] arr={3,1,2,4,5,8,9};
for(int i=1;i< arr.length;i++){//拿到待排序的元素；
int tem=arr[i];//待排序元素
int j;
for(j=i-1;j>=0&&arr[j]>tem;j--){//每一个待排序元素和前面有序序列比较的过程（次数）
//将arr[j]向后移动一位
arr[j+1]=arr[j];
}
arr[j+1]=tem;
}
System.out.println(Arrays.toString(arr));
}
}
（二）希尔排序
希尔排序：是插入排序的一种，又称为“缩小增量排序”，是直接插入排序的一种更高效的改进版本。
希尔排序是非稳定性排序算法。
该方法因D.L.Shell于1959年提出而得名。
直接插入排序的升级版
哪些地方做了优化：
希尔排序在排序前先将序列分成几个序列，再对这几个子序列分别进行插入排序
再将整个序列分成几个子序列（比第一次分得子序列少） 再对每一个子序列进行插入排序
直到不能再将整个序列拆分成子序列为止。
增量：每次拆分成子序列的个数，这个增量是依次减小的
例如：序列长度为7 第一次的增量是7/2=3 第二次的增量是3/2=1
第一次将序列分成（序列长度/2）个子序列
第二次将序列分成（前一次增量/2）个子序列
...........................
时间复杂度：平均时间复杂度：O(n^1.3) 最好情况：O(n) 最坏情况：O(n^2)
是一种不稳定的排序
代码如下：
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr={12,23,2,5,47,45,96,100,120,19,23,14};
int gap=arr.length/2;
while (gap!=0){//将数组分几次 增量的个数
//将子序列进行插入排序
for(int i=gap;i=0&&arr[j]>value;j-=gap){
//将元素向后移动一个增量位；
arr[j+gap]=arr[j];
}
arr[j+gap]=value;
}
//变换增量
gap=gap/2;
}
System.out.println(Arrays.toString(arr));
}
}
三、选择排序
（一）简单选择排序
选择排序--直接选择排序（简单选择排序）
核心：比较+置换（交换）
始终拿序列当中最小的那个元素和其他的元素进行比较，最终将最小的元素插入到适当位置
假设第一个是最小的元素
时间复杂度：平均时间复杂度：O（n^2） 最好情况：O(n^2) 最坏情况：O(n^2)
是一种不稳定的排序
代码如下：
import java.util.Arrays;
public class SimpleChoice {
public static void main(String[] args) {
int[] arr={3,10,15,24,35,36,47,58,67,77,87,96};
for(int i=0;i
（二）堆排序
堆排序：大顶堆（升序排序）和小顶堆（降序排序） 我们以大顶堆为例来进行堆排序的分享
堆：近似于完全二叉树
大顶堆：每一个结点都大于子节点
小顶堆：每一个结点都小于子节点
将序列构建成大顶堆（小顶堆）
从最后一个非叶子结点开始构建（叶子结点：没有子节点的结点）
大顶堆构建完以后开始排序
将大顶堆的根元素与最后一个结点调换位置
然后将最后一个结点以外的其他节点在构建大顶堆
然后再将根元素与最后一个结点调换位置，重复操作，最终形成了排序
公式：大顶堆的每个节点与子节点的关系： 每个结点的左节点公式arr[i]>=arr[2*i+1]
每个结点的右节点公式arr[i]>=arr[2*i+2]
小顶堆的每个结点与子节点的公式： 每个结点的左节点公式：arr[i]<=arr[2*i+1]
每个结点的右节点公式：arr[i]<=arr[2*i+2]
代码部分要先构建大顶堆
代码如下：
import java.util.Arrays;
public class MaxHeap {
public static void main(String[] args) {
int[] arr={3,9,0,2,1,4,5};
//最后一个飞叶子节点
int starIndex=(arr.length-1)/2;
//构建大顶堆
for(int i=starIndex;i>=0;i--) {
toMaxHeap(arr, arr.length, starIndex);
}
//构建完大顶堆之后我们需要将根元素有最后一个元素调换位置
for(int i=arr.length-1;i>0;i--){
//将根元素与i对应的元素进行调换
int tem=arr[0];
arr[0]=arr[i];
arr[i]=tem;
//交换完以后，我们还需要将剩余元素调整成大顶堆
toMaxHeap(arr,i,0);
System.out.println(Arrays.toString(arr));
}
}
//构建大顶堆的方法
public static void toMaxHeap(int[] arr,int size,int index){
//arr表示对哪个数组进行大顶堆构建 size表示调整元素的个数 index表示从哪里开始调整
//获取左右子节点的索引
int leftNode=index*2+1;
int rightNode=index*2+2;
//拿到最大结点所对应的那个索引
//假设 传进来的当前下标就是最大元素的下标
int maxIndex=index;
if(arr[leftNode]>arr[maxIndex]&&leftNodearr[maxIndex]&&rightNode
四、归并排序
归并排序：是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法）将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案修补”在一起，即分而治之。基本思想
1.把数组从中间划分成两个子数组;
2.一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素
3.依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
代码如下：
import java.util.Arrays;
public class Guibing {
public static void main(String[] args) {
// int[] arr={1,4,7,8,2,5,6,10};
int[] arr={12,4234,5,7,3,764,7,3,56,8};
//拆分
chaifen(arr,0,arr.length-1);
//归并
// Sort.guibing(arr,0,(arr.length/2)-1,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//拆分的方法
public static void chaifen(int[] arr,int starIndex,int endIndex){
//定义一个中间量
int centerIndex=(starIndex+endIndex)/2;
if(starIndex
五、基数排序
基数排序是桶排序的扩展。它的基本思想是: 将整数按位数切割成不同的数字，然后按每个位数分别比较。 具体做法是: 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
代码如下：.
import java.util.Arrays;
public class JiShu {
public static void main(String[] args) {
int[] arr={3,5,2,14,35,657,23,545,7,45};
// //先获取做大的数
// int max=getMax(arr);
// System.out.println(max);
//调用基数排序方法
sort(arr);
System.out.println(Arrays.toString(arr));
}
//获取数据中最大的数：
public static int getMax(int[] arr){
int max=arr[0];
for(int i=1;imax){
max=arr[i];
}
}
return max;
}
public static void sort(int[] arr){
//定义一个二维数组 来存储10个桶
int[][] temArr=new int[10][arr.length];
//获取数组中的最大数，目的是算出一共多少位，根据多少位来决定需要向桶里放多少次拿多少次
int max=getMax(arr);
//转换成字符串,求长度
int[] count=new int[10];
int length=String.valueOf(max).length();
for(int i=0,n=1;i
最后，我来给大家总结一下这八种排序的时间以及空间复杂度。
OK! 今天的分享就到这里 谢谢大家。
代码如下：
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr={3,1,2,4,5,8,9};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//参数：需要对那个数组进行排序，还需要两个哨兵，left right
public static void quickSort(int[] arr,int left,int right){
//出口:当left大于right时结束
if(left>right){
return;
}
//定义一个变量来存储基准数
int base=arr[left];
//i,j充当现有数组哨兵
int i=left;
int j=right;
while(i!=j){ //一共分了多少次的子集合，一旦这个循环停了，说明该换基准数了。
//让哨兵往左走，当i==j的时候结束,一定要先走j（先走右边）
while(arr[j]>=base&&i
二、插入排序
（一）直接插入排序
插入排序：直接插入排序
核心思想：将数组中的所有元素依次跟前面的有序元素相比较，如果待排序的元素比正在比较的元素小，那么这个正在排序的元素往前移。
排序的过程：将序列中的第一个元素当做有序的序列。
然后依次拿后面的元素（待排序的元素）和前面已经排序好的元素序列进行比较，
如果待排序元素大于正在比较的元素，则不动。
如果待排序元素小于正在比较的元素，那么正在比较的这个元素小猴哦移动一位。
直到待排序元素遇到比自己小的元素时，将待排序的元素放到正在比较的元素的后面。
代码如下：
import java.util.Arrays;
public class DirectInsert {
public static void main(String[] args) {
int[] arr={3,1,2,4,5,8,9};
for(int i=1;i< arr.length;i++){//拿到待排序的元素；
int tem=arr[i];//待排序元素
int j;
for(j=i-1;j>=0&&arr[j]>tem;j--){//每一个待排序元素和前面有序序列比较的过程（次数）
//将arr[j]向后移动一位
arr[j+1]=arr[j];
}
arr[j+1]=tem;
}
System.out.println(Arrays.toString(arr));
}
}
（二）希尔排序
希尔排序：是插入排序的一种，又称为“缩小增量排序”，是直接插入排序的一种更高效的改进版本。
希尔排序是非稳定性排序算法。
该方法因D.L.Shell于1959年提出而得名。
直接插入排序的升级版
哪些地方做了优化：
希尔排序在排序前先将序列分成几个序列，再对这几个子序列分别进行插入排序
再将整个序列分成几个子序列（比第一次分得子序列少） 再对每一个子序列进行插入排序
直到不能再将整个序列拆分成子序列为止。
增量：每次拆分成子序列的个数，这个增量是依次减小的
例如：序列长度为7 第一次的增量是7/2=3 第二次的增量是3/2=1
第一次将序列分成（序列长度/2）个子序列
第二次将序列分成（前一次增量/2）个子序列
...........................
时间复杂度：平均时间复杂度：O(n^1.3) 最好情况：O(n) 最坏情况：O(n^2)
是一种不稳定的排序
代码如下：
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr={12,23,2,5,47,45,96,100,120,19,23,14};
int gap=arr.length/2;
while (gap!=0){//将数组分几次 增量的个数
//将子序列进行插入排序
for(int i=gap;i=0&&arr[j]>value;j-=gap){
//将元素向后移动一个增量位；
arr[j+gap]=arr[j];
}
arr[j+gap]=value;
}
//变换增量
gap=gap/2;
}
System.out.println(Arrays.toString(arr));
}
}
三、选择排序
（一）简单选择排序
选择排序--直接选择排序（简单选择排序）
核心：比较+置换（交换）
始终拿序列当中最小的那个元素和其他的元素进行比较，最终将最小的元素插入到适当位置
假设第一个是最小的元素
时间复杂度：平均时间复杂度：O（n^2） 最好情况：O(n^2) 最坏情况：O(n^2)
是一种不稳定的排序
代码如下：
import java.util.Arrays;
public class SimpleChoice {
public static void main(String[] args) {
int[] arr={3,10,15,24,35,36,47,58,67,77,87,96};
for(int i=0;i
（二）堆排序
堆排序：大顶堆（升序排序）和小顶堆（降序排序） 我们以大顶堆为例来进行堆排序的分享
堆：近似于完全二叉树
大顶堆：每一个结点都大于子节点
小顶堆：每一个结点都小于子节点
将序列构建成大顶堆（小顶堆）
从最后一个非叶子结点开始构建（叶子结点：没有子节点的结点）
大顶堆构建完以后开始排序
将大顶堆的根元素与最后一个结点调换位置
然后将最后一个结点以外的其他节点在构建大顶堆
然后再将根元素与最后一个结点调换位置，重复操作，最终形成了排序
公式：大顶堆的每个节点与子节点的关系： 每个结点的左节点公式arr[i]>=arr[2*i+1]
每个结点的右节点公式arr[i]>=arr[2*i+2]
小顶堆的每个结点与子节点的公式： 每个结点的左节点公式：arr[i]<=arr[2*i+1]
每个结点的右节点公式：arr[i]<=arr[2*i+2]
代码部分要先构建大顶堆
代码如下：
import java.util.Arrays;
public class MaxHeap {
public static void main(String[] args) {
int[] arr={3,9,0,2,1,4,5};
//最后一个飞叶子节点
int starIndex=(arr.length-1)/2;
//构建大顶堆
for(int i=starIndex;i>=0;i--) {
toMaxHeap(arr, arr.length, starIndex);
}
//构建完大顶堆之后我们需要将根元素有最后一个元素调换位置
for(int i=arr.length-1;i>0;i--){
//将根元素与i对应的元素进行调换
int tem=arr[0];
arr[0]=arr[i];
arr[i]=tem;
//交换完以后，我们还需要将剩余元素调整成大顶堆
toMaxHeap(arr,i,0);
System.out.println(Arrays.toString(arr));
}
}
//构建大顶堆的方法
public static void toMaxHeap(int[] arr,int size,int index){
//arr表示对哪个数组进行大顶堆构建 size表示调整元素的个数 index表示从哪里开始调整
//获取左右子节点的索引
int leftNode=index*2+1;
int rightNode=index*2+2;
//拿到最大结点所对应的那个索引
//假设 传进来的当前下标就是最大元素的下标
int maxIndex=index;
if(arr[leftNode]>arr[maxIndex]&&leftNodearr[maxIndex]&&rightNode
四、归并排序
归并排序：是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法）将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案修补”在一起，即分而治之。基本思想
1.把数组从中间划分成两个子数组;
2.一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素
3.依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
代码如下：
import java.util.Arrays;
public class Guibing {
public static void main(String[] args) {
// int[] arr={1,4,7,8,2,5,6,10};
int[] arr={12,4234,5,7,3,764,7,3,56,8};
//拆分
chaifen(arr,0,arr.length-1);
//归并
// Sort.guibing(arr,0,(arr.length/2)-1,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//拆分的方法
public static void chaifen(int[] arr,int starIndex,int endIndex){
//定义一个中间量
int centerIndex=(starIndex+endIndex)/2;
if(starIndex
五、基数排序
基数排序是桶排序的扩展。它的基本思想是: 将整数按位数切割成不同的数字，然后按每个位数分别比较。 具体做法是: 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
代码如下：.
import java.util.Arrays;
public class JiShu {
public static void main(String[] args) {
int[] arr={3,5,2,14,35,657,23,545,7,45};
// //先获取做大的数
// int max=getMax(arr);
// System.out.println(max);
//调用基数排序方法
sort(arr);
System.out.println(Arrays.toString(arr));
}
//获取数据中最大的数：
public static int getMax(int[] arr){
int max=arr[0];
for(int i=1;imax){
max=arr[i];
}
}
return max;
}
public static void sort(int[] arr){
//定义一个二维数组 来存储10个桶
int[][] temArr=new int[10][arr.length];
//获取数组中的最大数，目的是算出一共多少位，根据多少位来决定需要向桶里放多少次拿多少次
int max=getMax(arr);
//转换成字符串,求长度
int[] count=new int[10];
int length=String.valueOf(max).length();
for(int i=0,n=1;i
最后，我来给大家总结一下这八种排序的时间以及空间复杂度。
OK! 今天的分享就到这里 谢谢大家。
