Java數(shù)據結構與算法——快速排序

Panda 發(fā)布于2019-08-16 11:12 / 1191人閱讀

摘要：快排是一種不穩(wěn)定的排序算法，在經過排序后，等值的元素的相對位置可能發(fā)生改變。

聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據結構與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇文章介紹排序算法中最常用也是面試中最容易考到的排序算法——快排，包括快排的思想和原理、java快排代碼、快排的特點性能和快排的適用場景。

0、其他排序算法索引(待更)

java數(shù)據結構與算法——桶排序
java數(shù)據結構與算法——插入排序

1、快速排序思想及原理

事實上，快速排序是堆冒泡排序的一種改進。

它的基本思想是：通過一趟排序將要排序的數(shù)據分割為兩部分，第一部分所有數(shù)據比第二部分的所有數(shù)據小，按照這種思路將兩部分數(shù)據再次分別進行快速排序，可以使用遞歸完成，最終使得整個數(shù)據序列有序。

具體來講，在待排數(shù)據中找一個基準數(shù)據（通常取第一個數(shù)），接下來將待排數(shù)據中比基準數(shù)據小的放在待排數(shù)據的左側，將比待排數(shù)據中比基準數(shù)據大的放在待排數(shù)據右側。此時，左右兩個分區(qū)的元素相對有序，接著采用上述思路繼續(xù)對左右兩個分區(qū)繼續(xù)排序，直到各分區(qū)只有一個元素位置。這里用到了一個典型的分治思想。下面舉例說明：

待排序列依次為47、29、71、99、78、19、24、47。為了區(qū)分兩個47，將后面的47下面增加一個下劃線。

步驟：
1、選取一個基準數(shù)，一般選第0個元素47。
2、將比基準數(shù)小的移動到左側，比基準數(shù)大的移動到右側，相等的不移動，此時基準數(shù)位置為K。
3、對左右兩側重復步驟1和步驟2，直到左右側細分到只有一個元素。

快排的難點也就是在第2步，怎么移動各個數(shù)據？
<1> 首先從數(shù)列的右邊開始往左找，設下標為i，也就是i--操作，找到第一個比基準數(shù)小的值，讓他與基準數(shù)交換；
<2> 接著開始從左往右找，設下標為j，也就是j++，找到第一個比基準數(shù)大的值，讓他與基準數(shù)交換位置；
<3> 重復1和2，直到i和j相遇時結束，最后基準值所在位置為k。

2、java快排代碼

public class QuickSort {
    private int[] array;
    public QuickSort(int[] array){
        this.array = array;
    }
    
    public void printSort(){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
    
    public void sort(){
        quicksort(array,0,array.length -1);
    }
    
    private void quicksort(int[] array,int begin,int end){
        if(beginbase){ //從右往左掃，如果元素比基準值大
                    j--;  //則右邊標記--，直到找到第一個比基準值小的，停止掃描
                }
                if(i
測試代碼
public class SortTest {
    public static void main(String[] args) {
        teseQuickSort();
    }

    private static void teseQuickSort(){
        int[] array = {3,5,7,3,8,9,6,1,0};
        QuickSort qs = new QuickSort(array);
        qs.sort();
        qs.printSort();
    }
}
3、快排的特點及性能
快排是在冒泡排序之上改進而來的，冒泡排序每次只能交換相鄰的兩個元素，而快排則是跳躍式的交換，交換距離很大，總的比較次數(shù)和交換次數(shù)少了很多，速度也快了很多。
快排的平均時間復雜度為O(nlogn)，事實上，大多數(shù)情況下，排序速度要快于這個時間復雜度。快排實際上是采用的一種分而治之的思想，把問題分解為一個個的小問題去逐一解決，最終在把結果組合起來。
快排因為遞歸調用，所以空間復雜度為O(logn)。
快排是一種不穩(wěn)定的排序算法，在經過排序后，等值的元素的相對位置可能發(fā)生改變。
快排基本上被認為是相同數(shù)量級中所有排序算法中平均性能最好的。
4、快排的適用場景
快排由于相對簡單而且性能不錯，所以快排適用于幾乎絕大多數(shù)場合。
其他排序算法索引(待更)
java數(shù)據結構與算法——桶排序
java數(shù)據結構與算法——插入排序
碼字不易，如對您有幫助，歡迎點贊收藏打賞^_^

GPU云服務器云服務器快速排序算法最好的快速排序算法最快速的排序算法 java快速排序

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

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

Java面試題：穩(wěn)定和不穩(wěn)定排序算法之間的區(qū)別-MergeSort與QuickSort

摘要：穩(wěn)定與不穩(wěn)定算法示例以下圖片解釋了穩(wěn)定和不穩(wěn)定的排序是如何工作的這就是穩(wěn)定和不穩(wěn)定排序算法之間的區(qū)別。穩(wěn)定排序算法的一些常見示例是合并排序，插入排序和冒泡排序。 showImg(https://segmentfault.com/img/remote/1460000018913243); 來源 | 愿碼(ChainDesk.CN)內容編輯愿碼Slogan | 連接每個程序員的故事網...

wanghui 2019-08-16 16:46 評論0 收藏0
七大排序算法總結(java)

摘要：前面介紹了七大算法的思想與實現(xiàn)步驟，下面來做一個歸總。直到無序區(qū)中的數(shù)為零，結束排序。步驟以從小到大為例，排序數(shù)組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數(shù)據結構來進行排序的，其中每一個堆都是完全二叉樹。前面介紹了七大算法的思想與實現(xiàn)步驟，下面來做一個歸總。排序方法平均復雜度最壞復雜度最好復雜度輔助空間穩(wěn)定性直接選擇排序 O(n^2...

cartoon 2019-08-14 14:09 評論0 收藏0
Java數(shù)據結構與算法——插入排序

摘要：當序列本身有序時，插入排序的時間復雜度為。因為此時的分區(qū)內數(shù)據往往是近似有序的，所以使用快排并不一定優(yōu)于插入排序。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數(shù)據結構與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇文章介紹排序算法中插入排序算法，包括插入排序的思路，適用場景，性能分析，java代碼等 0、其他排序算法索引(待更) java數(shù)據結構與算法——快速...

騫諱護 2019-08-15 15:19 評論0 收藏0
跳槽季如何快速全面復習面試題

摘要：排序算法和集合工具類排序算法和集合工具類。面試官總是問排序算法也不是在難為你，而是在考察你的編程功底。你首先要理解多線程不僅僅是和那么簡單，整個并發(fā)包下面的工具都是在為多線程服務。去年的這個時候樓主通過兩個月的復習拿到了阿里巴巴的 offer，有一些運氣，也有一些心得，借著跳槽季來臨特此分享出來。簡單梳理一下我的復習思路，同時也希望和大家一起交流討論，一起學習，如果不對之處歡迎指正一...

keke 2019-08-16 14:25 評論0 收藏0
Java排序算法之——快速排序

摘要：代碼片段語言組織能力有限，直接上代碼排序算法之快速排序參數(shù)為需要排序的數(shù)組參數(shù)為數(shù)組的起始下角標即參數(shù)為數(shù)組的最后下角標即經過一輪排序，已經將數(shù)組分為左右兩部分進行遞歸排序總結快速排序的精髓在于分治思想，分而治之，它的時間復雜度為。算法簡述所謂快速排序算法是基于交換排序和遞歸思想的，它的速度的確如名字所示——快！并且這種一算一般被用作數(shù)量級比較大的數(shù)據當中，在大數(shù)據中有著很重要的地...

Yangyang 2019-08-14 12:19 評論0 收藏0