สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องเรียงลำดับจากน้อยไปมาก ดังนั้นหากอาร์เรย์เป็นแบบ [5,2,3,1] ผลลัพธ์จะเป็น [1,2,3,5]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างเมธอดเดียวที่เรียกว่า partition ซึ่งจะเป็นอาร์เรย์ ต่ำและสูง
-
ตั้งค่า pivot :=ต่ำ
-
สำหรับผมอยู่ในช่วงต่ำไปสูง – 1
-
ถ้า nums[i]
-
-
สลับ nums[pivot] และ nums[high]
-
กำหนดวิธีการที่เรียกว่า sortArr() ซึ่งจะใช้อาร์เรย์ ต่ำและสูง
-
ถ้าต่ำ>=สูงก็คืน
-
partitionIndex :=พาร์ทิชัน (ตัวเลข ต่ำ สูง)
-
sortArr(nums, ต่ำ, partitionIndex – 1)
-
sortArr(nums, partitionIndex + 1, สูง)
-
เรียก sortArr() จากวิธีหลักโดยส่งค่าต่ำและสูงเป็น 0 และขนาดของ arr – 1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
int partition(vector <int>& nums, int low, int high){
int pivot = low;
for(int i = low; i < high; i++){
if(nums[i] < nums[high]){
swap(nums[i], nums[pivot]);
pivot++;
}
}
swap(nums[pivot], nums[high]);
return pivot;
}
void sortArr(vector <int>& nums, int low, int high){
if(low >= high) return;
int partitionIndex = partition(nums, low, high);
sortArr(nums, low, partitionIndex - 1);
sortArr(nums, partitionIndex + 1, high);
}
vector<int> sortArray(vector<int>& nums) {
sortArr(nums, 0, nums.size() - 1);
return nums;
}
};
main(){
vector<int> v1 = {5,2,3,1};
Solution ob;
print_vector(ob.sortArray(v1));
} อินพุต
[5,2,3,1]
ผลลัพธ์
[1,2,3,5]
