Java 六大排序算法

Java 六大排序算法 Java 六大排序算法 1. 冒泡排序

public class BubbleSort {
    public static void main(String[] args) {

        BubbleSort bubbleSort = new BubbleSort();
        int[] a = {4,5,6,1,2,3};
        System.out.println("排序前：");
        for (int i : a) {
            System.out.println(i);
        }
        bubbleSort.bubblesort(a);
        System.out.println("排序后：");
        for (int i : a) {
            System.out.println(i);
        }
    }

    public void bubblesort(int[] a){
        int temp;
        for (int i = 0; i < a.length; i++){
            for (int j = 0; j < a.length - 1 - i; j++){//j从0开始
                if (a[j]  > a[j+1]) {
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }
}

2. 选择排序

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {4,6,8,7,9,2,10,1};
        System.out.println("排序前=================");
        for (int i : a) {
            System.out.println(i);
        }
        new SelectionSort().selectionsort(a);
        System.out.println("排序前=================");
        for (int i : a) {
            System.out.println(i);
        }
    }
    
    public void selectionsort(int[] a){
        int temp;
        for (int i = 0; i < a.length -1; i++){
            int indexMin = i;
            for (int j = i; j < a.length; j++){
                if (a[indexMin] > a[j]){
                    indexMin = j;	//c
                }
            }
            temp = a[i];
            a[i] = a[indexMin];
            a[indexMin] = temp;
        }
    }
}

3. 插入排序

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {4,3,2,10,12,1,5,6};
        System.out.println("排序前===========");
        for (int i : a) {
            System.out.println(i);
        }
        new InsertionSort().insertionsort(a);
        System.out.println("排序前===========");
        for (int i : a) {
            System.out.println(i);
        }
    }

    public void insertionsort(int[] a){
        int temp;
        for (int i = 1; i < a.length; i++){
            for (int j = i; j > 0; j--){
                if (a[j-1] > a[j]){
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
}

4. 希尔排序

public class ShellSort {
    public static void main(String[] args) {
        int[] a = {9,1,2,5,7,4,8,6,3,5};
        System.out.println("排序前===========");
        for (int i : a) {
            System.out.println(i);
        }
        new ShellSort().shellsort(a);
        System.out.println("排序后===========");
        for (int i : a) {
            System.out.println(i);
        }
    }

    public void shellsort(int[] a) {
        int temp;
        //首先确定h的值
        int N = a.length;
        int h = 0;
        while (h < N/2) {
            h = h * 2 + 1;
        }
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (a[j] < a[j - h]) {
                        temp = a[j];
                        a[j] = a[j - h];
                        a[j - h] = temp;
                    }
                }
            }
            h = h/2;
        }
    }
}

5. 归并排序

public class MergeSort {
    private static int[] assist;

    public void sort(int[] a){
        assist = new int[a.length];

        int lo = 0;
        int hi = a.length-1;
        sort(a, lo, hi);
    }

    
    public void sort(int[] a, int lo, int hi){
        if (lo >= hi){	// 注意此处需要判断条件，以终止递归
            return;
        }
        int mid = lo + (hi-lo)/2;

        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }

    public void merge(int[] a, int lo, int mid, int hi){
        int i = lo;     //该指针指向assist数组
        int p1 = lo;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= hi){
            if (a[p1] < a[p2]){
                assist[i++] = a[p1++];
            }else {
                assist[i++] = a[p2++];
            }
        }

        while (p1 <= mid){
            assist[i++] = a[p1++];
        }
        while (p2 <= hi){
            assist[i++] = a[p2++];
        }

        //复制数组assist给a，注意 index从lo到hi
        for (int index = lo; index <= hi; index++) {
            a[index] = assist[index];
        }
    }

    public static void main(String[] args) {
        int[] a = {2,3,1,5,4,6,7,9,8};
        System.out.println("排序前==========");
        for (int i : a) {
            System.out.print(i+" ");
        }
        System.out.println(" ");
        new MergeSort().sort(a);
        System.out.println("排序后==========");
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
}

6. 快速排序

public class QuickSort {
    
    public void sort(int[] a){
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }
    public void sort(int[] a, int lo, int hi){
        if (lo >= hi){
            return;
        }
        //对a数组中，从lo到hi的元素进行切分
        int part = partition(a, lo, hi);
        //对左边分组中的元素进行排序
        sort(a, lo, part-1);
        sort(a, part+1, hi);
    }
    public int partition(int[] a, int lo, int hi){
        int temp;
        int key = a[lo]; // 最左边元素做基准
        int left = lo;
        int right = hi +1; //最右边元素下一个
        //进行切分
        while (true){
            while (key <= a[--right]){//循环停止，证明找到了一个比基准值小的元素
                if (right == lo){
                    break;  //已经扫描到最左边了，无需继续扫描
                }
            }
            while (a[++left] <= key){
                if (left == hi){
                    break;
                }
            }
            if (left >= right){
                break;  //扫描完了所有元素，结束循环
            }else {
                //交换left和right索引处的元素
                temp = a[left];
                a[left] = a[right];
                a[right] = temp;
            }
        }
        //交换最后right索引处和基准值所在的索引处的值
        temp = a[lo];
        a[lo] = a[right];
        a[right] = temp;

        return right;   //right就是切分的界限
    }

    public static void main(String[] args) {
        int[] a = {1,4,7,3,2,6,9,8,0};
        System.out.println("排序前===========");
        for (int i : a) {
            System.out.print(i+" ");
        }
        new QuickSort().sort(a);
        System.out.println(" ");
        System.out.println("排序后==========");
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
}