快速排序

DataPipeline 发布于2019-08-16 10:46 / 607人阅读

摘要：时间复杂度的简介算法的时间复杂度是一个函数，描述了算法的执行时间。通常使用大符号来表示。在进行算法分析时，语句总的执行次数是关于问题规模的函数，进而分析随的变情况来确定的数量级。

时间复杂度的简介

算法的时间复杂度是一个函数，描述了算法的执行时间。通常使用大O符号来表示。
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变
情况来确定T(n)的数量级。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数,O(f(n))
分析:随着n的增长，算法执行的时间的增长率和 f(n) 的增长率成正比，
所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。

常见的时间复杂度分析
有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)依此类推
如果有二分则为O(logn)，二分例如二分查找，如果一个for循环套一个二分，
那么时间复杂度则为O(nlogn)

常见的时间复杂度
常数阶O(1),对数阶O(  ),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

快速排序

快速排序的分析

快速排序的流程

快速排序的代码实现

    public static void main(String[] args) {
        //1.定义要排序的数组
        int[] arr = {5,2,6,8,4,3,7};
        //2.定义变量low保存数组中第一个元素的索引
        int low = 0;
        //3.定义变量high保存数组中最后一个元素的索引
        int high = arr.length - 1;
        System.out.println("排序前的元素:" + Arrays.toString(arr));
        quickSort(arr, low, high);
        System.out.println("排序后的元素:" + Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int low,int high){
        //1.定义变量来保存数组第一个元素在数组拍完序后的位置
        int position;
        if(low < high){
            position = findPosition(arr,low,high);
            //2.对小于数组中第一个数的部分进行快速排序
            quickSort(arr, low, position - 1);
            //3.对大于数组中第一个数的部分进行快速排序
            quickSort(arr, position + 1, high);
        }
    }

    //查找第一个元素在要排序的数中的位置
    //当low=high的时候，low和high的值就是第一个元素排序完在数组中的值
    public static int findPosition(int[] arr,int low,int high){
        //1.定义变量temp保存数组的第一个元素
        int temp = arr[low];
        while(low < high){
            //2.high索引对应的元素比temp大，--high
            while(low < high && arr[high] >= temp){
                --high;
            }
            //3.循环结束,high索引对应的值小于第一个元素，将high索引对应的值赋值给low索引对应的值
            arr[low] = arr[high];
            //4.low索引对应的元素比temp小，++low
            while(low < high && arr[low] <= temp){
                ++low;
            }
            //5.循环结束,low索引对应的值大于第一个元素，将low索引对应的值赋值给high索引对应的值
            arr[high] = arr[low];
        }
        //6.将数组第一个元素放置在数组排序完的位置上
        arr[low] = temp;
        //7.最外层循环接收，low=high，第一个元素在拍完序中的位置就是low和hight的值
        return low;
    }

快速排序的时间复杂度为O(nlogn)
冒泡排序和选择排序的时间复杂度为O(n^2)

GPU云服务器云服务器快速排序快速排序函数快速排序算法 php快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70429.html

快速排序就这么简单

摘要：快速排序的介绍来源百度百科快速排序由在年提出。快速排序是面试出现的可能性比较高的，也是经常会用到的一种排序，应该重点掌握。前面一个章节已经讲了递归了，那么现在来看快速排序就非常简单了。快速排序就这么简单从前面已经讲解了冒泡排序、选择排序、插入排序了，本章主要讲解的是快速排序，希望大家看完能够理解并手写出快速排序的代码，然后就通过面试了！如果我写得有错误的地方也请大家在评论下指出。 ...

Faremax 2019-08-15 14:54 评论0 收藏0
算法之旅 | 快速排序法

摘要：今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法快速排序法平均时间复杂度为。快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。 HTML5学堂-码匠：前几期算法之旅跟大家分享了冒泡排序法和选择排序法，它们都属于时间复杂度为O(n^2)的慢排序。今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法—— 快速排序法 [ 平均时间复杂度为O (n l...

AlanKeene 2019-08-22 11:11 评论0 收藏0
Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

摘要：实现快速排序介绍通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。冒泡排序介绍重复遍历要排序的元素列，依次比较两个相邻的元素，前一个元素若比后一个元素大则互换位置。以升序排序为例，最大的元素会在第一次遍历后冒泡到数组的末端。假如数组...

dadong 2019-08-23 15:08 评论0 收藏0
怎样测试程序的平均性能

标准库中的sort函数，是快速排序算法的典型实现。算法将含有n个元素的序列排序，平均需要 O(n log n) 时间。上周，我提出了测试一个程序的性能比测试其功能更难这个观点。确认程序的性能达到标准以及确定标准的含义都十分困难。接下来，我会继续讨论标准库中的sort(排序)函数。sort函数实现了快速排序算法，快速排序算法平均可以在 O(n log n) 时间内对含有n个元素的序列进行排序...

mochixuan 2019-05-29 16:19 评论0 收藏0