Bagaimana untuk melaksanakan gabungan jenis algoritma pengisihan python

Penerangan Algoritma

Algoritma pengisihan lanjutan pertama dalam bahagian ini ialah isihan gabungan. Perkataan "penggabungan" bermaksud "untuk bergabung". Seperti namanya, algoritma isihan cantuman ialah algoritma yang mula-mula membahagikan jujukan kepada sub-jujukan, mengisih sub-jujukan, dan kemudian menggabungkan sub-jujukan tersusun ke dalam urutan tertib yang lengkap. Ia sebenarnya mengamalkan idea bahagi dan takluk.

Purata kerumitan masa isihan gabungan ialah O(nlgn), kerumitan masa dalam kes terbaik ialah O(nlgn), dan kerumitan masa dalam kes terburuk juga O(nlgn). Kerumitan ruangnya ialah O(1). Selain itu, pengisihan gabungan ialah algoritma pengisihan yang stabil.

Mengambil isihan menaik sebagai contoh, proses algoritma cantuman ditunjukkan dalam Rajah 2-21.

Tatasusunan asal ialah tatasusunan tidak tertib 8 nombor. Selepas satu operasi, tatasusunan 8 nombor dibahagikan kepada dua tatasusunan tidak tertib 4 nombor. Setiap operasi membahagikan tatasusunan tidak tertib kepada separuh sehingga semua subarray terkecil mengandungi hanya satu elemen. Apabila terdapat hanya satu elemen dalam tatasusunan, tatasusunan mesti dipesan. Kemudian, program ini mula menggabungkan setiap dua tatasusunan tertib kecil ke dalam tatasusunan tertib yang besar. Mula-mula, gabungkan dua tatasusunan yang mengandungi satu nombor ke dalam tatasusunan yang mengandungi dua nombor, kemudian cantumkan dua tatasusunan yang mengandungi dua nombor ke dalam tatasusunan yang mengandungi empat nombor, dan akhirnya cantumkannya ke dalam tatasusunan yang mengandungi lapan nombor. Apabila semua tatasusunan tersusun digabungkan, tatasusunan terpanjang yang terbentuk akan diisih.

Pelaksanaan kod

Gabung kod isihan:

  #归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#递归边界条件
   return num　　　　　　　　　#到达边界时返回当前的子数组
  mid = int(len(num)/2)　　　　　 #求出数组的中位数
  llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
  result = []
  i,j = 0,0
  while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
   if rlist[j]<llist[i]:
     result.append(rlist[j])
     j += 1
   else:
     result.append(llist[i])
     i += 1
  result += llist[i:]+rlist[j:]　 #把数组未添加的部分加到结果数组末尾
  return result　　　　　　　　　#返回已排序的数组
print(MergeSort(nums))

Jalankan program, hasil output ialah:

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

Dalam MergeSort Dalam fungsi (), langkah pertama adalah untuk menilai syarat sempadan. Apabila tatasusunan yang mengandungi hanya satu elemen diluluskan sebagai parameter fungsi, unsur itu sahaja wujud dalam tatasusunan, jadi tatasusunan telah mencapai saiz minimumnya. Sebaik sahaja anda selesai dengan tugas menguraikan tatasusunan secara rekursif, hanya kembalikan tatasusunan terurai ke tahap rekursi sebelumnya.

Jika panjang tatasusunan yang tidak diisih masih lebih besar daripada 1, maka gunakan pembolehubah pertengahan untuk menyimpan subskrip tengah tatasusunan dan bahagikan tatasusunan yang tidak diisih kepada dua subarray di sebelah kiri dan kanan. Kemudian, cipta dua tatasusunan baharu untuk menyimpan subarray kiri dan kanan yang diisih. Idea rekursi digunakan di sini. Kami hanya memikirkan fungsi MergeSort() sebagai fungsi yang mengisih senarai, walaupun di dalam fungsi MergeSort(), fungsi itu sendiri juga boleh dipanggil untuk mengisih dua subarray.

Kemudian, gunakan gelung sementara untuk menggabungkan dua tatasusunan yang telah diisih. Memandangkan saiz relatif elemen dalam dua tatasusunan tidak dapat ditentukan, kami menggunakan dua pembolehubah, i dan j, untuk menandakan kedudukan elemen yang menunggu untuk ditambah dalam sub-tatasusunan kiri dan sub-tatasusunan kanan masing-masing. Apabila gelung while tamat, mungkin terdapat beberapa elemen terbesar yang tinggal di penghujung subarray yang belum ditambahkan pada senarai hasil, jadi pernyataan result+=llist[i:]+rlist[j:] adalah untuk menghalang elemen ini daripada dirindui. Selepas penggabungan tatasusunan selesai, fungsi mengeluarkan tatasusunan tertib.

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