Java常用排序算法_插入排序|快速排序|归并排序高效率排序算法

插入排序

插入排序的概念比较简单、就像平时玩扑克一样、将后面来的数插入到前面序列中,在后面的一张插入的时候、前面的序列已经是有序的了

public class InsertSort {
    public static void insertSort(int[] a){
        int i, j;
        int n =a.length;
        int target;
        for (i = 1; i < n; i  ) {
           j = i;
            target = a[i];
            while (j > 0 && target < a[j-1])
            {
                a[j] = a[j-1];
                j--;
            }
            a[j] = target;
        }
    }
    public static void main(String[] args){
        int[]  a={1,5,9,4,10,8,7};
        insertSort(a);
        for(int i= 0;i<a.length;i  ){
            System.out.print(a[i] ",");
        }
    }
}

快速排序

快速排序是在序列中选取一个中间值、是左边的数全部不大于（不小于）这个中间值、右边的数全部不小于（不大于）这个数、使整个序列分成左右两个分序列、然后又对这两个分序列按上述规则处理、一直递归下去、直到分序列的元素数不少于一个（不需要再划分了）

public class QuickSort {
    public static int gerMark(int[] a, int left ,int right){
        int mark = a[left];
        while(left<right){
            while(left<right&&mark<a[right]){
                right--;
            }
            a[left]=a[right];
            while(left<right&&mark>a[right]){
                left  ;
            }
            a[right]=a[left];
        }
        a[left]= mark;
        return left;
    }
    
    public static void quickSort(int[] a, int left ,int right){
        if(left<right){
            int middle = gerMark(a,left,right);
            quickSort(a,left,middle-1);
            quickSort(a,middle 1,right);
        }
    }
    
    public static void main(String[] args){
        
        int[] a={7,2,5,4,12};
        quickSort(a,0,a.length-1);
        for(int i= 0;i<a.length;i  ){
            System.out.print(a[i] ",");
        }
    }
}

归并排序

归并排序也是以递归的方式进行排序、但是它是插入排序的延伸、我们要以递归的逆过程和插入排序的延伸（插入排序是一个一个插入、归并排序是一组数据插入另一组数据）来思考、首先可以想象、一个根节点包含这组数

经过不断地递归划分成为一个二叉树、每个节点都只有一个元素、再一层一层地向上按插入排序的逻辑重新排序每个节点中的一组数、最后的根节点中的序列就有序了

public class MergeSort {

    public  static int[] mergeSort(int[] a, int left,int right){
        int middle = (left right)/2;
        if(left<right){
            mergeSort(a,left,middle);
            mergeSort(a,middle 1,right);
            merge(a,left,middle,right); 
        }
        return a;
    }
    
    public static void merge(int[] a ,int left ,int middle,int right){
        int[] temp = new int[right-left 1];
        int i=left;
        int j=middle 1;
        int k=0;
        while(i<=middle&&j<=right){
            if(a[i]<a[j]){
                temp[k  ]=a[i  ];
            }
            else{
                temp[k  ]=a[j  ];
            }
        }   
        while(i<=middle){
            temp[k  ]=a[i  ];
        }
        while(j<=right){
            temp[k  ]=a[j  ];
        }
        for(int m=0;m<temp.length;m  ){
            a[left m] = temp[m];
        }
    }
    
    public static void main(String[] args){
        int[] a={8,99,37,10,51,109};
        mergeSort(a,0,a.length-1);
        for(int i= 0;i<a.length;i  ){
            System.out.print(a[i] ",");
        }
    }
}

以上就是使用Java语言编写的三种排序（插入排序、快速排序、归并排序）算法、另外还有最常用的冒泡排序方法、这里就不提供了、比较简单、大家可以自己去实现一下