十大排序

public class BubbleSort {

    public static void main(String[] args) {

        int[] arr = {3, 2, 5, 4, 1, 6, 9, 7, 8, 0};
        BubbleSort.sort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

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

    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}

import java.util.Arrays;

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr, int bucketSize) {
        int maxVal = Integer.MIN_VALUE, minVal = Integer.MAX_VALUE;
        for (int item : arr) {
            maxVal = Math.max(maxVal, item);
            minVal = Math.min(minVal, item);
        }

        int[][] buckets = new int[(maxVal - minVal) / bucketSize + 1][0];
        for (int item : arr) {
            int bucketIndex = (item - minVal) / bucketSize;
            int[] newBucket = Arrays.copyOf(buckets[bucketIndex], buckets[bucketIndex].length + 1);
            newBucket[newBucket.length - 1] = item;
            buckets[bucketIndex] = newBucket;
        }

        int index = 0;
        for (int[] bucket : buckets) {
            BubbleSort.sort(bucket);
            for (int item : bucket) {
                arr[index++] = item;
            }
        }
    }
}

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr) {
        int maxVal = Integer.MIN_VALUE, minVal = Integer.MAX_VALUE;
        for (int item : arr) {
            maxVal = Math.max(maxVal, item);
            minVal = Math.min(minVal, item);
        }

        int[] bucket = new int[maxVal - minVal + 1];

        for (int item : arr) {
            bucket[item]++;
        }

        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }
}

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr) {
        for (int i = arr.length >> 1; i >= 0; i--) {
            heap(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heap(arr, 0, i);
        }
    }

    private static void heap(int[] arr, int root, int len) {
        int rootIndex = root, leftIndex = rootIndex * 2 + 1, rightIndex = rootIndex * 2 + 2;

        if (leftIndex < len && arr[rootIndex] < arr[leftIndex]) {
            rootIndex = leftIndex;
        }
        if (rightIndex < len && arr[rootIndex] < arr[rightIndex]) {
            rootIndex = rightIndex;
        }

        if (rootIndex != root) {
            swap(arr, root, rootIndex);
            heap(arr, rootIndex, len);
        }
    }

    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {

            int tmp = arr[i];
            int index = i - 1;
            while (index >= 0 && arr[index] > tmp) {
                arr[index + 1] = arr[index--];
            }
            arr[index + 1] = tmp;
        }
    }
}

import java.util.Arrays;

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr) {

        if (arr.length < 2) return;

        int mid = arr.length >> 1;
        int[] leftArr = Arrays.copyOfRange(arr, 0, mid);
        int[] rightArr = Arrays.copyOfRange(arr, mid, arr.length);

        sort(leftArr);
        sort(rightArr);

        int index = 0;
        while (leftArr.length > 0 && rightArr.length > 0) {
            if (leftArr[0] <= rightArr[0]) {
                arr[index++] = leftArr[0];
                leftArr = Arrays.copyOfRange(leftArr, 1, leftArr.length);
            } else {
                arr[index++] = rightArr[0];
                rightArr = Arrays.copyOfRange(rightArr, 1, rightArr.length);
            }
        }
        while (leftArr.length > 0) {
            arr[index++] = leftArr[0];
            leftArr = Arrays.copyOfRange(leftArr, 1, leftArr.length);
        }
        while (rightArr.length > 0) {
            arr[index++] = rightArr[0];
            rightArr = Arrays.copyOfRange(rightArr, 1, rightArr.length);
        }
    }

}

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr, int left, int right) {
        if (left >= right) return;
        int index = left + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[left]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, left, index - 1);
        sort(arr, left, left - 1);
        sort(arr, left + 1, right);
    }

    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}

public class RadioSort {

    public static void main(String[] args) {

        int[] arr = {3, 2, 5, 4, 1, 6, 9, 7, 8, 0};
        RadioSort.sort(arr);

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int item : arr) {
            max = Math.max(max, item);
        }

        // 计算位数
        int point = 1;
        while (max / 10 > 0) {
            max = max / 10;
            point++;
        }

        int[] bucket = new int[arr.length];

        int div = 1;
        for (int i = 1; i <= point; i++, div *= 10) {

            for (int item : arr) {
                bucket[item / div % 10] = item;
            }

            int index = 0;
            for (int item : bucket) {
                arr[index++] = item;
            }
        }
    }
}

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

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

    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}

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

        for (int i : arr) {
            System.out.print(i + "   ");
        }
    }

    public static void sort(int[] arr) {
        for (int i = arr.length >> 1; i > 0; i >>= 1) {

            for (int j = i; j < arr.length; j += i) {
                int tmp = arr[j];
                int index = j - i;
                while (index >= 0 && arr[index] > tmp) {
                    arr[index + i] = arr[index];
                    index -= i;
                }
                arr[index + i] = tmp;
            }
        }
    }
}