常用排序算法的Java实现

冒泡、插入、选择、归并、快速排序的Java实现

/**
 * @author: gethin
 * @create: 2018-05-23 16:21
 * @description: 常用排序算法
 **/
public class Sort {
    public static void main(String[] args) {
        int[] list = {2, 19, 5, 14, 28, 1, 66, 53, 11};
        bubbleSort(list);
        selectionSort(list);
        insertionSort(list);
        mergeSort(list);
        quickSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
    
    /**
     * BubbleSort
     * Continuously compare adjacent elements in each traversal,swapping their values if the elements are not in order.
     */
    public static void bubbleSort(int[] list) {
        //Array may be sorted and next pass not needed
        boolean needNextPass = true;
        for (int i = 0; i < list.length - 1 && needNextPass; i++) {
            needNextPass = false;
            for (int j = 0; j < list.length - i - 1; j++) {
                if (list[j] > list[j + 1]) {
                    int temp = list[j + 1];
                    list[j + 1] = list[j];
                    list[j] = temp;
                    needNextPass = true;
                }
            }
        }
    }
    
    /**
     * SelectionSort
     * Each time the smallest element is selected from the data elements to be sorted,
     * it is stored at the beginning of the sequence until all the data elements to be sorted are finished.
     */
    public static void selectionSort(int[] list) {
        for (int i = 0; i < list.length; i++) {
            int minElementIndex = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[minElementIndex] > list[j]) {
                    minElementIndex = j;
                }
            }
            //Swap the min element with current element.
            int temp = list[i];
            list[i] = list[minElementIndex];
            list[minElementIndex] = temp;
        }
    }
    
    /**
     * InsertionSort
     * Each step will insert current element into appropriate position ,until all the insertion is completed.
     */
    public static void insertionSort(int[] list) {
        for (int i = 1; i < list.length; i++) {
            int currentElement = list[i];
            int j = i;
            for (; j > 0; j--) {
                if (currentElement < list[j - 1]) {
                    list[j] = list[j - 1];
                } else {
                    break;
                }
            }
            list[j] = currentElement;
        }
    }
    
    /**
     * MergeSort
     * step1 Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
     * step2 Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be
     * the sorted list.
     */
    public static void mergeSort(int[] list) {
        if (list.length > 1) {
            int firstLength = list.length / 2;
            int[] first = new int[firstLength];
            System.arraycopy(list, 0, first, 0, firstLength);
            mergeSort(first);
            int secondLength = list.length - list.length / 2;
            int[] second = new int[secondLength];
            System.arraycopy(list, firstLength, second, 0, secondLength);
            mergeSort(second);
            merge(first, second, list);
        }
    }
    
    private static void merge(int[] first, int[] second, int[] temp) {
        int i, j, k = 0;
        for (i = 0, j = 0; i < first.length & j < second.length; ) {
            if (first[i] < second[j]) {
                temp[k++] = first[i++];
            } else {
                temp[k++] = second[j++];
            }
        }
        while (i < first.length) {
            temp[k++] = first[i++];
        }
        while (j < second.length) {
            temp[k++] = second[j++];
        }
    }
    
    /**
     * step1 Pick an element, called a pivot, from the array.
     * step2 Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
     * step3 Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
     */
    public static void quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
    }
    
    private static void quickSort(int[] list, int first, int last) {
        if (first < last) {
            int pivot = partition(list, first, last);
            partition(list, first, pivot - 1);
            partition(list, pivot + 1, last);
        }
    }
    
    private static int partition(int[] list, int first, int last) {
        int pivot = list[first];
        while (first < last) {
            while (first < last && list[last] > pivot) {
                last--;
            }
            if (first < last) {
                list[first] = list[last];
            }
            while (first < last && list[first] < pivot) {
                first++;
            }
            if (first < last) {
                list[last] = list[first];
            }
        }
        list[first] = pivot;
        return first;
    }
}