基础排序算法

基础算法

几种简单的排序算法

选择排序

/**
   * 使能比较的类型都可以进行比较
   */
  public static void sort(Comparable[] arr){
      int n = arr.length;

      for(int i = 0; i < n - 1; i++){
          int minIndex = i;
          for(int j = i + 1; j < n; j++){
              if(arr[j].compareTo(arr[minIndex]) < 0){
                  minIndex = j;
              }
          }
          swap(arr,i,minIndex);
      }
  }
  private static void swap(Object[] arr,int i, int j){
      Object t = arr[i];
      arr[i] = arr[j];
      arr[j] = t;
  }

插入排序

    public static void sort(Comparable[] arr){
        for( int i = 1; i < arr.length; i++ ){
            //写法1
//            for(int j = i; j > 0; j-- ){
//                if(arr[j].compareTo(arr[j - 1]) < 0){
//                    swap(arr,j,j - 1);
//                }else {
//                    break;
//                }
//            }

            // 写法2
//            for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
//                swap(arr, j, j-1);

            //写法3
            Comparable temp = arr[i];
            int j = i;
            for(; j > 0; j--){
                if(temp.compareTo(arr[j - 1]) < 0){
                    arr[j] = arr[j - 1];
                }else {
                    break;
                }
            }
            arr[j] = temp;
        }
    }

希尔排序

public static void sort(Comparable[] arr){
    int n = arr.length;
    int h = 1;
    while (h <= n / 3){
        h = 3 * h + 1;
    }
    while (h >= 1){
        for(int i = h; i < n;i++){
            Comparable e = arr[i];
            int j = i;
            for(; j >= h && e.compareTo(arr[j - h]) < 0 ; j -= h)
                arr[j] = arr[j - h];
            arr[j] = e;
        }
        h = h/3;
    }

}

归并排序

//自顶向下
    private static void merge(Comparable[] arr,int l,int mid,int r){
        Comparable[] aux = Arrays.copyOfRange(arr,l,r+1);

        int i = l;
        int j = mid+1;
        for(int k = l; k <= r; k++){
            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l].compareTo(aux[j-l]) < 0 ){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }

    }


    public static void sort(Comparable[] arr,int l,int r){
        /*if(l >= r){
            return;
        }*/
 		// 优化2: 对于小规模数组, 使用插入排序
        if( r - l <= 15 ){
            InsertionSort.sort(arr, l, r);
            return;
        }
        
        int mid = (r - l) / 2 + l;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        //merge(arr,l,mid,r);
        // 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if( arr[mid].compareTo(arr[mid+1]) > 0 )
            merge(arr, l, mid, r);
    }

归并排序自底向上

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){

            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l].compareTo(aux[j-l]) < 0 ){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;

        // Merge Sort Bottom Up 无优化版本
//        for (int sz = 1; sz < n; sz *= 2)
//            for (int i = 0; i < n - sz; i += sz+sz)
//                // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
//                merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));

        // Merge Sort Bottom Up 优化
        // 对于小数组, 使用插入排序优化
        for( int i = 0 ; i < n ; i += 16 )
            InsertionSort.sort(arr, i, Math.min(i+15, n-1) );

        for( int sz = 16; sz < n ; sz += sz )
            for( int i = 0 ; i < n - sz ; i += sz+sz )
                // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
                if( arr[i+sz-1].compareTo(arr[i+sz]) > 0 )
                    merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1) );

    }

快速排序

/**
 * @author footman77
 * @create 2018-11-15 21:19
 */
public class QuickSort {
    private QuickSort(){
    }
    private static int partition(Comparable[] arr, int l, int r){
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        int j = l;// arr[l+1...j] < v ; arr[j+1...i) > v
        for(int i = l + 1; i <= r; i++)
            if(arr[i].compareTo(v) < 0){
                j++;
                swap(arr,j,i);
            }
        swap(arr,l,j);
        return j;
    }

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr,int l, int r){
        // 对于小规模数组, 使用插入排序
        if( r - l <= 15){
            InsertionSort.sort(arr,l,r);
            return;
        }
//        if(l >= r){
//            return;
//        }
        int p = partition(arr,l,r);
        sort(arr, l, p - 1);
        sort(arr,p + 1, r);
    }
    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr, 0, n-1);
    }
    private static void swap(Object[] arr,int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }