Java常见排序

Java常见的排序

选择排序

Selection.java

/**
 * 选择排序：
 *      从未排序的数组中找到最大的或者是最小的放在未排序中第一个
 */
public class Selection {
    public static void main(String[] args) {
        int[] array = {1,7,6,10,9,3,8,4,2,5};
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[i] > array[j]){
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }

        for (int i = 0; i < array.length; i++) {
            System.err.print(array[i]);
            System.err.print("\t");
        }
    }
}

冒泡排序

Bubble.java

/**
 * 冒泡排序，两两比较，把最大的沉下去，把最小的浮上来
 */
public class Bubble {
    public static void main(String[] args) {
        //int[] array = {3,2,1};
        /**
         * 3,2,1
         *
         * 第一次排序
         * 3,2,1->2,3,1
         * 2,3,1->2,1,3
         *
         * 第二次排序
         * 2,1,3->1,2,3
         */
        int[] array = {1,7,6,10,9,3,8,4,2,5};
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length - (1+i); j++) {
                /**
                 * 减多个i减少没必要的排序，因为最大的已经在上次沉到低了，这次只需要找打两两比较之中最大的沉到最后就行了
                 */
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }

        for (int i = 0; i < array.length; i++) {
            System.err.print(array[i]);
            System.err.print("\t");
        }


    }
}

插入排序

Insertion.java

/**
 * 插入排序=有序数组+无序数组
 * 将无序数组的第一个放到有序数组排序
 */
public class Insertion {
    public static void main(String[] args) {
        int[] array = {1,7,6,10,9,3,8,4,2,5};
        for (int i = 1; i < array.length; i++) {
            //i=0即为第一个有序数组
            //大于等于i小于array.length的为无序数组
            //0到i的为有序数组

            //比有序数组最后一个还要小的话，那就需要排序，否则比他大就排序（i-1）就是有序数组的最大的那个了
            if(array[i]<array[i-1]){
                for (int j = 0; j < i; j++) {
                    if(array[j]>array[i]){
                        int temp = array[j];
                        array[j] = array[i];
                        array[i] = temp;
                    }
                }
            }
        }

        for (int i = 0; i < array.length; i++) {
            System.err.print(array[i]);
            System.err.print("\t");
        }
    }
}

快速排序

QuickSort.java

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {3,1,2,5,4};
        quickSort(array,0,array.length-1);
        for (int i = 0; i < array.length; i++) {
            System.err.print(array[i]);
            System.err.print("\t");
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int temp = arr[left];
        while (right > left) {
            // 先判断基准数和后面的数依次比较
            while (temp <= arr[right] && left < right) {
                --right;
            }
            // 当基准数大于了 arr[right]，则填坑
            if (left < right) {
                arr[left] = arr[right];
                ++left;
            }
            // 现在是 arr[right] 需要填坑了
            while (temp >= arr[left] && left < right) {
                ++left;
            }
            if (left < right) {
                arr[right] = arr[left];
                --right;
            }
        }
        arr[left] = temp;
        return left;
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (arr == null || left >= right || arr.length <= 1)
            return;
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid);
        quickSort(arr, mid + 1, right);
    }
}