Bagaimana untuk melaksanakan pengisihan pemilihan algoritma pengisihan python

1. Pengenalan

Algoritma pengisihan utama merujuk kepada beberapa algoritma pengisihan asas dan mudah difahami. Terdapat tiga algoritma pengisihan utama: isihan sisipan, isihan pemilihan dan isihan gelembung. Walaupun kecekapannya lebih rendah daripada algoritma pengisihan lanjutan, selepas memahami algoritma pengisihan utama, lebih mudah untuk mempelajari algoritma pengisihan lanjutan yang agak kompleks.

2. Penerangan

Isih pilihan bermaksud memilih data terkecil atau terbesar daripada tatasusunan tidak tertib setiap kali, dan meletakkannya daripada tatasusunan tidak tersusun ke penghujung tatasusunan untuk mencapai kesan isihan.

Purata kerumitan masa isihan pemilihan ialah O(n2), dan kerumitan masa dalam kes terbaik dan kerumitan masa dalam kes terburuk ialah O(n2). Selain itu, ia adalah algoritma pengisihan yang tidak stabil. Proses isihan pemilihan mudah difahami. Mengambil algoritma pengisihan menaik sebagai contoh, kita mula-mula melintasi tatasusunan yang tidak diisih dan mencari elemen terkecil, seperti yang ditunjukkan dalam Rajah 2-4. Kemudian, keluarkan elemen terkecil daripada tatasusunan yang tidak diisih dan tambahkannya pada penghujung tatasusunan yang diisih.

Oleh kerana elemen terkecil ialah 1, 1 ditambah pada penghujung tatasusunan tertib yang masih kosong.

Seperti yang ditunjukkan dalam Rajah 2-5, kami terus melintasi elemen yang tinggal. Kali ini, elemen terkecil ialah 2. Kami menambahnya pada penghujung tatasusunan yang diisih. Operasi ini betul kerana elemen dalam tatasusunan yang diisih mestilah lebih kecil daripada elemen dalam tatasusunan yang tidak diisih.

Seperti yang ditunjukkan dalam Rajah 2-6, ulangi langkah di atas Apabila hanya tinggal satu elemen dalam tatasusunan yang tidak diisih, tambahkannya pada penghujung tatasusunan yang diisih. Keseluruhan Pengisihan tatasusunan selesai.

3 Pelaksanaan kod

Pilih kod pengisihan:

nums = [5,3,6,4,1,2,8,7]
res = []　　　#用于存储已排序元素的数组
while len(nums): #当未排序数组内还有元素时，重复执行选择最小数的代码
 minInd = 0 #初始化存储最小数下标的变量，默认为第一个数
 for i in range(1, len(nums)):
  if(nums[i] < nums[minInd]): #更新最小数的下标
    minInd = i
 temp = nums[minInd]
 nums.pop(minInd) #把最小数从未排序数组中删除
 res.append(temp) #把最小数插入到已排序数组的末尾
print(res)

Jalankan atur cara, hasil keluarannya ialah:

[1,2,3,4,5,6,7,8]

Dalam atur cara, i dalam gelung pertama untuk mewakili kedudukan pertama dalam tatasusunan yang tidak diisih, iaitu kedudukan pertama selepas tatasusunan tersusun. Kemudian, gunakan gelung for untuk mencari subskrip nilai minimum dalam tatasusunan yang tidak diisih. Pada mulanya, indeks minimum minInd diberikan indeks bagi elemen pertama tatasusunan yang tidak diisih. Apabila elemen yang lebih kecil daripada minimum semasa ditemui, cuma kemas kini indeks dan ulangi keseluruhan tatasusunan. Selepas menukar nilai minimum yang ditemui dengan elemen pertama dalam tatasusunan yang tidak diisih, nilai minimum diletakkan pada penghujung tatasusunan yang dipesan.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pengisihan pemilihan algoritma pengisihan python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!