算法学习笔记--排序

冒泡排序：

冒泡排序

public class BubbleSort {

  public static void main(String[] args) {
    int [] nums = {5,6,73,3,2,3,4};

    boolean hasChange = true;

    for(int i=0 ; i< nums.length-1 && hasChange;i++){
     hasChange =false;
     for(int j=0;j<nums.length-i-1;j++){
       if(nums[j] >nums[j+1]){
         swap(nums,j,j+1);
         hasChange=true;
       }
     }
    }
    System.out.println(nums);
  }

  private static void swap(int[] nums, int j, int i) {
     int temp =nums[j];
     nums[j]=nums[i];
     nums[i]=temp;
  }


}

插入排序：

插入排序

public class InsertSort {

  public static void main(String[] args) {
    int[] nums ={23,4,5,6,89,2,0};
    int temp;
    int j;
    for(int i=1;i<nums.length;i++){
      temp=nums[i];
      for( j=i;j>0 && nums[j-1]>temp;j--){
          nums[j]=nums[j-1];
      }
      nums[j]=temp;
    }
    System.out.println(nums);
  }
}

快速排序：

快速排序

public class QuickSort {

  public static void main(String[] args) {
    int[] nums = {12,45,62,55,7,9,4};

    quick(nums,0,nums.length-1);
    System.out.println(nums);

  }
  public static  void   quick(int [] nums,int low,int high){
     int pivot;
     if(low<high){
       pivot = partition(nums,low,high);
       quick(nums,low,pivot-1);
       quick(nums,pivot+1,high);
     }
  }

  private static int partition(int[] nums, int low, int high) {
    int pioutKey=nums[low];
    while (low<high){
      while (low<high && nums[high]>pioutKey){
        high--;
      }
      swap(nums,low,high);
      while (low<high && nums[low]<pioutKey){
        low++;
      }
      swap(nums,low,high);
    }

    return low;
  }
  public static void swap(int[] L,int i,int j) {
    int temp=L[i];
    L[i]=L[j];
    L[j]=temp;
  }
}

归并排序：

归并排序

public class mergeSort {

  public static void main(String[] args) {
    int[] nums = {4,78,54,7,72,9,10};

    mergeSort(nums,0,nums.length-1);
    System.out.println(nums);
  }
  public static  void mergeSort(int[] arr , int l ,int r){
     if(l==r){
       return;
     }
     //分治
     int m=(l+r)/2;
     mergeSort(arr,l,m);
     mergeSort(arr, m+1, r);
     merge(arr,l,m+1,r);
  }


  public static  void merge(int [] arr ,int l ,int m,int r) {
     int leftSize = m-l;
     int rightSize = r-m+1;
     int[] left =new int[leftSize];
     int[] right = new int[rightSize];
     int i , j ,k ;

     for(i=l;i<m;i++){
       left[i-l]=arr[i];
     }
     for(i=m;i<=r;i++){
       right[i-m]=arr[i];
     }
     //合并
    i=0;k=l; j=0;
    while (i<leftSize && j<rightSize){
        if(left[i]<right[j]){
         arr[k]=left[i];
          i++;
          k++ ;
        }
        else {
          arr[k]=right[j];
          j++;
          k++;
        }
    }
     while (i<leftSize){
       arr[k]=left[i];
       i++;
       k++ ;
     }
     while (j<rightSize){
       arr[k]=right[j];
       j++;
       k++;
     }
  }

}