Penjelasan terperinci tentang algoritma isihan pantas Javascript_Pengetahuan asas

Isih cepat ialah penambahbaikan pada isihan gelembung. Bahagikan data untuk diisih kepada dua bahagian bebas melalui pengisihan satu laluan Semua data dalam satu bahagian adalah lebih kecil daripada semua data di bahagian lain Kemudian gunakan kaedah ini untuk mengisih kedua-dua bahagian data masing-masing proses pengisihan boleh Teruskan secara rekursif, dan akhirnya keseluruhan data menjadi urutan tertib.

Anggapkan tatasusunan yang hendak diisih ialah A[0]...A[N-1]. Mula-mula, pilih data secara rawak (biasanya nombor pertama tatasusunan) sebagai data penanda aras, dan kemudian semua nombor lebih kecil. daripada itu Letakkannya di hadapannya, dan semua nombor yang lebih besar daripadanya diletakkan di belakangnya. Proses ini dipanggil satu laluan pantas. Perlu diingat bahawa isihan cepat bukanlah algoritma pengisihan yang stabil, iaitu, kedudukan relatif berbilang nilai yang sama mungkin berubah pada akhir algoritma.
Algoritma isihan pantas satu laluan ialah:
1) Tetapkan dua pembolehubah rendah dan tinggi Apabila pengisihan bermula: rendah=0, tinggi=N-1; 2) Gunakan elemen tatasusunan pertama sebagai data rujukan dan tetapkan ia kepada asas, iaitu, base=A[0]
3) Cari ke hadapan dari tinggi, iaitu, cari ke hadapan dari belakang (tinggi--), cari nilai pertama A[tinggi] yang kurang daripada asas, dan tukar A[tinggi] dan A[rendah]; 4) Cari ke belakang dari rendah, iaitu, cari dari depan ke belakang (rendah), cari A[rendah] pertama yang lebih besar daripada asas, dan tukar A[rendah] dan A[tinggi]; 5) Ulang langkah 3 dan 4 sehingga rendah=tinggi;

Salin kod

Kerumitan ruang: O(nlog2n).

Kestabilan: Tidak stabil.