Quicksort ialah salah satu algoritma pengisihan terpantas. Ia memerlukan tatasusunan nilai, memilih salah satu nilai sebagai elemen 'pangsi' dan menggerakkan nilai lain supaya nilai yang lebih rendah berada di sebelah kiri elemen pangsi dan nilai yang lebih tinggi berada di sebelah kanannya.
Isih Pantas berdiri sebagai salah satu algoritma pengisihan yang paling elegan dan cekap dalam dunia algoritma. Tidak seperti algoritma yang lebih mudah seperti Bubble Sort atau Selection Sort, Quick Sort menggunakan strategi bahagi-dan-takluk yang canggih yang menjadikannya lebih pantas dalam amalan. Walaupun Merge Sort juga menggunakan divide-and-conquer, pendekatan pembahagian unik Quick Sort selalunya membawa kepada prestasi dan penggunaan memori yang lebih baik.
Purata Kerumitan Masa: O(n log n)
Kerumitan Masa Kes Terburuk: O(n²)
Kerumitan Ruang: O(log n)
Isih Pantas ialah algoritma pengisihan yang sangat cekap yang berfungsi dengan memilih elemen 'pivot' daripada tatasusunan dan membahagikan elemen lain kepada dua sub-tatasusunan mengikut sama ada ia kurang daripada atau lebih besar daripada pangsi. Tidak seperti Merge Sort, yang membahagikan dahulu dan bergabung kemudian, Quick Sort melakukan pengisihannya semasa proses pembahagian.
Pertimbangkan perbandingan ini dengan algoritma pengisihan lain:
| Algorithm | Time Complexity (Average) | Space Complexity | In-Place? |
|---|---|---|---|
| Quick Sort | O(n log n) | O(log n) | Yes |
| Merge Sort | O(n log n) | O(n) | No |
| Bubble Sort | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(1) | Yes |
| Heap Sort | O(n log n) | O(1) | Yes |
Sebelum kita menyelami pelaksanaan JavaScript bagi algoritma isihan pantas, mari kita ambil pendekatan langkah demi langkah untuk memahami cara algoritma berfungsi dengan mengisih susunan nombor ringkas secara manual dengan hanya empat langkah mudah.
Isih pantas boleh dipecahkan kepada empat langkah mudah:
- Pilih elemen pangsi daripada tatasusunan. Elemen ini boleh jadi elemen pertama, terakhir, tengah atau malah unsur rawak daripada senarai/tatasusunan.
- Susun semula tatasusunan supaya semua elemen yang kurang daripada pangsi berada di sebelah kiri dan semua elemen yang lebih besar berada di sebelah kanan.
- Tukar elemen pangsi dengan elemen pertama nilai yang lebih besar, supaya pangsi berada di tengah.
- Gunakan operasi yang sama secara rekursif pada sub-tatasusunan di sebelah kiri dan kanan pangsi.
Mari kita gunakan langkah ini pada tatasusunan sebenar. Boleh?
Susun Awal: [3, 6, 2, 7, 1]
Selepas mengisih semua sub-tatasusunan, kami mendapat tatasusunan diisih terakhir:
Susun Isih: [1, 2, 3, 6, 7]
Di bawah ialah ilustrasi terbaik tentang cara ini berfungsi dalam kehidupan sebenar:
Kerumitan masa Isih Pantas berbeza-beza berdasarkan pemilihan pangsi:
Kes Terbaik (O(n log n)):
Kes Purata (O(n log n)):
Kes Terburuk (O(n²)):
Kerumitan ruang Isih Cepat ialah O(log n) disebabkan oleh:
function quickSort(arr) {
// Base case: arrays with length 0 or 1 are already sorted
if (arr.length <= 1) return arr;
// Helper function to swap elements
const swap = (i, j) => {
[arr[i], arr[j]] = [arr[j], arr[i]];
};
// Partition function using Lomuto's partition scheme
function partition(low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(i, j);
}
}
swap(i + 1, high);
return i + 1;
}
// Main quickSort function implementation
function quickSortHelper(low, high) {
if (low < high) {
const pivotIndex = partition(low, high);
quickSortHelper(low, pivotIndex - 1); // Sort left side
quickSortHelper(pivotIndex + 1, high); // Sort right side
}
}
quickSortHelper(0, arr.length - 1);
return arr;
}
Isih Pantas ialah pilihan yang popular kerana kecekapannya dan pengisihan di tempatnya. Ia mengatasi prestasi algoritma yang lebih mudah seperti Isih Buih dan Isih Pemilihan dengan prestasi kes purata O(n log n) dan kerumitan ruang yang rendah.
Pengambilan utama:
Untuk memastikan anda tidak terlepas mana-mana bahagian dalam siri ini dan berhubung dengan saya untuk lebih mendalam
perbincangan tentang Pembangunan Perisian (Web, Pelayan, Mudah Alih atau Mengikis / Automasi), data
struktur dan algoritma, dan topik teknologi menarik lain, ikuti saya di:
Nantikan dan selamat mengekod ???
Atas ialah kandungan terperinci Memecahkan algoritma Isih Pantas: Dari Teori kepada Amalan dalam Minit. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Urutan keutamaan pengendali dalam bahasa c
Bagaimana untuk mematikan pusat keselamatan windows
Bagaimana untuk mewakili nombor negatif dalam binari
Di manakah bilangan penonton dalam talian di stesen b?
bios tidak dapat mengesan pemacu keadaan pepejal
bootmgr tiada dan tidak boleh boot
Bagaimana untuk menukar susun atur cad daripada putih kepada hitam
arahan telnet
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
