八大内部排序

Inner Sort

Posted by Jerry on May 12, 2017

八大内部排序

八大内部排序

选择排序

    /**
     * 选择排序,基于比较的排序方式
     * @param a
     * @param lo
     * @param hi
     */
    public static void selectedSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for(int i = lo;i < hi;i++){
            int min = i;
            for(int j = i+1;j<=hi;j++){
                if(a[min]>a[j])min = j;
            }
            if(min!=i)
                swap(a,min,i);
        }
    }

插入排序

    /**
     * 插入排序,基于比较的排序方式
     * @param a
     * @param lo
     * @param hi
     */
    public static void insertSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for (int i = lo+1; i <= hi; i++) {
            int low = lo, high = i-1, tmp = a[i];
            while(low<=high){
                int mid = low + (high - low) / 2;
                if (tmp>=a[mid]){
                    low = mid + 1;
                }else {
                    high = mid - 1;
                }
            }
            for(int j = i-1;j>high;j--){
                a[j+1] = a[j];
            }
            a[high+1] = tmp;
        }
    }

向上冒泡排序

    /**
     * 向上冒泡排序,基于交换的排序方式
     * @param a
     * @param lo
     * @param hi
     */
    public static void bubbleUpSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for(int i = lo; i<hi;i++){
            boolean flag = true;
            for (int j = hi; j>i;j--){
                if(a[j]<a[j-1]){
                    swap(a,j,j-1);
                    flag = false;
                }
            }
            if (flag)break;
        }
    }

向下冒泡排序

    public static void bubbleDownSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for(int i = hi;i>0;i--){
            boolean flag = true;
            for(int j = lo; j<i;j++){
                if(a[j]>a[j+1]){
                    swap(a,j,j+1);
                    flag = false;
                }
            }
            if(flag)break;
        }
    }

归并排序

    public static void mergeSort(int[] a, int lo, int hi){
        if(lo<hi){
            int mid = lo + (hi-lo)/2;
            mergeSort(a,lo,mid);
            mergeSort(a,mid+1,hi);
            merge(a,lo, mid,hi);
        }
    }

    private static void merge(int[] a, int lo, int mid, int hi) {
        int[] l = new int[mid-lo+1], r = new int[hi-mid];
        for(int i=lo,j=0,k=0;i<=hi;i++){
            if(i<=mid)l[j++]=a[i];
            else r[k++] = a[i];
        }
        int i = 0,j=0,k=lo;
        while(i<l.length&&j<r.length){
            a[k++]=(l[i]>r[j])?r[j++]:l[i++];
        }
        while (i<l.length)a[k++] = l[i++];
        while (j<r.length)a[k++] = r[j++];
    }

快速排序

    public static void quickSort(int[] a, int lo, int hi){
        if(lo>hi)return;
        int privot = division(a,lo,hi);
        quickSort(a,lo, privot-1);
        quickSort(a,privot+1,hi);
    }

    private static int division(int[] a, int lo, int hi) {
        int p = a[lo], low = lo, high = hi;
        //这里是不能是等于
        while (low<high){
            while (high>low&&a[high]>=p)high--;
            a[low] = a[high];
            while (high>low&&a[low]<=p)low++;
            a[high] = a[low];
        }
        a[high]=p;

        return high;
    }

希尔排序

    public static void shellSort(int[] a, int lo, int hi){
        int len = (hi - lo + 1);
        //h为步长,初始化步长为n/2
        for(int h = len/2;h>=1;h/=2){
            for(int j = lo+h;j<=hi;j++){
                int tmp = a[j];
                int k = j-h;
                for(;k>=lo;k-=h){
                    if(tmp<a[k]){
                        a[k+h] = a[k];
                    }else {
                        break;
                    }
                }
                a[k+h] = tmp;
            }
        }
    }

堆排序(递归和非递归调整堆)

    /**
     * 最大堆,
     * @param a
     */
    public static void heapSort(int[] a){
        createHeap(a);
        for (int i = a.length-1; i >0 ; i--) {
            swap(a,0,i);
            adjustHeap2(a,0,i);
        }
    }

    /**
     * 递归调整堆
     * @param a 堆排序数组
     * @param i 调整的起始节点
     * @param size 当前堆大小
     */
    private static void adjustHeap(int[] a, int i,int size) {
        //需要调整节点i的,左孩子和右孩子节点
        int lchild = 2*i+1,rchild = 2*i + 2;
        int max = i;
        if(i<size/2){
            //先判断是否存在孩子节点
            if(lchild<size&&a[lchild]>a[max]){
                max = lchild;
            }
            if(rchild<size&&a[rchild]>a[max]){
                max = rchild;
            }
            //如果交换了,就递归调整堆
            if(max != i){
                swap(a,i,max);
                adjustHeap(a,max,size);
            }
        }
    }

    /**
     * 非递归版调整树
     * @param a
     * @param i
     * @param size
     */
    private static void adjustHeap2(int[] a, int i,int size) {
        int max = i;
        while(i<size/2) {
            //需要调整节点i的,左孩子和右孩子节点
            int lchild = 2*i+1,rchild = 2*i + 2;
            //先判断是否存在孩子节点
            if (lchild < size && a[lchild] > a[max]) {
                max = lchild;
            }
            if (rchild < size && a[rchild] > a[max]) {
                max = rchild;
            }
            if (max == i) break;
            //如果交换了,就继续调整堆
            swap(a, i, max);
            i = max;
        }
    }

    /**
     * 建最大根堆
     * @param a
     */
    private static void createHeap(int[] a) {
        for (int j = a.length/2-1; j >=0 ; j--) {
            adjustHeap(a,j,a.length);
        }
    }

测试类

package top.wwj.pro.algorithm.Sort;

import java.util.Arrays;
import java.util.Random;

/**
 * Created by Jerry on 2017/5/12.
 */
public class InnerSort {

    public static void selectedSort(int[] a){
        selectedSort(a,0,a.length-1);
    }
    public static void insertSort(int[] a){
        insertSort(a,0,a.length-1);
    }
    public static void bubbleUpSort(int[] a){
        bubbleUpSort(a, 0, a.length-1);
    }
    public static void bubbleDownSort(int[] a){
        bubbleDownSort(a,0,a.length-1);
    }
    public static void mergeSort(int[] a){
        mergeSort(a, 0, a.length-1);
    }
    public static void quickSort(int[] a){
        quickSort(a,0,a.length-1);
    }
    public static void shellSort(int[] a){
        shellSort(a,0,a.length-1);
    }
    /**
     * 选择排序,基于比较的排序方式
     * @param a
     * @param lo
     * @param hi
     */
    public static void selectedSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for(int i = lo;i < hi;i++){
            int min = i;
            for(int j = i+1;j<=hi;j++){
                if(a[min]>a[j])min = j;
            }
            if(min!=i)
                swap(a,min,i);
        }
    }

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

    /**
     * 插入排序,基于比较的排序方式
     * @param a
     * @param lo
     * @param hi
     */
    public static void insertSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for (int i = lo+1; i <= hi; i++) {
            int low = lo, high = i-1, tmp = a[i];
            while(low<=high){
                int mid = low + (high - low) / 2;
                if (tmp>=a[mid]){
                    low = mid + 1;
                }else {
                    high = mid - 1;
                }
            }
            for(int j = i-1;j>high;j--){
                a[j+1] = a[j];
            }
            a[high+1] = tmp;
        }
    }

    /**
     * 向上冒泡排序,基于交换的排序方式
     * @param a
     * @param lo
     * @param hi
     */
    public static void bubbleUpSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for(int i = lo; i<hi;i++){
            boolean flag = true;
            for (int j = hi; j>i;j--){
                if(a[j]<a[j-1]){
                    swap(a,j,j-1);
                    flag = false;
                }
            }
            if (flag)break;
        }
    }

    public static void bubbleDownSort(int[] a, int lo, int hi){
        if(a==null||lo>=hi||hi>a.length-1)return;
        for(int i = hi;i>0;i--){
            boolean flag = true;
            for(int j = lo; j<i;j++){
                if(a[j]>a[j+1]){
                    swap(a,j,j+1);
                    flag = false;
                }
            }
            if(flag)break;
        }
    }

    public static void mergeSort(int[] a, int lo, int hi){
        if(lo<hi){
            int mid = lo + (hi-lo)/2;
            mergeSort(a,lo,mid);
            mergeSort(a,mid+1,hi);
            merge(a,lo, mid,hi);
        }
    }

    private static void merge(int[] a, int lo, int mid, int hi) {
        int[] l = new int[mid-lo+1], r = new int[hi-mid];
        for(int i=lo,j=0,k=0;i<=hi;i++){
            if(i<=mid)l[j++]=a[i];
            else r[k++] = a[i];
        }
        int i = 0,j=0,k=lo;
        while(i<l.length&&j<r.length){
            a[k++]=(l[i]>r[j])?r[j++]:l[i++];
        }
        while (i<l.length)a[k++] = l[i++];
        while (j<r.length)a[k++] = r[j++];
    }

    public static void quickSort(int[] a, int lo, int hi){
        if(lo>hi)return;
        int privot = division(a,lo,hi);
        quickSort(a,lo, privot-1);
        quickSort(a,privot+1,hi);
    }

    private static int division(int[] a, int lo, int hi) {
        int p = a[lo], low = lo, high = hi;
        //这里是不能是等于
        while (low<high){
            while (high>low&&a[high]>=p)high--;
            a[low] = a[high];
            while (high>low&&a[low]<=p)low++;
            a[high] = a[low];
        }
        a[high]=p;

        return high;
    }

    public static void shellSort(int[] a, int lo, int hi){
        int len = (hi - lo + 1);
        //h为步长,初始化步长为n/2
        for(int h = len/2;h>=1;h/=2){
            for(int j = lo+h;j<=hi;j++){
                int tmp = a[j];
                int k = j-h;
                for(;k>=lo;k-=h){
                    if(tmp<a[k]){
                        a[k+h] = a[k];
                    }else {
                        break;
                    }
                }
                a[k+h] = tmp;
            }
        }
    }

    /**
     * 最大堆,
     * @param a
     */
    public static void heapSort(int[] a){
        createHeap(a);
        for (int i = a.length-1; i >0 ; i--) {
            swap(a,0,i);
            adjustHeap2(a,0,i);
        }
    }

    /**
     * 递归调整堆
     * @param a 堆排序数组
     * @param i 调整的起始节点
     * @param size 当前堆大小
     */
    private static void adjustHeap(int[] a, int i,int size) {
        //需要调整节点i的,左孩子和右孩子节点
        int lchild = 2*i+1,rchild = 2*i + 2;
        int max = i;
        if(i<size/2){
            //先判断是否存在孩子节点
            if(lchild<size&&a[lchild]>a[max]){
                max = lchild;
            }
            if(rchild<size&&a[rchild]>a[max]){
                max = rchild;
            }
            //如果交换了,就递归调整堆
            if(max != i){
                swap(a,i,max);
                adjustHeap(a,max,size);
            }
        }
    }

    /**
     * 非递归版调整树
     * @param a
     * @param i
     * @param size
     */
    private static void adjustHeap2(int[] a, int i,int size) {
        int max = i;
        while(i<size/2) {
            //需要调整节点i的,左孩子和右孩子节点
            int lchild = 2*i+1,rchild = 2*i + 2;
            //先判断是否存在孩子节点
            if (lchild < size && a[lchild] > a[max]) {
                max = lchild;
            }
            if (rchild < size && a[rchild] > a[max]) {
                max = rchild;
            }
            if (max == i) break;
            //如果交换了,就继续调整堆
            swap(a, i, max);
            i = max;
        }
    }

    /**
     * 建最大根堆
     * @param a
     */
    private static void createHeap(int[] a) {
        for (int j = a.length/2-1; j >=0 ; j--) {
            adjustHeap(a,j,a.length);
        }
    }

    public  static int[] randomArray(int length){
        Random r = new Random();
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = r.nextInt(length);
        }
        return arr;
    }

    public static void printInt(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if(i<arr.length-1){
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int size=9;
        int[] a = InnerSort.randomArray(size);
        int[] b = InnerSort.randomArray(size);
        int[] c = InnerSort.randomArray(size);
        int[] d = InnerSort.randomArray(size);
        int[] e = InnerSort.randomArray(size);
        int[] f = InnerSort.randomArray(size);
        int[] g = InnerSort.randomArray(size);
        int[] h = InnerSort.randomArray(size);
        int[] t = {2, 1};
        InnerSort.heapSort(t);
//        printInt(a);
//        InnerSort.bubbleUpSort(null,12,12);
        InnerSort.bubbleUpSort(a);
        InnerSort.selectedSort(b);
        InnerSort.insertSort(c);
        InnerSort.bubbleDownSort(d);
        InnerSort.mergeSort(e);
        InnerSort.quickSort(f);
        InnerSort.shellSort(g);
        InnerSort.heapSort(h);
        InnerSort.printInt(a);
        InnerSort.printInt(b);
        InnerSort.printInt(c);
        InnerSort.printInt(d);
        InnerSort.printInt(e);
        InnerSort.printInt(f);
        InnerSort.printInt(g);
        InnerSort.printInt(h);
        System.out.println(Arrays.toString(t));
    }
}