java實現快速排序

zzzmh 發布于2019-08-16 12:31 / 3266人閱讀

摘要：總的來說，快速排序也是利用了分治法的思想。快速排序的時間復雜度為，這是一種不穩定的排序方法。以下代碼實現以二分法的思路對數組分組以最左邊最右邊中間三個數的中位數為主元確定主元

以上為思路。
總的來說，快速排序也是利用了分治法的思想。
基本步驟：1.先選擇好合適的主元pivot，
2.然后再把比主元小的元素放到主元的左邊（右邊），把較大的元素放到主元的右邊（左邊），
3.接著再以主元為分界點，把數組分為兩個部分，再分別對兩邊的數組重復第二步的操作，
4.最后便實現了有序排列。

快速排序的時間復雜度為O(NlgN)，這是一種不穩定的排序方法。

以下代碼實現

public static void quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        
        if (left < index - 1)
            quickSort(arr, left, index - 1);
    
        if (index < right)
            quickSort(arr, index, right);
    }
    //以二分法的思路對數組分組
    private static int partition(int arr[], int left, int right){
        int i = left, j = right;
        int tmp;
        //以最左邊、最右邊、中間三個數的中位數為主元
        int pivot = findPivot(arr, left, (left+right)>>1, right);
  
        while (i <= j) {
      
            while (arr[i] < pivot)
                i++;

            while (arr[j] > pivot)
                j--;

            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
  
        return i;
    }
    //確定主元
    private static int findPivot(int[] nums, int left, int mid, int right){
        if(nums[left] > nums[right]) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        
        if(nums[left] > nums[mid]) {
            int temp = nums[left];
            nums[left] = nums[mid];
            nums[mid] = temp;
        }
        
        if(nums[mid] > nums[right]) {
            int temp = nums[right];
            nums[right] = nums[mid];
            nums[mid] = temp;
        }
        return  nums[mid];
    }

GPU云服務器云服務器 java快速排序 java遞歸快速排序 java中快速排序 java快速排序泛型

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

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

算法學習之路，排序之快速排序（Java實現）

摘要：接下來我來說明快速排序的思路以及實現的代碼。快速排序思路首先是定義一個變量，把數組的第一個元素的值賦給，然后定義兩個變量指向數組的第一個元素和最后一個元素。今天突然想寫個排序，以前寫過，然后寫了之后一直出錯，然后自己百度了一下，看了別人寫的方法，自己也嘗試著寫了一個。接下來我來說明快速排序的思路以及實現的代碼。快速排序思路：首先是定義一個變量key，把數組的第一個元素的值賦給key...

charles_paul 2019-08-14 15:38 評論0 收藏0
java排序算法(快速排序)

摘要：快速排序思路在數組中尋一中間數，將比中間數小的放在左邊，將比中間數大的放在右邊從左邊開始找，找到比中間數大的，記住，從右邊開始找，找到比中間數小的，然后交換兩邊然后在左邊再尋一中間數，同坐上面的事，右邊也一樣，然后循環實現數組輸出中間值的位快速排序思路在數組中尋一中間數，將比中間數小的放在左邊，將比中間數大的放在右邊從左邊開始找，找到比中間數大的，記住，從右邊開始找，找到比中間數...

khlbat 2019-08-15 17:53 評論0 收藏0
跳槽季如何快速全面復習面試題

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

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

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

cartoon 2019-08-14 14:09 評論0 收藏0