10 algoritma penyortiran terbaik dijelaskan, dengan contoh

Artikel ini meneroka algoritma penyortiran mendalam, alat asas dalam sains komputer untuk organisasi data yang cekap dan memberikan pandangan praktikal melalui kod sampel pelbagai jenis algoritma. Artikel ini mengandungi analisis teknikal algoritma penyortiran, menggunakan notasi O yang besar untuk menganalisis kerumitan masa dan ruangnya, dan juga memberikan gambaran keseluruhan peringkat tinggi untuk difahami oleh orang ramai. Artikel ini secara komprehensif meneroka algoritma penyortiran, membincangkan kepentingannya, pelbagai jenis dan algoritma utama yang perlu difahami, memberi tumpuan kepada aplikasi praktikal dan perbandingan algoritma.

mata utama

Asas dan Praktikal:

Artikel ini meneroka algoritma penyortiran mendalam, alat yang mesti dimiliki dalam sains komputer untuk organisasi data yang cekap dan memberikan pandangan praktikal melalui kod sampel pelbagai jenis algoritma.
1. Analisis Teknikal dan Kebolehcapaian Teknikal: Ia termasuk pemeriksaan teknikal algoritma penyortiran, menganalisis kerumitan masa dan ruang menggunakan notasi besar O, dan juga menyediakan gambaran keseluruhan peringkat tinggi untuk pemahaman yang mudah. Liputan Komprehensif:
Artikel ini secara komprehensif meneroka algoritma penyortiran, membincangkan kepentingannya, jenis yang berbeza dan algoritma utama yang perlu difahami, memberi tumpuan kepada aplikasi praktikal dan perbandingan algoritma.
Apakah algoritma penyortiran?
3. Pada dasarnya, algoritma penyortiran adalah program komputer yang menganjurkan data ke dalam pesanan tertentu, seperti susunan abjad atau berangka, biasanya dalam urutan menaik atau menurun.

Apakah tujuan algoritma penyortiran?

Algoritma menyusun terutamanya digunakan untuk menyusun semula sejumlah besar data dengan cara yang cekap untuk memudahkan untuk mencari dan memanipulasi mereka. Mereka juga digunakan untuk meningkatkan kecekapan algoritma lain seperti carian dan penggabungan yang bergantung kepada data yang disusun untuk beroperasi.

Mengapa algoritma penyortiran begitu penting?

Algoritma penyortiran digunakan untuk menganjurkan data dalam urutan tertentu, yang menjadikannya lebih mudah untuk mencari, mengakses, dan menganalisis data. Dalam banyak aplikasi, penyortiran adalah bahagian utama aliran pemprosesan data, dan kecekapan algoritma penyortiran boleh memberi kesan yang signifikan terhadap prestasi keseluruhan sistem.

Dalam pangkalan data: jenis digunakan untuk mendapatkan rekod dalam urutan tertentu, seperti tarikh, abjad atau urutan berangka. Ini membolehkan pengguna dengan cepat mencari data yang mereka perlukan tanpa mencari secara manual sejumlah besar data yang tidak disusun.

Dalam enjin carian:

Susun hasil carian dalam urutan relevan. Dengan menyusun hasilnya dengan cara ini, pengguna dapat dengan cepat mencari maklumat yang mereka cari tanpa menapis hasil yang tidak relevan atau tidak relevan.
• Dalam banyak aplikasi saintifik dan kejuruteraan:
Penyelidik boleh menjalankan analisis data dan simulasi untuk mendapatkan wawasan tentang sistem yang kompleks dan membuat ramalan yang lebih tepat mengenai tingkah laku masa depan.
pelbagai jenis jenis dalam struktur data
• pelbagai jenis boleh didapati. Pilihan algoritma penyortiran bergantung kepada pelbagai faktor, seperti saiz set data, jenis data yang disusun, dan kerumitan masa dan ruang yang diperlukan.

Algoritma penyortiran berasaskan perbandingan

Algoritma ini membandingkan unsur -unsur dataset dan menentukan pesanan mereka berdasarkan hasil perbandingan. Contoh algoritma penyortiran berasaskan perbandingan termasuk jenis gelembung, memasukkan jenis, jenis cepat, jenis gabungan, dan jenis timbunan.

Algoritma penyortiran berasaskan bukan perbandingan

Algoritma ini tidak membandingkan unsur -unsur secara langsung, tetapi gunakan sifat -sifat lain dari dataset untuk menentukan pesanan mereka. Contoh-contoh algoritma penyortiran berasaskan bukan perbandingan termasuk penyortiran kiraan, penyortiran kardinaliti, dan penyortiran baldi.

Algoritma penyortiran di tempat

algoritma ini menyusun dataset dalam situ, yang bermaksud mereka tidak memerlukan memori tambahan untuk menyimpan hasil pertengahan. Contoh algoritma penyortiran dalam situ termasuk penyortiran gelembung, memasukkan penyortiran, penyortiran cepat, dan penyortiran bukit.

algoritma penyortiran stabil

Algoritma ini mengekalkan urutan relatif elemen seperti dataset. Contoh algoritma penyortiran yang stabil termasuk memasukkan jenis, gabungan, dan timsort.

Algoritma Penyortiran Adaptif

Algoritma ini menggunakan sebarang pesanan sedia ada dalam dataset untuk meningkatkan kecekapan mereka. Contoh algoritma penyortiran penyesuaian termasuk memasukkan penyisihan, penyortiran gelembung, dan timsort.

Algoritma Penyortiran Sepuluh Top yang perlu diketahui

Sekarang mari kita lihat pada sepuluh algoritma penyortiran teratas yang perlu anda perhatikan ketika memilih algoritma penyortiran.

Bubblestone

Bubblestone adalah algoritma penyortiran yang mudah yang melelehkan senarai item yang diberikan, membandingkan setiap sepasang item bersebelahan, dan menukarnya jika mereka tidak betul. Algoritma berterusan sehingga ia melintasi keseluruhan senarai tanpa bertukar -tukar apa -apa item. Penyortiran gelembung kadang -kadang dipanggil "penyortiran tenggelam".



Sejarah Bubble Sort
Asal -usul Bubble Sort bermula pada akhir 1950 -an, dan Donald Knut mempopularkannya dalam klasiknya pada tahun 1968 The Art of Computer Programming. Sejak itu, ia telah digunakan secara meluas dalam pelbagai aplikasi, termasuk algoritma penyortiran penyusun, penyortiran unsur -unsur dalam pangkalan data, dan juga menyusun kad bermain.
kebaikan dan kekurangan penyortiran gelembung
Bubblestone dianggap sebagai algoritma penyortiran yang agak tidak cekap kerana kerumitan purata dan terburuknya adalah O (n^2). Ini menjadikannya kurang cekap daripada kebanyakan algoritma penyortiran lain, seperti jenis cepat atau gabungan.

Penerangan Teknikal: O (N^2) Kompleks bermakna bahawa masa yang diperlukan untuk algoritma diselesaikan adalah berkadar dengan kuadrat saiz input. Ini bermakna saiz input yang lebih besar akan menyebabkan algoritma selesai lebih lama. Sebagai contoh, jika anda menganggap algoritma yang menyusun pelbagai nombor, ia mungkin mengambil satu saat untuk menyusun pelbagai nombor sepuluh, tetapi mungkin mengambil masa empat saat untuk menyusun pelbagai 20 nombor. Ini kerana algoritma perlu membandingkan setiap elemen dalam array dengan setiap elemen lain, jadi ia harus membandingkan array yang lebih besar 20 kali dan array yang lebih kecil hanya 10 kali.

Walau bagaimanapun, sangat mudah difahami dan dilaksanakan dan sering digunakan sebagai pengenalan kepada penyortiran dan blok bangunan untuk algoritma yang lebih kompleks. Tetapi sekarang ia jarang digunakan dalam amalan.
kes pengguna untuk menyusun gelembung
Bubblestone adalah algoritma mudah yang boleh digunakan untuk menyusun senarai atau tatasusunan elemen kecil. Ia mudah dilaksanakan dan difahami, jadi ia boleh digunakan dalam situasi di mana kesederhanaan dan kejelasan lebih penting daripada prestasi.
tujuan pendidikan. Ia sering digunakan sebagai contoh algoritma penyortiran mudah dalam kursus sains komputer. Pelajar boleh mempelajari teknik penyortiran asas dan memahami bagaimana algoritma berfungsi dengan belajar menyusun gelembung.
Susun dataset kecil. Ia boleh digunakan untuk menyusun dataset kecil dengan sehingga beberapa ratus elemen. Dalam situasi di mana prestasi bukan isu kritikal, penyortiran yang menggelegak boleh menjadi cara yang cepat dan mudah untuk menyusun senarai kecil.
Data pra-disusun. Ia boleh digunakan sebagai langkah awal dalam algoritma penyortiran yang lebih kompleks. Sebagai contoh, jika data telah disusun sebahagiannya, data boleh disusun lagi menggunakan jenis gelembung sebelum menjalankan algoritma yang lebih kompleks.
Susun data dengan sumber yang terhad. Ia berguna dalam situasi di mana sumber terhad, seperti dalam sistem tertanam atau mikrokontroler, kerana ia memerlukan sedikit memori dan kuasa pemprosesan.
Blok bangunan untuk algoritma yang lebih kompleks. Ia sering digunakan dengan penyortiran gabungan atau penyortiran cepat, serta menyusun subarrays kecil menggunakan penyortiran sisipan, kerana algoritma lain ini dapat mencapai prestasi yang lebih baik pada dataset yang lebih besar.
pelaksanaan penyortiran gelembung

Melangkah melalui projek menggunakan gelung bersarang.
Bandingkan item bersebelahan dalam senarai.
Jika pesanan projek salah, bertukar projek.
Teruskan sehingga senarai disusun.

Sort Bubbling dalam Python

def bubble_sort(items):
    for i in range(len(items)):
        for j in range(len(items)-1-i):
            if items[j] > items[j+1]:
                items[j], items[j+1] = items[j+1], items[j]
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(bubble_sort(items))

Penyortiran Bubbling dalam JavaScript

function bubbleSort(items) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < items.length - 1; i++) {
      if (items[i] > items[i + 1]) {
        let temp = items[i];
        items[i] = items[i + 1];
        items[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(bubbleSort(items));

(disebabkan oleh batasan ruang, hanya nama algoritma dan penerangan ringkas akan dikekalkan. Sila rujuk teks asal untuk kod lengkap dan penjelasan terperinci)

Masukkan Sort

Masukkan jenis adalah algoritma mudah yang membina array yang disusun akhir pada satu masa, dan dinamakan begitu kerana bagaimana unsur -unsur yang lebih kecil dimasukkan ke dalam kedudukan yang betul dalam array yang disusun.

Cepat jenis

Cepat adalah algoritma penyortiran yang popular dan konquer berdasarkan prinsip membahagikan array menjadi dua subarray-satu yang mengandungi elemen yang lebih kecil daripada elemen "pivot" dan yang lain yang mengandungi elemen yang lebih besar daripada elemen pivot. Kemudian rekursif menyusun dua subarray.

Bucket Sort

Penyortiran baldi adalah algoritma yang berguna untuk menyusun data yang diedarkan secara sama rata, yang dapat dengan mudah dipasangkan untuk prestasi yang lebih baik.

Hill Sort

Sort Hill menggunakan algoritma penyisihan memasukkan, tetapi bukannya menyusun keseluruhan senarai sekaligus, ia membahagikan senarai ke dalam sublists yang lebih kecil. Sublists ini kemudian disusun menggunakan algoritma sisipan sisipan, dengan itu mengurangkan bilangan swap yang diperlukan untuk menyusun senarai.

gabungan jenis

Idea asas jenis gabungan adalah untuk membahagikan senarai input ke dalam dua bahagian, menyusun setiap bilangan rekursif menggunakan jenis gabungan, dan kemudian menggabungkan dua bahagian yang disusun bersama -sama.

Pilih Sort

Pilih Sort berulang kali pilih elemen terkecil dari bahagian yang tidak disusun dari senarai dan swapnya dengan elemen pertama bahagian yang tidak disusun. Proses ini berterusan sehingga keseluruhan senarai disusun.

jenis hitam

Idea asas penyortiran kardinaliti adalah untuk menyusun data dengan mengumpulkan setiap nombor nombor atau watak, dari kanan ke kiri atau dari kiri ke kanan.

sikat sort

Susun sikat membandingkan pasangan unsur -unsur yang jarak tertentu, dan jika mereka tidak betul, swapnya.

timsort

Algoritma Timsort berfungsi dengan membahagikan data input ke dalam subarray yang lebih kecil dan kemudian menyusun subarray ini menggunakan jenis sisipan.

(kod pelaksanaan TIMSORT ditinggalkan kerana alasan panjang)

Perbandingan semua algoritma penyortiran

Sila ambil perhatian bahawa kerumitan masa dan kerumitan spatial yang disenaraikan dalam jadual adalah

kerumitan kes terburuk, dan prestasi sebenar mungkin berbeza -beza bergantung kepada pelaksanaan tertentu dan data input.

算法	时间复杂度	空间复杂度	原地排序	稳定排序	自适应排序
冒泡排序	O(n^2)	O(1)	是	是	否
快速排序	O(n log n)	O(log n)	是	否	是
桶排序	O(n k)	O(n k)	否	是	否
希尔排序	O(n log n)	O(1)	是	否	否
合并排序	O(n log n)	O(n)	否	是	否
选择排序	O(n^2)	O(1)	是	否	否
基数排序	O(w·n)	O(w n)	否	是	否
梳排序	O(n^2)	O(1)	是	否	是
Timsort	O(n log n)	O(n)	是	是	是

Apakah algoritma penyortiran yang paling biasa digunakan?

Algoritma penyortiran yang paling biasa digunakan mungkin menyusun cepat. Ia digunakan secara meluas dalam banyak bahasa pengaturcaraan (termasuk C, C, Java, dan Python), serta dalam banyak aplikasi dan perpustakaan perisian. Penyortiran cepat disukai untuk kecekapan dan fleksibiliti dalam mengendalikan pelbagai jenis data dan sering digunakan sebagai algoritma penyortiran lalai dalam bahasa pengaturcaraan dan kerangka perisian. Walau bagaimanapun, algoritma penyortiran lain seperti jenis gabungan dan timsort juga digunakan secara meluas dalam pelbagai aplikasi kerana kecekapan dan keupayaan uniknya.

(kandungan yang tinggal, seperti ringkasan, FAQ, dan lain -lain, telah ditinggalkan kerana batasan ruang.)

Atas ialah kandungan terperinci 10 algoritma penyortiran terbaik dijelaskan, dengan contoh. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!