几种常见的排序

1.冒泡排序2.直接插入排序3.选择排序4.希尔排序5.快速排序6.归并排序7.基数排序8.堆排序

    public static int[] Bubble(int[] arr){
        for(int i=0;iarr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        return arr;
    }

时间复杂度:O(n^2);
空间复杂度：O(1);
稳定性：稳定

  //直接插入排序
    public static int[] Selection(int[] arr){
        for(int i=1;i0;j--){
                if(arr[j] 
 
 
时间复杂度:O(n^2);
 空间复杂度:O(1);
 稳定性:稳定
 
 
3.选择排序 
public static int[] SelectionSort(int[] arr){
        for(int i=0;iarr[j]){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        return arr;
    }
 
 
 
时间复杂度:O(n^2);
 空间复杂度:O(1);
 稳定性：不稳定
 
 
4.希尔排序 
 //希尔排序
    public static int[] ShellSort(int[] arr){
      int gap=1;
      while(gap0;h=(h-1)/3){
          for(int i=h;ih-1;j=j-h){
                  if(arr[j] 
 
 
时间复杂度：O（n^1.3）;
 空间复杂度:O(1);
 稳定性:不稳定
 
 
5.快速排序 
 //快速排序
    public static int[] QuickSort(int[] arr,int start,int end){
        if(startret){
                j--;
            }
            //当走到这一步，如果i 
 
 
时间复杂度：O(N*log2 N);
 空间复杂度：O(log2 N);
 稳定性:不稳定
 
 
6.归并排序 
    //归并排序:分而治之
    public static void MergeSort(int[] arr){
        //先拆分后归并
       chaifen(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void chaifen(int[] arr,int start,int end){
        //将数组进行拆分
        int center=(start+end)/2;
        if(start 
 
 
时间复杂度：O(N*log2 N);
 空间复杂度：O(n);
 稳定性：稳定
 
 
7.基数排序 
public static void CardinalitySort(int [] arr){
        //遍历数组，找到数组中的最大值
        int max=getMax(arr);
        //计算最大值有几位数     把int类型转化为String 类型，然后，计算其具体长度
        int len=String.valueOf(max).length();
        //定义一个二维数组,相当于10个桶
        int[][] ret=new int[10][arr.length];
        //定义一个统计数组
        int[] counts=new int[10];
        //进入循环
        for(int i=0,n=1;iflag){
                flag=arr[i];
            }
        }
        return flag;
    }
 
 
 
时间复杂度：O(k*(m+n));
 空间复杂度：O(m+n);
 稳定性：稳定
 
 
8.堆排序 
//堆排序
    public static void HeapSort(int[] arr){
        int startIndex=(arr.length-1)/2;
        for(int i=startIndex;i>=0;i--){
            HeapSort2(arr,arr.length,i);
        }
        System.out.println(Arrays.toString(arr));
        //此刻，已经调整为了大顶堆；大顶堆的特性是:1.是一棵完全二叉树；2.它的所有父节点都大于它的子节点
        //现在，需要将 堆顶元素和当前树的最后一个节点值进行交换
        for(int i=arr.length-1;i>0;i--){
            int t=arr[0];
            arr[0]=arr[i];
            arr[i]=t;
            //此时，已经将最大元素放在了数组最后，以此类推，将每回的最大值都放在数组的后面，最后，数组就变成了一个升序的数组
            //此时，需要继续调整剩下元素，让剩下的元素，继续呈 大顶堆的样子
            HeapSort2(arr,i,0);
        }
        System.out.println(Arrays.toString(arr));
    }
    //这个方法的主要目的是：调整为大顶堆的格式
    public static void HeapSort2(int[] arr,int size,int index){
        int maxIndex=index;
        int leftNode=index*2+1;
        int rightNode=index*2+2;
        if(leftNodearr[maxIndex]){
            maxIndex=leftNode;
        }
        if(rightNodearr[maxIndex]){
            maxIndex=rightNode;
        }
        if(index!=maxIndex){
            //如果此时 最大值节点和传过来的节点不是同一个节点的话，需要交换两个节点的值
            int t=arr[maxIndex];
            arr[maxIndex]=arr[index];
            arr[index]=t;           //目的就是 让当前的节点的值最大（也就是说，当前节点的值比它的左右子节点的值都大）
            //此时，虽然当前节点 以及它的左右子节点是 大顶堆的格式，但是，它的子节点以及子节点的子节点不一定是大顶堆了，此刻，需要继续调整
            HeapSort2(arr,size,maxIndex);
        }
    }
 
 
 
时间复杂度：O(n*log2 N);
 空间复杂度：O(1);
 稳定性:不稳定