排序笔记

1.归并排序

public class mergesort{
  public static void mergesort(int[] list){
    if(list.length>1){
      int[] list1 = new int[list.length/2];
      System.arraycopy(list,0,list1,0,list.length/2);
      mergesort(list1);
      int list2length = list.length-list1.length;
      int[] list2 = new int[list2length];
      System.arraycopy(list,list.length/2,list2,0,list2length);
      mergesort(list2);
      int[] temp = merge(list1,list2);
      System.arraycopy(temp,0,list,0,temp.length);
    }
  }
  public static int[] merge(int[] list1,int[] list2){
    int[] temp = new int[list1.length + list2.length];
    int c1 = 0;                                           //list1
    int c2 = 0;                                           //list2
    int c3 = 0;                                           //temp
    while(c1<list1.length && c2<list2.length){
      if(list1[c1]<list2[c2])
        temp[c3++] = list1[c1++];
      else
        temp[c3++] = list2[c2++];
    }
    while(c1<list1.length)
      temp[c3++] = list1[c1++];
    while(c2<list2.length)
      temp[c3++] = list2[c2++];
    return temp;
  }
  public static void main(String args[]){
    int list[] = {2,4,5,9,1,6,7,8};
    mergesort(list);
    for(int i = 0;i<list.length;i++){
      System.out.println(list[i]+" ");
    }
  }
}

2.快速排序

public class quicksort{
  public static void quickSort(int[] list){
    quickSort(list,0,list.length-1);
  }
  public static void quickSort(int[] list,int first,int last){
    if(last > first){
      int pivotindex = partition(list,first,last);
      quickSort(list,first,pivotindex-1);
      quickSort(list,pivotindex+1,last);
    }
  }
  public static int partition(int[] list,int first,int last){
    int pivot = list[first];      //choose the first element as the pivot
    int low = first+1;
    int high = last;
    while(high > low){
      while(high >= low && list[low] <= pivot)    //从开始往后找>=主元的给low
        low++;
      while(high >= low && list[high] > pivot)    //从后往前找<主元的给high
        high--;
      if(high > low){                             //交换high，low项
        int temp = list[high];
        list[high] = list[low];
        list[low] = temp;
      }
    }
    while(high>first && list[high]>=pivot)
      high--;
    if(pivot>list[high]){                          //如果主元比high项大，交换
      list[first] = list[high];
      list[high] = pivot;
      return high;
    }
    else{
      return first;
    }
  }
  public static void main(String args[]){
    int[] list = {2,3,2,5,6,1,-2,3,14,12};
    quickSort(list);
    for(int i = 0;i<list.length;i++)
      System.out.println(list[i]);
  }
}