五种排序算法的比较

五种排序算法的比较:
冒泡排序、插入排序、选择排序均是原地排序,即空间复杂度为O(1),平均时间复杂度O(n^2)
其中选择排序最好最坏均是O(n*n),但它不是稳定的,因此不如插入排序更受欢迎

归并排序:时间复杂度为在任何情况下都O(nlogn),归并是稳定的、但并不是原地排序,它使用了临时数组,即空间复杂度为O(n)
快速排序:大部分情况下时间复杂度为O(nlogn),极端情况下为O(n^2),主要考虑分区点的选取。快排不是稳定的,是原地排序,空间复杂度为O(1)

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月21日 下午9:47:08
 * ******************************************/
package ren.laughing.code.Sort;

public class Sort {

    /**
     * 冒泡排序
     * 
     * @param arr arr
     */
    public static void bubbleSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                // 循环判断,把大数浮上去
                if (arr[j + 1] < arr[j]) {
                    // swap
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     * 
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < length - 1; i++) {
            int j = i + 1;
            int flag = arr[j];
            for (; j > 0; j--) {
                if (arr[j - 1] > flag) {
                    // 每次插入前,较大的其他元素均后移
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = flag;
        }
    }

    /**
     * 选择排序:交换的是位置
     * 
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < length - 1; i++) {
            // 记录最小值的位置
            int index = i;
            for (int j = i + 1; j < length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            // 交换值,不稳定的排序
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }

    /**
     * 归并排序 递归
     * 
     * @param arr   arr
     * @param start start
     * @param end   end
     */
    public static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = start + (end - start) / 2;
        mergeSort(arr, start, middle);
        mergeSort(arr, middle + 1, end);
        merge(arr, start, middle, end);
    }

    /**
     * 归并方法,将两个数组归并成一个有序数组
     * 
     * @param arr    arr
     * @param start  start
     * @param middle middle
     * @param end    end
     */
    private static void merge(int[] arr, int start, int middle, int end) {
        // 申请临时空间保存排序后的数组,排序后再还原至原数组arr
        int[] temp = new int[end - start + 1];
        int i = start, j = middle + 1, k = 0;
        while (i <= middle && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= middle) {
            temp[k++] = arr[i++];
        }
        while (j <= end) {
            temp[k++] = arr[j++];
        }
        // 赋值给原数组
        for (int t = 0; t < temp.length; t++) {
            arr[start + t] = temp[t];
        }
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        // 先找出中间点
        int partition = partition(arr, start, end);
        quickSort(arr, start, partition - 1);
        quickSort(arr, partition + 1, end);
    }

    private static int partition(int[] arr, int start, int end) {
        // 分区点的选取是重点,这里选择末尾的点
        int flag = arr[end];
        int j = start;// 分区的最终位置
        for (int i = start; i < end; i++) {
            if (arr[i] < flag) {
                // 交换arr[i]和arr[j]
                int temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
                j++;
            }
        }
        // 交换arr[j]和arr[end]
        int temp2 = arr[end];
        arr[end] = arr[j];
        arr[j] = temp2;
        return j;

    }

    public static void main(String[] args) {
        int[] arr = { 2452672803 };
        // bubbleSort(arr);
        // insertSort(arr);
        // selectSort(arr);
        // mergeSort(arr, 0, arr.length - 1);
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注