[数据结构与算法]java排序算法总结

1.选择排序

public class SelectSort {
    public static void main(String[] args) {
        int[] a = {3, 5, 7, 9, 4, 8, 6, 2, 1, 0};
        show(a);
        sort(a);
        print(a);
    }

    public static void show(int[] array){
        print(array);
        System.out.println(" ");

    }

    public static void sort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int minPos = i;
            findMin(array, i);
        }
    }

    public static void findMin(int[] array, int i) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[i]) {
                swap(array, j, i);
            }
        }
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

2.冒泡排序

public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {3, 5, 7, 9, 4, 8, 6, 2, 1, 0};
//        int[] order = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        show(a);
        sort(a);
        print(a);
    }

    public static int[] sort(int[] array) {
        boolean isSort = false;
        for (int i = array.length - 1; i > 0; i--) {
            isSort = false;
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) swap(array, j, j + 1);
                isSort = true;
            }
            if (!isSort) break;
        }
        return array;

    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

3.插入排序

public class InsertSort {//斗地主 抓牌
    public static void main(String[] args) {
        int[] a = {3, 5, 7, 9, 4, 8, 6, 2, 1, 0};
        //        int[] order = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        show(a);
//        sort(a);
        sortImprove(a);
        print(a);

        long starttime = System.currentTimeMillis();
        long endtime = System.currentTimeMillis();
        System.out.println("运行时间为" + (endtime - starttime) + "ms");
    }


    public static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) swap(array, j, j - 1);
            }
        }
    }

    public static void sortImprove(int[] array) {
        boolean isSort = false;
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                isSort = false;
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    isSort = true;
                }
                if (!isSort) break;
            }
        }
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

4.希尔排序

public class ShellSort {
    public static void main(String[] args) {//上来可以用希尔排序先排一遍，如果能接受的话，就可以了。
        int[] a = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
        sortknuth(a);
        print(a);
    }

    public static void sort(int[] array) {


        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (array[j] < array[j - gap]) swap(array, j, j - gap);
                }
            }
        }
//        int gap = 4;
    }

    public static void sortknuth(int[] array) {
        int h = 1;
        while (h <= array.length / 3) {
            h = h * 3 + 1;
        }

        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (array[j] < array[j - gap]) swap(array, j, j - gap);
                }
            }
        }
//        int gap = 4;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

5.归并排序

public class MergeSort {
    public static void main(String[] args) {
//        int[] a = {1, 4, 7, 8, 2, 3, 5, 9, 11}; //为什么这个数组无法排序总是排序为
        // 1 3 4 5 7 8 2 9 11
        int[] a = {10, 4, 7, 8, 3, 6, 9, 11, 12, 13};//1 3 4 6 7 8 9
        sort(a, 1, 5);
        print(a);
    }

    public static void sort(int[] array, int left, int right) {
        if (left == right) return;
        int mid = left + (right - left) / 2;
        sort(array, left, mid);
        sort(array, mid + 1, right);

        merge(array, left, mid + 1, right);
//        mergebug(array);
    }

    public static void merge(int[] array, int leftPtr, int rightPtr, int rightBound) {
        int mid = rightPtr - 1;
        int[] temp = new int[(rightBound - leftPtr) + 1];

        int i = leftPtr;
        int j = rightPtr;
        int k = 0;

        while (i <= mid && j <= rightBound) {
            temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }

        while (i <= mid) temp[k++] = array[i++];
        while (j <= rightPtr) temp[k++] = array[j++];

        //print(temp);
        for (int m = 0; m < temp.length; m++) {
            array[leftPtr + m] = temp[m];
        }
    }

    /*public static void mergebug(int[] array) {
        int mid = array.length >> 1;
        System.out.println("mid" + mid);
        int[] temp = new int[array.length];

        int i = 0;
        int j = mid;
        int k = 0;

        while (i < mid && j < array.length) {
            temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }

        while (i < mid) temp[k++] = array[i++];
        while (j < array.length) temp[k++] = array[j++];

        print(temp);
    }*/

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

6.快速排序

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {7, 3, 2, 10, 8, 1, 6, 5, 4, 9};
        sort(a, 0, a.length - 1);
        print(a);
    }

    public static void sort(int[] array, int leftBound, int rightBound) {
        if (leftBound >= rightBound) return;
        int mid = partition(array, leftBound, rightBound);
        sort(array, leftBound, mid - 1);
        sort(array, mid + 1, rightBound);
    }

    public static int partition(int[] array, int leftBound, int rightBound) {
        int pivot = array[rightBound];
        int left = leftBound;
        int right = rightBound - 1;

        while (left <= right) {
            while (left <= right && array[left] <= pivot) left++;
            while (left <= right && array[right] > pivot) right--;
            if (left < right) swap(array, left, right);
        }
        swap(array, left, rightBound);
        return left;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

7.计数排序

对数器

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

import static day01_sort.SelectSort.print;

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

    static void checker() {
        boolean same = true;
        for (int times = 0; times <1000 ; times++) {
            int[] arr = getRandomArray();
            int[] arr2 = new int[arr.length];
            System.arraycopy(arr, 0, arr2, 0, arr.length);
            /*print(arr);
            System.out.println(" ");*/

            Arrays.sort(arr);
//        SelectSort.sort(arr2);
//        BubbleSort.sort(arr2);
//        InsertSort.sortImprove(arr2);
//        ShellSort.sort(arr);
//        ShellSort.sortknuth(arr);
//        MergeSort.sort(arr2,0,arr2.length-1);
            QuickSort.sort(arr2,0,arr2.length-1);


            for (int i = 0; i < arr2.length; i++) {
                if (arr[i] == arr2[i]) same = true;
            }
        }

        /*print(arr);
        System.out.println(" ");
        print(arr2);
        System.out.println(" ");*/
        System.out.println(same == true ? "right":"wrong");
    }

    public static void main(String[] args) {
        checker();
    }
}

TimSort

归并排序和二分法快速排序的结合

对数插入排序

荷兰国旗问题