速来围观！leetcode java实现汇总

class SelectionSort(int[] arr){
    public void selectionSort(int[] arr){
      //排除杂条件
      if(arr == null || arr.length < 2){
          return;
      }
      for (int i = 0; i < arr.length; i++){
        //外层循环的每一个i先设置为此循环的最小值的索引，给到内层循环进行比较
         minIndex = i;
         for (int j = i+1; j<arr.length;j++){
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
         }
      }
      //每次一个大循环找到一个该轮最小值放到第一个
      swap(arr,i,minIndex)
    }

    public void swap(int[] arr;int i;int minIndex){
        int tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}

class BubbleSort(int[] arr){
       //排除杂条件
      if(arr == null || arr.length < 2){
          return;
      }
      for(int i = arr.length - 1; i > 0; i--){
          maxIndex = i;
          for(int j = 0; j < 0 ; j--){
             if(arr[j] > arr[j+1]){
               swap(arr,j,j+1);
             }
          }
  }
    public void swap(int[] arr,int i,int j){
    //异或还可以理解为无进位相加，下面方法的使用前提是arr[i]指向的内存和arr[j]指向的内存是两块不同的内存，因为同样的内存异或会成为0
       arr[i] = arr[i] ^ arr[j];
       arr[j] = arr[i] ^ arr[j];
       arr[i] = arr[i] ^ arr[j];
    }
}

class InsertionSort(){
   public insertSort(int[] arr){
     //排除杂条件
      if(arr == null || arr.length < 2){
          return;
      }
      //i从1开始是因为0-0上已经实现了排序
      for (int i = 1; i < arr.length; i++){//0到i做到有序,此时已经做到了0~i-1上的数有序，所以现在比较i-1（j）和第i位置的数的大小，换到不比左边位置的数小了就停止
          for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){
               swap(arr, j, j + 1);
         }
      }
   }
   public void swap(int[] arr,int i,int j){
    //异或还可以理解为无进位相加，下面方法的使用前提是arr[i]指向的内存和arr[j]指向的内存是两块不同的内存，因为同样的内存异或会成为0
       arr[i] = arr[i] ^ arr[j];
       arr[j] = arr[i] ^ arr[j];
       arr[i] = arr[i] ^ arr[j];
    }
}

public class MergeSort{
   public static void process(int[] arr, int L,int R){
      if(L==R){
      return;
      }
      int mid = L+((R-L)>>1);
      //先两边有序，后归并merge
      process(arr,L,mid);
      process(arr,mid,R);
      merge(arr,L,mid,R);
   }
   public static void merge(int[] arr,int L,int M,int R){
   //新设置一个数组放比较值
   int[] help = new int[R-L+1];
   int i = 0;
   int p1 = L;
   int p2 = M + 1;
   // 哪个小放哪个，并移动相应的指针
   while (p1 <= M && p2 <= R){
     help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]
     }
   //下面两个循环只会走一个
   while (p1<=M){
     help[i++] = arr[p1++];
    }
   while (p2<=R){
     help[i++] = arr[p2++];
    }
   for(i = 0,i < help.length;i++){
    //拷贝回原来数组
     arr[L+i] = help[i]
     }
   
   }
}

public class QuickSort{
   public static void quickSort(int[] arr,int L,int R){
   if(L<R){
     //随机找一个值和最后一个值交换
     swap(arr,L+(int)(Math.random()*(R-L+1)),R);
     int[] p = partition(arr,L,R);
     quickSort(arr,L,p[0]-1);//<区
     quickSort(arr,p[1]+1,R);//>区
     }
   }
  public static int[] partition(int[] arr,int L,int R){
    int less = L - 1; //<区右边界
    int more = R; //>区左边界
    while(L<more){
    //如果[i]<num,[i]和<区下一个交换,<区右扩i++
    if(arr[L] < arr[R]){
    //[i]>num.[i]和>区的前一个做交换.>区左扩，i原地不变
        swap(arr,++less,L++);
     }else if(arr[L]>arr[R]){
     swap(arr,--more,L);
     }else{
     //[i]==num,直接跳下一个
      L++;
      }
  }
  //>区的第一个数和最后一个数做交换
  swap(arr,more,R);
  return new int[]{ less + 1, more };
}

public class GetMax{
   public static int process(int[] arr, int L,int R){
     if(L==R){
      return arr[L]; 
      }
    int mid = ((R-L)>>1);//寻找到中点
    //递归调用
    int leftMax = process(arr,L,mid);
    int rightMax = process(arr,mid+1,R);
    return Math.max(leftMax,rightMax);
   }
}