本文共 5496 字，大约阅读时间需要 18 分钟。

/** * 快排概念： * 快排也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的；在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边， * 比它小的元素移动到数组的另一边，从而将数组拆成两个部分，这种思路叫做分治法 * * 时间复杂度： * 原数组在分支法的思想下，没一轮都会被拆分为两部分，所以遍历的轮数为logn,每一轮的比较和交换需要把数组全部遍历一遍， * 这个时间复杂度是O(n),所以总的平均时间复杂度是O(nlogn) * 但是如果将原本逆序的数列排序成顺序数列，整个数列并没有被分成两半，每一轮都只确定来基准元素的位置，数列的第一个元素要么是最大值要么是最小值， * 无法发挥分支法的优势，这个时候快速排序需要进行n轮，时间复杂度退化为O(n平方)。 * 解决思路是：随机选择一个元素作为基准元素 * *//**     * 递归的方式     * @param arr     * @param startIndex     * @param endIndex     */    public static void quickSort(int[] arr,int startIndex,int endIndex){        if(arr == null || startIndex >= endIndex){            return;        }        //得到基准元素位置        int pivotIndex = partition(arr,startIndex,endIndex);        //根据基准元素位置分成两部分进行递归        quickSort(arr,startIndex,pivotIndex - 1);        quickSort(arr,pivotIndex + 1,endIndex);    }    /**     * 循环方式     * 引入一个存储Map类型元素的栈，用于存储每一次交换时的起始下标和结束下标     * 每一次循环，都会让栈顶元素出栈，通过partition方法方法进行分支，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。     * 当栈为空时，说明排序已经完毕，推出循环     */    public static void quickSort2(int[] arr,int startIndex,int endIndex){        Stack

/** * 冒泡排序，基本优化 * 冒泡排序思想：把相邻两个元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置，当一个元素小于或等于右侧相邻元素时，位置不变。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作 * 为原地稳定算法，时间复杂度为n²，最好时间复杂度为n，平均和最坏情况为n² * 采用双循环进行排序，外部循环控制所有回合，内部循环实现每一轮的冒泡处理，先进行元素比较，再进行元素交换 * * @param arr */public static void bubbleSort(int[] arr) {    for (int i = 0; i < arr.length - 1; i++) {        //有序标记，每一轮的初始致都为true        boolean isSorted = true;        for (int j = 0; j < arr.length - i - 1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;                //因为有元素交换，所以是无序的                isSorted = false;            }        }        if (isSorted) {            break;        }    }}/** * 冒泡排序优化 * sortBorder是无序数列的边界，在每一轮排序过程中，处于sortBorder之后的元素不需要进行比较了，肯定是有序的 * @param arr */public static void bubbleSort2(int[] arr) {    //记录最后一次交换的位置    int lastExchangeIndex = 0;    //无序数列的边界，每次比较只需要比较到此为止    int sortBorder = arr.length - 1;    for (int i = 0; i < arr.length; i++) {        //有序标记，每一轮的初始致都为true        boolean isSorted = true;        for (int j = 0; j < sortBorder; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;                //因为有元素交换，所以是无序的                isSorted = false;                //更新为最后一次交换元素的位置                lastExchangeIndex = j;            }        }        sortBorder = lastExchangeIndex;        if (isSorted) {            break;        }    }}

/** * 插入排序 * 首先我们将数组中数据分为两个区间，已排序和未排序区间。初始化时已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序算法中的元素，在已排序算法中找到合适的插入位置将其插入 * 原地稳定算法，时间复杂度为O(n2),但它赋值次数比冒泡的少（插入赋值一次，冒泡3次），所以效率比冒泡的高 * @param data */public static void insertSort(int[] data){    if(data == null || data.length <= 1) return;    for (int i=1;i
   
    =0 ;j--){            if(data[j]>val){                //数据移动                data[j+1] = data[j];            }else {                break;            }        }        //找到位置插入        data [j + 1] = val;    }}public static void main(String[] args) {    int[] data ={6,11,3,9,8};    quickSort(data);    System.out.println("快排结果为"+ Arrays.toString(data));    data =new int[]{6,11,3,9,8};    mergeSort(data,0,data.length-1);    System.out.println("归并排序结果为"+ Arrays.toString(data));    data =new int[]{6,11,3,9,8};    bubbleSort(data);    System.out.println("冒泡排序结果为"+ Arrays.toString(data));    data =new int[]{6,11,3,9,8};    insertSort(data);    System.out.println("插入排序结果为"+ Arrays.toString(data));}
   

转载地址：http://dhsvi.baihongyu.com/