Rumah > Artikel > pembangunan bahagian belakang > Algoritma Isih Pemilihan
Algoritma Isih Pemilihan membahagikan tatasusunan kepada dua bahagian: bahagian yang diisih dan bahagian yang tidak diisih. Pada mulanya, bahagian yang diisih kosong, dan bahagian yang tidak diisih mengandungi semua elemen. Algoritma berfungsi dengan mencari elemen terkecil (atau terbesar, bergantung pada susunan pengisihan) daripada bahagian yang tidak diisih dan menukarnya dengan elemen pertama bahagian yang tidak diisih. Proses ini berterusan sehingga keseluruhan tatasusunan diisih.
#Suppose we have the following array: arr = [64, 25, 12, 22, 11]
Susunan selepas hantaran pertama: [11, 25, 12, 22, 64]
Susun atur selepas hantaran kedua: [11, 12, 25, 22, 64]
Susun atur selepas hantaran ketiga: [11, 12, 22, 25, 64]
Tatasusunan diisih akhir: [11, 12, 22, 25, 64]
def selection_sort(arr): # Traverse through all array elements for i in range(len(arr)): # Find the minimum element in the remaining unsorted part min_index = i for j in range(i+1, len(arr)): if arr[j] < arr[min_index]: min_index = j # Swap the found minimum element with the first element of the unsorted part arr[i], arr[min_index] = arr[min_index], arr[i] # Example usage arr = [64, 25, 12, 22, 11] selection_sort(arr) print("Sorted array:", arr)
Tatasusunan diisih: [11, 12, 22, 25, 64]
Kes Terbaik: O(n²)
Kes Purata: O(n²)
Kes Terburuk: O(n²)
Walaupun Isih Pemilihan berprestasi baik untuk set data kecil, ia tidak sesuai untuk tatasusunan yang lebih besar kerana kerumitan masanya ialah O(n²). Walau bagaimanapun, ia mudah untuk dilaksanakan dan boleh berguna dalam kes di mana ingatan menjadi kebimbangan, kerana Isih Pemilihan ada di tempatnya (tidak memerlukan memori tambahan).
Kelebihan:
Mudah untuk difahami dan dilaksanakan.
Berprestasi baik pada senarai kecil.
Tidak memerlukan memori tambahan kerana ia menyusun tatasusunan di tempatnya.
Kelemahan:
Tidak cekap untuk set data yang besar kerana O(n²) kerumitan masanya.
Ia bukan algoritma pengisihan yang stabil, bermakna elemen yang sama mungkin tidak mengekalkan susunannya berbanding satu sama lain.
Atas ialah kandungan terperinci Algoritma Isih Pemilihan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!