快速排序

DataPipeline 發布于2019-08-16 10:46 / 681人閱讀

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

時間復雜度的簡介

算法的時間復雜度是一個函數，描述了算法的執行時間。通常使用大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快速排序

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/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