常见排序算法及对应的时间复杂度和空间复杂度

public static void BubbleSort(int [] arr){
 
     int temp;//临时变量
     for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次。
         for(int j=0; j<arr.length-i-1; j++){
 
             if(arr[j] > arr[j+1]){
                 temp = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = temp;
             }
         }
     }
 }

public static void select_sort(int array[],int n){
 
   for(int i=0;i<n-1;i++){
 
       int minIndex = i;
       for(int j=i+1;j<n;j++){
          if(array[j]<array[minIndex]){
              minIndex = j;
          }
       }
       if(minIndex != i){
           int temp = array[i];
           array[i] = array[minIndex];
           array[minIndex] = temp;
       }
   }
}

public static void  insert_sort(int array[],int n){
 
   int temp;
 
   for(int i=0;i<n-1;i++){
       for(int j=i+1;j>0;j--){
           if(array[j] < array[j-1]){
               temp = array[j-1];
               array[j-1] = array[j];
               array[j] = temp;
           }else{         //不需要交换
               break;
           }
       }
   }
}

public static void quickSort(int[] a, int low, int high) {
    if (low < high) { // 如果不加这个判断递归会无法退出导致堆栈溢出异常
        int middle = getMiddle(a, low, high);
        quickSort(a, 0, middle - 1);
        quickSort(a, middle + 1, high);
    }
}
 
private static int getMiddle(int[] a, int low, int high) {
    int temp = a[low];// 基准元素
    while (low < high) {
        // 找到比基准元素小的元素位置
        while (low < high && a[high] >= temp) {
            high--;
        }
        a[low] = a[high];
        while (low < high && a[low] <= temp) {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}

public static int[] mergeSort(int[] nums, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        // 左边
        mergeSort(nums, low, mid);
        // 右边
        mergeSort(nums, mid + 1, high);
        // 左右归并
        merge(nums, low, mid, high);
    }
    return nums;
}
 
public static void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;
    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = nums[j++];
    }
    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
        nums[k2 + low] = temp[k2];
    }
}

public static void shellSort(int a[]){
   int temp = 0;
   int d = a.length;
   while(true){
       d = d/2;
       for(int k = 0;k<d;k++){    //根据增量分为若干子序列
           for(int i=k+d;i<a.length;i+=d){
               for(int j=i;j>k;j-=d){
                   if(a[j]<a[j-d]){
                       temp = a[j-d];
                       a[j-d] = a[j];
                       a[j] = temp;
                   }else{
                       break;
                   }
               }
           }
       }
       if(d == 1){
           break;
       }
   }
}

public static void minHeapSort(int a[],int n){
  int temp = 0;
  makeMinHeap(a,n);
 
  for(int i=n-1;i>0;i--){
      temp = a[0];
      a[0] = a[i];
      a[i] = temp;
      MinHeapFixdown(a,0,i);
  }    
}
 
//构建最小堆
public static void makeMinHeap(int a[], int n){
 for(int i=(n-1)/2 ; i>=0 ; i--){
     minHeapFixdown(a,i,n);
 }
}
//从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
public static void minHeapFixdown(int a[],int i,int n){
 
   int j = 2*i+1; //子节点
   int temp = 0;
 
   while(j<n){
       //在左右子节点中寻找最小的
       if(j+1<n && a[j+1]<a[j]){  
           j++;
       }
 
       if(a[i] <= a[j])
           break;
 
       //较大节点下移
       temp = a[i];
       a[i] = a[j];
       a[j] = temp;
 
       i = j;
       j = 2*i+1;
   }
}

public static void radixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
 
   //A:原数组
   //temp:临时数组
   //n:序列的数字个数
   //k:最大的位数2
   //r:基数10
   //cnt:存储bin[i]的个数
 
   for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
 
       //初始化
       for(int j=0;j<r;j++){
           cnt[j] = 0;
       }
       //计算每个箱子的数字个数
       for(int j=0;j<n;j++){
           cnt[(A[j]/rtok)%r]++;
       }
       //cnt[j]的个数修改为前j个箱子一共有几个数字
       for(int j=1;j<r;j++){
           cnt[j] = cnt[j-1] + cnt[j];
       }
       for(int j = n-1;j>=0;j--){      //重点理解
           cnt[(A[j]/rtok)%r]--;
           temp[cnt[(A[j]/rtok)%r]] = A[j];
       }
       for(int j=0;j<n;j++){
           A[j] = temp[j];
       }
   }
}