侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 39 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

java排序算法 快速排序 快速排序的优化

SeaDream乄造梦
2022-02-23 / 0 评论 / 0 点赞 / 478 阅读 / 2,045 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

快速排序算法总体的平均时间复杂度是O(nlogn)。

  • 思想(分治法思想)
  • 原数列在每一轮都要被拆分两部分,被拆分后的每一部分在下一轮又分别被拆分为两部分,直到不可再 分为止
  • 最简单的是选择数列的第一个元素。然而这种情况下如果本来数列就是有序的,会出现复杂度为(O(n²))
    */

单边for循环

import java.util.Arrays;

public class 单边for循环 {
    public static void quickSort(int []arr,int startIndex,int endIndex) {
        // 递归结束条件:startIndex大于或等于endIndex时
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(arr,startIndex,endIndex);

        // 根据基准元素,分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }
    /**
     * 分治(单边循环法)
     * @param arr         待交换的数组
     * @param startIndex      起始下标
     * @param endIndex      结束下标
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第1个位置(也可以选择随机位置)的元素作为基准元素

        int pivot = arr[startIndex];
        int mark = startIndex;
        for(int i=startIndex+1; i<=endIndex; i++){
            if(arr[i]<pivot){
                mark ++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;

        return mark;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {4,4,6,5,3,2,8,1};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

双边for循环

import java.util.Arrays;

/**
 * 平均时间复杂度  O(nlogn),最坏情况O(n²)
 */

public class 双边for循环 {
    public static void quickSort (int [] arr,int startIndex,int endIndex) {
        // 递归结束条件:startIndex大于或等于endIndex时
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素的位置
        int pivotIndex = partition(arr,startIndex,endIndex);
        // 根据基准元素,分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }
    /**
     * 分治(单边循环法)
     * @param arr         待交换的数组
     * @param startIndex      起始下标
     * @param endIndex      结束下标
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第1个位置(也可以选择随机位置)的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            //控制right  指针比较 并左移
            while (left<right && arr[right]>pivot) {
                right--;
            }
            //控制left指针比较并右移
            while( left<right && arr[left] <= pivot) {
                left++;
            }
            //交换left和right 指针所指向的元素
            if (left<right) {
                int p = arr[left];
                arr[left]=arr[right];
                arr[right] = p;
            }
        }
        //pivot 和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {4,4,6,5,3,2,8,1};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
0

评论区