快速排序

DataPipeline 發(fā)布于2019-08-16 10:46 / 686人閱讀

摘要：時間復雜度的簡介算法的時間復雜度是一個函數(shù)，描述了算法的執(zhí)行時間。通常使用大符號來表示。在進行算法分析時，語句總的執(zhí)行次數(shù)是關于問題規(guī)模的函數(shù)，進而分析隨的變情況來確定的數(shù)量級。

時間復雜度的簡介

算法的時間復雜度是一個函數(shù)，描述了算法的執(zhí)行時間。通常使用大O符號來表示。
在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變
情況來確定T(n)的數(shù)量級。

一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù),O(f(n))
分析:隨著n的增長，算法執(zhí)行的時間的增長率和 f(n) 的增長率成正比，
所以 f(n) 越小，算法的時間復雜度越低，算法的效率越高。

常見的時間復雜度分析
有幾重for循環(huán)，只有一重則時間復雜度為O(n)，二重則為O(n^2)依此類推
如果有二分則為O(logn)，二分例如二分查找，如果一個for循環(huán)套一個二分，
那么時間復雜度則為O(nlogn)

常見的時間復雜度
常數(shù)階O(1),對數(shù)階O(  ),線性階O(n),
線性對數(shù)階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k),指數(shù)階O(2^n)
隨著問題規(guī)模n的不斷增大，上述時間復雜度不斷增大，算法的執(zhí)行效率越低。

快速排序

快速排序的分析

快速排序的流程

快速排序的代碼實現(xiàn)

    public static void main(String[] args) {
        //1.定義要排序的數(shù)組
        int[] arr = {5,2,6,8,4,3,7};
        //2.定義變量low保存數(shù)組中第一個元素的索引
        int low = 0;
        //3.定義變量high保存數(shù)組中最后一個元素的索引
        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.定義變量來保存數(shù)組第一個元素在數(shù)組拍完序后的位置
        int position;
        if(low < high){
            position = findPosition(arr,low,high);
            //2.對小于數(shù)組中第一個數(shù)的部分進行快速排序
            quickSort(arr, low, position - 1);
            //3.對大于數(shù)組中第一個數(shù)的部分進行快速排序
            quickSort(arr, position + 1, high);
        }
    }

    //查找第一個元素在要排序的數(shù)中的位置
    //當low=high的時候，low和high的值就是第一個元素排序完在數(shù)組中的值
    public static int findPosition(int[] arr,int low,int high){
        //1.定義變量temp保存數(shù)組的第一個元素
        int temp = arr[low];
        while(low < high){
            //2.high索引對應的元素比temp大，--high
            while(low < high && arr[high] >= temp){
                --high;
            }
            //3.循環(huán)結束,high索引對應的值小于第一個元素，將high索引對應的值賦值給low索引對應的值
            arr[low] = arr[high];
            //4.low索引對應的元素比temp小，++low
            while(low < high && arr[low] <= temp){
                ++low;
            }
            //5.循環(huán)結束,low索引對應的值大于第一個元素，將low索引對應的值賦值給high索引對應的值
            arr[high] = arr[low];
        }
        //6.將數(shù)組第一個元素放置在數(shù)組排序完的位置上
        arr[low] = temp;
        //7.最外層循環(huán)接收，low=high，第一個元素在拍完序中的位置就是low和hight的值
        return low;
    }

快速排序的時間復雜度為O(nlogn)
冒泡排序和選擇排序的時間復雜度為O(n^2)

GPU云服務器云服務器快速排序快速排序函數(shù) 快速排序算法 php快速排序

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/70429.html

快速排序就這么簡單

摘要：快速排序的介紹來源百度百科快速排序由在年提出。快速排序是面試出現(xiàn)的可能性比較高的，也是經(jīng)常會用到的一種排序，應該重點掌握。前面一個章節(jié)已經(jīng)講了遞歸了，那么現(xiàn)在來看快速排序就非常簡單了。快速排序就這么簡單從前面已經(jīng)講解了冒泡排序、選擇排序、插入排序了，本章主要講解的是快速排序，希望大家看完能夠理解并手寫出快速排序的代碼，然后就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。 ...

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

摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...

AlanKeene 2019-08-22 11:11 評論0 收藏0
Javascript實現(xiàn)冒泡排序與快速排序以及對快速排序的性能優(yōu)化

摘要：實現(xiàn)快速排序介紹通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。冒泡排序介紹重復遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后冒泡到數(shù)組的末端。假如數(shù)組...

dadong 2019-08-23 15:08 評論0 收藏0
怎樣測試程序的平均性能

標準庫中的sort函數(shù)，是快速排序算法的典型實現(xiàn)。算法將含有n個元素的序列排序，平均需要 O(n log n) 時間。上周，我提出了測試一個程序的性能比測試其功能更難這個觀點。確認程序的性能達到標準以及確定標準的含義都十分困難。接下來，我會繼續(xù)討論標準庫中的sort(排序)函數(shù)。sort函數(shù)實現(xiàn)了快速排序算法，快速排序算法平均可以在 O(n log n) 時間內(nèi)對含有n個元素的序列進行排序...

mochixuan 2019-05-29 16:19 評論0 收藏0