八大排序
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 基数排序
- 堆排序
一、冒泡排序
代码如下（示例）：
public static void main(String[] args) {
int[] arr = new int[] {2,3,69,4,5,6};
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr.length-1;j++) {
if(arr[j]>arr[j+1]) {
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
System.out.println("冒泡排序法的输出结果为：");
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+",");
}
}
输出的结果：
二、选择排序
代码如下（示例）：
public static void main(String[] args) {
int[] arr=new int[] {8,9,5,52,1,3,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for (int i=0;i<arr.length-1;i++) {
int minIndex=i;
int min=arr[i];
for(int j=i+1;j<arr.length;j++) {
if(min>arr[j]) {
min=arr[j];
minIndex=j;
}
}
arr[minIndex]=arr[i];
arr[i]=min;
}
}
输出结果：
三、插入排序
认定一个排好序的数组，后面的数据一次插入到其对应的位置当中去。
代码如下（示例）：
public static void main(String[] args) {
int[] arr=new int[] {3,9,6,4,5,7};
sort(arr);
System.out.println("插入排序的输出结果是：");
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int i=1;i<arr.length;i++) {
for(int j=i-1;j>=0;j--) {
if(arr[j]>arr[j+1]) {
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else {
break;
}
}
}
}
代码输出结果图为：
例：
一个数组为[2,3,4,5,6,1]
[2,3,4,5,6,1]—>[2,3,4,5,1,6]—>[2,3,4,1,5,6]—>[2,3,1,4,5,6]—>[2,1,3,4,5,6]–>[1,2,3,4,5,6]
由此可以知道插入的数据越小，后移的次数就越多，效率也就明显越低
四、希尔排序
希尔排序的步骤：
希尔排序类似于插入排序，是一种缩小增量的排序。
①首先设置整个数组的步长，设置步长为数组的一半；
②继续将步长设置为原步长的一半；
③当步长为一时，结束。
例如：
一个数组为：
- 第一轮
将数组按照数组长度（8）的一半（4）设为步长，并分好组
此时颜色对应的数据进行比较
5和4比较：5>4 5和4互换位置
9和6比较： 9>6 9和6互换位置
7和8比较： 7<8 7和8位置不变
3和0比较： 3>0 3和0位置互换
经过一轮的比较此时的数组为：
第一轮的代码：
//第一轮
for(int i=4;i<arr.length;i++) {
for(int j=i-4;j>=0;j-=4) {
if(arr[j]>arr[j+4]) {
int temp=arr[j];
arr[j]=arr[j+4];
arr[j+4]=temp;
}
}
}
- 第二轮
和第一轮一样 此时的步长为数组长度一半的一半（2）
经过此次排序结果为：
第二轮的代码：
for(int i=2;i<arr.length;i++) {
for(int j=i-2;j>=0;j-=4) {
if(arr[j]>arr[j+2]) {
int temp=arr[j];
arr[j]=arr[j+2];
arr[j+2]=temp;
}
}
}
- 第三轮
第三轮 步长为1
通过比较变换之后得到：
第三轮的代码如下：
for(int i=1;i<arr.length;i++) {
for(int j=i-1;j>=0;j--) {
if(arr[j]>arr[j+1]) {
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else {
break;
}
}
}
综上可以得到一个综合的代码：
public static void main(String[] args) {
int[] arr=new int[] {5,9,7,3,4,6,8,0};
ShellSort(arr);
//sort(arr);
System.out.println("希尔排序的输出结果：");
System.out.println(Arrays.toString(arr));
}
public static void ShellSort(int[] arr) {
for(int gap=arr.length;gap>0;gap/=2) {
for(int i=gap;i<arr.length;i++) {
for(int j=i-gap;j>=0;j-=gap) {
if(arr[j]>arr[j+gap]) {
int temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
}
}
}
输出结果图为：
五、基数排序
基数排序又称为桶排序 ，把数组放到0-9的桶内，进行排序
现在有一个数组：
下面对个位进行排序
将数组的数据中个位的0-9排好在桶内，如下所示：
此时拍好之后将数据取出（取出的数据会覆盖原数组）：
个位数的排序所使用的代码如下：
首先我们要先定义一个桶：
int[][] bucket=new int[10][arr.length];
定义一个桶记录器，记录桶内元素的个数：
int[] elementCounts=new int[10];
下面向桶内存放数据：
//向桶内放数据
for(int i=0;i<arr.length;i++) {
//计算个位的值
int element=arr[i]/1%10;
int count=elementCounts[element];
bucket[element][count]=arr[i];
elementCounts[element]=elementCounts[element]+1;
}
//将桶内的数据取出
int index1=0;
for(int k=0;k<elementCounts.length;k++) {
if(elementCounts[k]!=0) {
for(int l=0;l<elementCounts[k];l++) {
arr[index1]=bucket[k][l];
index1++;
}
}
elementCounts[k]=0;
}
最后需要把桶记录器清空，以保证后续的排序不受影响
elementCounts[k]=0;
如此十位百位也是使用此方法来排序，直到排好序为止
那么十位百位排序所用到的代码如下：
//向桶内放数据
for(int i=0;i<arr.length;i++) {
//计算十位的值
int element=arr[i]/10%10;
int count=elementCounts[element];
bucket[element][count]=arr[i];
elementCounts[element]=elementCounts[element]+1;
}
//将桶内的数据取出
int index2=0;
for(int k=0;k<elementCounts.length;k++) {
if(elementCounts[k]!=0) {
for(int l=0;l<elementCounts[k];l++) {
arr[index2]=bucket[k][l];
index2++;
}
}
elementCounts[k]=0;
}
//向桶内放数据
for(int i=0;i<arr.length;i++) {
//计算百位的值
int element=arr[i]/100%10;
int count=elementCounts[element];
bucket[element][count]=arr[i];
elementCounts[element]=elementCounts[element]+1;
}
//将桶内的数据取出
int index3=0;
for(int k=0;k<elementCounts.length;k++) {
if(elementCounts[k]!=0) {
for(int l=0;l<elementCounts[k];l++) {
arr[index3]=bucket[k][l];
index3++;
}
}
elementCounts[k]=0;
}
综上，整体代码为：
public static void main(String[] args) {
int[] arr=new int[] {522,293,37,373,414,44,625,82,12,20};
sort(arr);
System.out.println("基数排序的输出结果：");
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
//定义桶
int[][] bucket=new int[10][arr.length];
//定义桶记录器
int[] elementCounts=new int[10];
//找到数组中的最大值
int max=arr[0];
for(int a=0;a<arr.length;a++) {
if(arr[a]>max) {
max=arr[a];
}
}
//找到数组中的最大位数
int maxLength=(max+"").length();
int n=1;
for(int h=0;h<maxLength;h++) {
//向桶内存放数据
for(int i=0;i<arr.length;i++) {
//计算--位的值
int element=arr[i]/n%10;
//放入道统中
int count=elementCounts[element];
bucket[element][count]=arr[i];
elementCounts[element]=elementCounts[element]+1;
}
int index=0;
//将桶内的数据取出
for(int k=0;k<elementCounts.length;k++) {
if(elementCounts[k]!=0) {
for(int l=0;l<elementCounts[k];l++) {
arr[index]=bucket[k][l];
index++;
}
}
elementCounts[k]=0;
}
n=n*10;
}
六、堆排序
1.大顶堆的构建
（大、小顶堆）
堆排序运用到完全二叉树（完全二叉树：从上到下，从左到右依次铺满）
堆排序是利用了平衡二叉树的一些特点来实现完全二叉树
完全二叉树：
完全二叉树是一种特殊的二叉树，要求从上到下从左到右依次平铺
[5,7,4,2,0,3,1,6]
大顶堆：
在完全二叉树的基础之上，每个节点的值都大于或者等于左右孩子的值
小顶堆：
在完全二叉树的基础之上，每个节点的值都小于或者等于左右孩子的值
上述完全二叉树转换为大顶堆为
实际上是利用了完全二叉树的特点来构建大顶堆
任何一个节点的左子节点：arr[2i+1]
任何一个节点的右子节点：arr[2i+2]
任何一个节点的父子节点：arr[(i-1)/2]
构建大顶堆
1.parent游标从后往前移动，如果当前节点没有子树直接跳过
2.如果当前节点有字数，先让child游标执行左子树
3.判断该节点有没有左子树，如果有child游标指向左右子树当前最大的值
4.当前节点和child节点的值进行对比，如果当前节点大于child的值，parent游标继续向前移动
5.如果当前节点小于child的值，父子节点的值进行交换
5.1parent游标指向child游标的位置，child游标的地址：2*child+1
5.1.1如果child游标指向空，parent游标继续向前移动
5.1.2如果child游标指向不为空，那么重复第五步
构建大顶堆的代码如下：
public static void main(String[] args) {
int[] arr=new int[] {5,7,4,2,0,3,1,6};
for(int p=arr.length-1;p>=0;p--) {
sort(arr,p);
}
}
public static void sort(int[] arr,int parent) {
//定义左子树
int child=2*parent+1;
while(child<arr.length-1) {
//排序
//判断有没有右子树，以及比较左右字数谁大，child指针指向大的
int rchild=child+1;
if(rchild<=arr.length-1 && arr[rchild]>arr[child]) {
child++;
}
//父子节点进行对比交换
if(arr[parent]<arr[child]) {
//交换
int temp=arr[parent];
arr[parent]=arr[child];
arr[child]=temp;
parent=child;
child = 2 * child+1;
}else {
break;
}
}
}