八大排序的相关内容
目录
一、冒泡排序
二、选择排序
三、插入排序
四、希尔排序
五、基数排序
六、快速排序
七、归并排序
八、堆排序
九、代码
一、冒泡排序
二、选择排序
每次遍历数组，将最小元素换到已排序的末尾
三、插入排序
假设第一个元素已经排好序，从第二个元素开始遍历数组，比较当前元素和前一个的大小
四、希尔排序
先分组
然后每组排序之后再合并
然后再分组
每组再排序，之后合并
最后再分组，一个一组
五、基数排序
定义0~9 1十个桶，先按个位排
排完之后是
然后再按十位排
排完之后是
最后按百位排是
六、快速排序
七、归并排序
分组
合并
八、堆排序
大顶堆：在完全二叉树的基础上，父结点大于左右孩子结点
一组数：
换成完全二叉树
大顶堆：
堆顶堆底互换
把堆底隔开，剩下元素还按照上面的做法继续排列
九、代码
public class BubbleSort {
public static void main(String[] args) {
int[] arr=new int[]{1,5,2,7,3,8,4,6};
//sort(arr);//冒泡排序
//sort1(arr);//选择排序
//sort2(arr);//插入排序
//sort3(arr);//希尔排序
/*int[] arr=new int[]{22,45,76,12,87,122,80,69};
sort4(arr);//基数排序*/
//sort5(arr,0,arr.length-1);//快速排序
//sort6(arr,0,arr.length-1);//归并排序
//堆排序
for(int p=arr.length-1;p>=0;p--){
sort7(arr,p,arr.length);
}
for(int i=arr.length-1;i>0;i--){
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
sort7(arr,0,i);
}
System.out.println(Arrays.toString(arr));
}
//冒泡
public static void sort(int[] arr){
int len=arr.length;
for(int j=0;j<len;j++){
for(int i=0;i<len-j-1;i++){
if(arr[i]>arr[i+1]){
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}
}
//选择排序
public static void sort1(int[] arr){
//int min=0;
int len=arr.length;
for(int j=0;j<len;j++){
int min=j;
for(int i=1;i<len;i++){
if(arr[i]<arr[min]){
min=i;
}
}
int temp=arr[min];
arr[min]=arr[j];
arr[j]=temp;
}
}
//插入排序
public static void sort2(int[] arr){
int len=arr.length;
for(int i=1;i<len;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;
}
}
}
}
//希尔排序
public static void sort3(int[] arr){
int len=arr.length;
for(int k=len/2;k>0;k/=2){
for(int j=k;j<len;j++){
for(int i=j-k;i>=0;i-=k){
if(arr[i]>arr[i+k]){
int temp=arr[i];
arr[i]=arr[i+k];
arr[i+k]=temp;
}else {
break;
}
}
}
}
}
//基数排序
public static void sort4(int[] arr){
int[][] brr1=new int[10][arr.length];//桶
int[] brr2=new int[10];//桶记录器
//个位的放入
for(int i=0;i<arr.length;i++){
int element=arr[i]%10;//个位
int count=brr2[element];
brr1[element][count]=arr[i];//放入数据
//brr1[count][element]=arr[i];//不可以这么写
brr2[element]=count+1;
}
//个位的取出
int index=0;
for(int i=0;i<10;i++){
if(brr2[i]>0){
for(int j=0;j<brr2[i];j++){
arr[index]=brr1[i][j];
//arr[index]=brr1[j][i];//不可以这么写
index++;
}
}
brr2[i]=0;
}
//十位的放入
for(int i=0;i<arr.length;i++){
int element=arr[i]/10%10;
int count=brr2[element];
brr1[element][count]=arr[i];//放入数据
brr2[element]=count+1;
}
//十位的取出
int index1=0;
for(int i=0;i<10;i++){
if(brr2[i]>0){
for(int j=0;j<brr2[i];j++){
arr[index1]=brr1[i][j];
index1++;
}
}
brr2[i]=0;
}
//百位的放入
for(int i=0;i<arr.length;i++){
int element=arr[i]/100%10;
int count=brr2[element];
brr1[element][count]=arr[i];//放入数据
brr2[element]=count+1;
}
//百位的取出
int index2=0;
for(int i=0;i<10;i++){
if(brr2[i]>0){
for(int j=0;j<brr2[i];j++){
arr[index2]=brr1[i][j];
index2++;
}
}
}
}
//快速排序
public static void sort5(int[] arr,int left,int right){
if(left<right){
int point=partition(arr,left,right);
sort5(arr,left,point-1);
sort5(arr,point+1,right);
}
}
public static int partition(int[] arr,int left,int right){
int point=arr[right];
int i=left-1;
for(int j=left;j<right;j++){
if(arr[j]<point){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int temp=arr[i+1];
arr[i+1]=arr[right];
arr[right]=temp;
return i+1;
}
//归并排序
public static void sort6(int[] arr,int left,int right){
if(left<right){
int mid=left+(right-left)/2;
sort6(arr,left,mid);
sort6(arr,mid+1,right);
merge(arr,left,right,mid);
}
}
public static void merge(int[] arr,int left,int right,int mid){
int[] brr=new int[right-left+1];
int i=left;
int j=mid+1;
int k=0;
while(i<=mid&&j<=right){
if(arr[i]<=arr[j]){
brr[k++]=arr[i++];
}else {
brr[k++]=arr[j++];
}
}
while (i<=mid){
brr[k++]=arr[i++];
}
while (j<=right){
brr[k++]=arr[j++];
}
for(int m=0;m<brr.length;m++){
arr[left+m]=brr[m];
}
}
//堆排序
public static void sort7(int[] arr,int parent,int length){
int child=2*parent+1;
while(child<length){
int rChild=child+1;
if(rChild<length&&arr[child]<arr[rChild]){
child++;
}
if(arr[parent]<arr[child]){
int temp=arr[parent];
arr[parent]=arr[child];
arr[child]=temp;
parent=child;
child=2*parent+1;
}else {
break;
}
}
}
}