排序_排序算法整理

经常零零散散的用到排序算法，将几类常见的总结下来：

插入排序

/**
     * 时间复杂度O(n^2),空间复杂度O(1)
     * 稳定排序
     * @param arr
     */
    public static void inserSort(int[] arr) {
        int i,j;
            for(i=1;i<arr.length;i++){
                int tmp = arr[i];
                // 前面已有序，找到插入点
                for(j=i-1;j>=0;j--){
                    if(arr[j] > tmp){
                        arr[j+1] = arr[j];
                    }else{
                        break;
                    }
                }
                arr[j+1] = tmp;
        	}
        }

冒泡排序

/**
     * 冒泡排序
     * 时间复杂度 O(n^2),空间复杂度O(1)
     * 稳定排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=arr.length-1;j>i;j--){
                if(arr[j] < arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
    }

选择排序

/**
     * 选择排序
     * 时间复杂度O(n^2),空间复杂度O(1)
     * 非稳定排序
     * @param arr
     */
    public static void selectSort(int[] arr){
        int minFlag;
        for(int i=0;i<arr.length-1;i++){
            minFlag = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j] < arr[minFlag]){
                    minFlag = j;
                }
            }
            if(minFlag != i){
                int tmp = arr[minFlag];
                arr[minFlag] = arr[i];
                arr[i] = tmp;
            }
        }
    }

快速排序

/**
     * 快速排序
     * 时间复杂度 O(nLogn),空间复杂度
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr,int low,int high){
        if(low < high){
            int pivot =partiton(arr,low,high);
            quickSort(arr,low,pivot-1);
            quickSort(arr,pivot+1,high);
        }
    }

    public static int partiton(int[] arr,int low,int high){
        int tmp = arr[low];
        while(low < high){
            while(low < high && arr[high] >= tmp){
                high--;
            }
            arr[low] = arr[high];
            while( low < high && arr[low] <= tmp){
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = tmp;
        return low;
    }

归并排序

/**
     * 时间复杂度O(nlogn),空间复杂度O(n)
     * 稳定排序
     * @param arr
     * @param low
     * @param high
     * @param tmp
     */
    public static void mergeSort(int[] arr,int low,int high,int[] tmp){
        if(low < high){
            int mid = (low + high)>>1;
            mergeSort(arr,low,mid,tmp);
            mergeSort(arr,mid+1,high,tmp);
            merge(arr,low,mid,high,tmp);
        }
    }

    private static void merge(int[] arr,int low,int mid,int high,int[] tmp){
        int i=0;
        int j=low,k=mid+1;
        while(j<=mid && k<=high){
            if(arr[j] <= arr[k]){
                tmp[i++] = arr[j++];
            }else{
                tmp[i++] = arr[k++];
            }
        }
        while(j <= mid){
            tmp[i++] = arr[j++];
        }
        while(k <= high){
            tmp[i++] = arr[k++];
        }
        for(int index=0;index<i;index++){
            arr[low+index] = tmp[index];
        }
    }