美文网首页
快速排序

快速排序

作者: 吕建雄 | 来源:发表于2020-01-16 22:41 被阅读0次

快速排序原理:

循环一趟,将待排序的数组分为两部分,其中一部分的值小于另一部分;然后继续对这两部分进行排序,以达到整个序列有序的目的;

class QuickSort {

    public static void main(String[] argv){

        int[] arr = {50,10,90,30,70,40,80,60,20};

        System.out.println("排序前...");

        for(int i=0;i<arr.length;i++) {

            System.out.println(arr[i]);

        }

        sort(arr,0,arr.length-1);

        System.out.println("排序后...");

        for(int i=0;i<arr.length;i++){

            System.out.println(arr[i]);

        }

    }

//分割数组

    public static int position(int[] arr, int low, int high){

    //哨兵值(此值很关键,决定整个排序的复杂度)

    int targetValue = arr[low];

    while(low < high){

        // 从右向左比较

        while(low<high&&arr[high]>=targetValue){

            high--;

        }

        //将low与high对应的值交换

        if(arr[high]<targetValue)

            int tmp = arr[high];

            arr[high]=arr[low];

            arr[low] = tmp;

        }

        // 从左向右比较

          while(low<high&&arr[low]<=targetValue){

            low++;

        }

        //交换low与high对应的值

        if(arr[low]>targetValue){

            int tmp = arr[low];

            arr[low] = arr[high];

            arr[high] = tmp;

        }

       }

        //返回low=4

        return low;

    }

    //递归比较各部分

    public static void sort(int[] arr, int low, int high){

        if (low < high) {

            int p = position(arr,low,high);

            sort(arr, low, p-1);

            sort(arr, p+1, high);

        }

    }

}

代码实现

分析:(只进行了一次循环的分析,其他类似)

第一轮:(50,10,90,30,70,40,80,60,20)

low=0,high=8, low

targetValue = 50

arr[high]=20<50

20<50,while循环不走,high=8,low=0

arr[high]=20 < 50

执行if内容

交换low与high的值

至此数组变更为:20,10,90,30,70,40,80,60,50

low=0,high=8,low<high

arr[low]=20<50

进入while循环low++

low=1,high=8,low

arr[low]=10<50

进入while循环low++

low=2,high=8,low

arr[low]=90>50

跳出循环,low=2,high=8

arr[low]=90 > 50

执行if块

至此数组变更为:20,10,50,30,70,40,80,60,90

第二轮:

low=2,high=8, low<high

arr[high]=90>50

进入到while循环high--

low=2,high=7, low

arr[high]=60>50

进入while循环high--

low=2,high=6,low

arr[high]=80>50

进行while循环high--

low=2,high=5,low

arr[high]=40 < 50

跳出while循环,high= 5,low = 2

arr[high]=40<50

进入到if块

交换low与high的值

至此数组变更为:20,10,40,30,70,50,80,60,90

low=2,high=5,low<high

arr[low]=40<50

进入到while循环low++

low=3,high=5,low

arr[low]=30<50

进入到while循环low++

low=4,high=5,low

arr[low]=70>50

跳出循环,low=4,high=5

arr[low]=70 > 50

执行if块

至此数组变更为:20,10,40,30,50,70,80,60,90

第三轮:(20,10,40,30,50,70,80,60,90)

low=4,high=5,low

arr[high]= 70>50

进入while循环,high--

low=4,high=4,low==high不执行while继续向下

由于low==high所以整个外出while会跳出,返回4(一轮比较后)

下标为4的全部小与50,下标大与40的全部大于50

然后再用同样的方法对分割的两个数组进行排序...以此类推

说明:

在最优的情况下,快排的时间复杂度为O(nlogn)

在最坏的情况下,快排的时间复杂度为O(n²)

平均数量级为O(nlogn)

快排最重要的是哨兵值的位置,若正好在中间,则平衡,性能最好,若哨兵值要么最大,要么最小,那么其会出现偏树,导致性能差;通常的优化方法是哨兵值通过三数取中来实现,一般取最左端、右端和中间三个数;将哨兵值设置为三个数的中间值

相关文章

  • 七大排序算法之快速排序

    七大排序算法之快速排序 @(算法笔记)[排序算法, 快速排序, C++实现] [TOC] 快速排序的介绍: 快速排...

  • 面试准备--排序

    堆排序 快速排序(simple) 快速排序(regular) 归并排序 Shell排序 插入排序 选择排序 冒泡排序

  • 排序

    插入排序 选择排序 冒泡排序 归并排序 快速排序* 三路快速排序

  • 算法笔记01-排序#2

    快速排序敢叫快速排序,那它一定得快。 快速排序 概述 快速排序也是分治排序的典型,它快,而且是原地排序。不过,要防...

  • PHP 实现快速排序

    导语 这篇了解下快速排序。 快速排序 快速排序(英语:Quicksort),又称划分交换排序(partition-...

  • 快速排序的Python实现

    目录 快速排序的介绍 快速排序的Python实现 快速排序的介绍 快速排序(quick sort)的采用了分治的策...

  • 数据结构与算法 快速排序

    起因:快速排序,又称分区交换排序,简称快排,之前没有了解过,抽空学习一下。 快速排序 1 快速排序 快速排序的定义...

  • 数组-快速排序

    采用快速方式对数组进行排序 快速排序百科:快速排序(Quicksort)是对冒泡排序算法的一种改进.快速排序是通过...

  • OC数据结构&算法

    更多整理资料尽在?一平米小站 目录 选择排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序 选...

  • 要成功就做一百题-94

    题目名称 今天来几个排序,都是经典题目,包括带拆分的快速排序,堆排序,归并排序。 描述 快速排序快速排序核心就是分...

网友评论

      本文标题:快速排序

      本文链接:https://www.haomeiwen.com/subject/blyqzctx.html