挖坑法、指針交換法實作快速排序

文章目錄

• 寫在最前
• 快速排序
• 時間複雜度
• • 挖坑法實作
  • 指針交換法實作(雙邊指針)
  • 指針交換法實作(單邊指針)
  • 指針交換法(雙邊)(使用棧實作)
• 參考資料

寫在最前

本文用來記錄自己的工作、學習遇到的問題, 好記性不如爛筆頭, 起的更多的是筆記的作用, 由于本人表達能力、技術水準有限, 本文僅起參考作用, 一切以您實際code為準, 給您帶來的不便敬請諒解; 如果發現哪裡了解不對或者有問題的地方, 歡迎批評指正.

快速排序

同冒泡排序一樣, 快速排序也是交換排序, 但是采用了分治的思想, 是以效率比冒泡排序高很多

冒泡排序每一輪都找出最大的元素到數列的一端; 而快排挑選一個基準元素, 将比基準元素大移動到數列一端, 比基準元素小的移動到另一端, 将數列分成兩部分

下面幾種實作, 推薦指針交換法(雙邊指針), 容易了解

時間複雜度

平均時間複雜度為O(nlogn), 最壞時間複雜度為O(n2)

挖坑法實作

基準元素位置相當于一個坑, 右側的小于基準元素就右側這個位置為新坑; 左側的大于基準元素, 左側這個則為新坑(用新坑的值填舊坑的值, 因為最開始的坑是基準元素, 是以要儲存基準元素值, 最後替換最後坑的值)

//挖坑法 遞歸實作 雙向
public static void quickSort1(int[] arr, int startIndex, int endIndex){
    if(startIndex >= endIndex){
        return;
    }
    int pivotIndex = partition1(arr, startIndex, endIndex);
    quickSort1(arr, startIndex, pivotIndex-1);
    quickSort1(arr,pivotIndex+1, endIndex);
}
//挖坑法
public static int partition1(int[] arr, int startIndex, int endIndex){
    //取第一個元素作為基準元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    //坑的位置!!!!!!!! 初始等于pivot的位置
    int index = startIndex;

    while(right >= left){
        //right指針從右向左移動
        while(right >= left){
            if(arr[right] < pivot){
                // 用新坑的值填舊坑的值 新坑為right位置 結束right指針本次循環
                arr[left] = arr[right];
                index = right;
                left++;
                break;
            }
            right--;
        }
        //left指針從左向右移動
        while(right >= left){
            if(arr[left] > pivot){
                // 用新坑的值填舊坑的值 新坑為left位置 結束left指針本次循環
                arr[right] = arr[left];
                index = left;
                right--;
                break;
            }
            left++;
        }
    }
    //用基準元素替換最後坑的位置
    arr[index] = pivot;
    return index;
}
           

指針交換法實作(雙邊指針)

指針交換法, 雙邊周遊, 右邊找小于pivot的停下, 左邊找大于pivot的停下, 然後左右交換, 最後用pivot和重合位置的元素交換

注意: pivot元素選取影響處理順序, 見代碼注釋詳細說明

//指針交換法 雙邊指針 遞歸實作 雙向
public static void quickSort2(int[] arr, int startIndex, int endIndex){
    if(startIndex >= endIndex){
        return;
    }
    int pivotIndex = partition2(arr, startIndex, endIndex);
    quickSort1(arr, startIndex, pivotIndex-1);
    quickSort1(arr,pivotIndex+1, endIndex);
}
//指針交換法 雙邊周遊, 右邊找小于pivot的停下, 左邊找到大于pivot的停下, 互換位置, 最後将pivot和指針重合處替換
public static int partition2(int[] arr, int startIndex, int endIndex){
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    while(right != left){
        // 注意: 因為上面pivot選擇的startIndex處的元素, 是以下面順序必須是先處理right指針, 再處理left指針; 
        // 了解是先處理left指針可能會多換出去一步, 最後pivot和重合點交換的時候不對了
        // pivot如果選擇endIndex處的元素, 則先處理left, 後處理right可以
        while(right > left && arr[right] >= pivot){
            right--;
        }
        while(right > left && arr[left] <= pivot){
            left++;
        }
//            while(right > left && arr[right] >= pivot){
//                right--;
//            }
        if(left < right){
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    //pivot指針和重合點交換 左邊都小于pivot  右邊都大于pivot 此輪結束
    int p = arr[left];
    arr[left] = arr[startIndex];
    arr[startIndex] = p;
    return left;
}
           

指針交換法實作(單邊指針)

//指針交換法 遞歸實作 單邊
public static void quickSort3(int[] arr, int startIndex, int endIndex){
    if(startIndex >= endIndex){
        return;
    }
    int pivotIndex = partition3(arr, startIndex, endIndex);
    quickSort3(arr, startIndex, pivotIndex-1);
    quickSort3(arr,pivotIndex+1, endIndex);
}
//指針交換法 單邊周遊
public static int partition3(int[] arr, int startIndex, int endIndex){
    int pivot = arr[startIndex];
    int mark = startIndex;
    for(int i = startIndex+1; i <= endIndex; i++){
        if(arr[i] < pivot){
            mark++;
            int temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
        }
    }
    //注意這裡啊
    int temp = arr[mark];
    arr[mark] = pivot;
    arr[startIndex] = temp;
    return mark;
}
           

指針交換法(雙邊)(使用棧實作)

絕大多數遞歸實作的問題都可以使用棧來實作, 因為遞歸調用本身就是一個函數棧

進入一個新方法, 相當于入棧; 方法傳回, 相當于出棧; 遞歸轉化棧, 在棧中存儲每一次方法調用的參數

//快排 棧實作 使用的雙邊、指針交換法
public static void quickSortWithStack(int[] arr, int startIndex, int endIndex) {
    //用一個集合棧來代替遞歸的函數棧
    Stack<Map<String, Integer>> stack = new Stack<>();
    //整個數列的起止下标 以哈希的形式入棧
    Map rootParam = new HashMap();
    rootParam.put("startIndex", startIndex);
    rootParam.put("endIndex", endIndex);
    stack.push(rootParam);
    //循環結束條件 棧為空時結束
    while(!stack.isEmpty()){
        //棧頂元素出棧 得到起止下标
        Map<String, Integer> param = stack.pop();
        //得到基準元素位置 partition2()方法見上面快排雙邊指針遞歸實作的partition2()
        int pivot = partition2(arr, param.get("startIndex"), param.get("endIndex"));
        //根據基準元素分成兩部分 每一部分的起止下标入棧
        if(param.get("startIndex") < pivot - 1){
            Map<String, Integer> leftParam = new HashMap<>();
            leftParam.put("startIndex", param.get("startIndex"));
            leftParam.put("endIndex", pivot - 1);
            stack.push(leftParam);
        }
        if(param.get("endIndex") > pivot + 1){
            Map<String, Integer> leftParam = new HashMap<>();
            leftParam.put("startIndex", pivot + 1);
            leftParam.put("endIndex", param.get("endIndex"));
            stack.push(leftParam);
        }
    }
}
           

參考資料

本文主要是用于自己學習的筆記

參考來源: 小灰的算法之旅