Bagaimana untuk melaksanakan algoritma isihan Hill dalam Python

Penerangan Algoritma

Isih bukit, juga dipanggil "mengurangkan pengisihan tambahan", ialah algoritma pengisihan yang dihasilkan dengan mengoptimumkan isihan sisipan. Idea pelaksanaannya ialah: kumpulkan elemen dalam tatasusunan ke dalam kenaikan subskrip, masukkan dan susun setiap kumpulan elemen, kurangkan kenaikan dan ulangi langkah sebelumnya sehingga kenaikan mencapai 1.

Secara umumnya, kerumitan masa pengisihan Bukit ialah O(n1.3)~O(n2), yang bergantung pada saiz kenaikan. Kerumitan ruang pengisihan Bukit ialah O(1), yang merupakan algoritma pengisihan yang tidak stabil. Semasa melakukan pengisihan Bukit, satu pergerakan elemen mungkin merangkumi berbilang elemen, yang mungkin mengimbangi berbilang pergerakan dan meningkatkan kecekapan.

Berikut ialah isihan Bukit menaik menggunakan (panjang tatasusunan/2) sebagai kenaikan awal Selepas setiap pusingan isihan, kenaikan dikurangkan separuh.

Langkah satu:

Seperti yang ditunjukkan dalam Rajah 2-28, bermula dari elemen pertama, kumpulkan mengikut kenaikan 4. Ia boleh dilihat bahawa apabila kenaikan adalah 4, terdapat hanya dua elemen dalam kumpulan, jika tidak, subskrip elemen akan melebihi julat tatasusunan.

Langkah 2:

Seperti yang ditunjukkan dalam Rajah 2-29, lakukan pengasingan sisipan pada elemen dalam kumpulan.

Langkah 3:

Seperti yang ditunjukkan dalam Rajah 2-30, teruskan menggunakan kaedah yang sama untuk mengumpulkan, dan memasukkan serta mengisih elemen dalam kumpulan supaya mereka Tertib.

Selepas semua nombor dalam keseluruhan tatasusunan telah dilalui, pusingan isihan ini tamat. Kurangkan kenaikan separuh dan teruskan dengan pusingan pengisihan seterusnya.

Langkah 4:

Seperti yang ditunjukkan dalam Rajah 2-31, apabila kenaikan adalah 2, dapat dilihat bahawa elemen dalam setiap kumpulan telah meningkat dan jumlah kumpulan telah berkurangan. Teruskan sisipan menyusun elemen dalam setiap kumpulan sehingga setiap kumpulan dilalui.

Langkah 5:

Pusingan terakhir pengisihan ditunjukkan dalam Rajah 2-32, dan kenaikan dikurangkan separuh lagi pada masa ini kenaikan ialah 1 , yang bersamaan dengan melaksanakan isihan sisipan pada keseluruhan tatasusunan, yang merupakan pusingan terakhir pengisihan.

Selepas pusingan terakhir penyisihan, keseluruhan penyisihan Bukit selesai.

Pelaksanaan kod

Dalam gelung for, memandangkan elemen pertama setiap kumpulan tidak perlu dimasukkan dan diisih, dan subskripnya adalah antara 0 dan langkah-1, ia bermula dari langkah subskrip Traverse.

Perlu diambil perhatian bahawa jika anda ingin mensimulasikan pendekatan dalam carta alir, anda perlu menggunakan dua gelung: kumpulan pertama, dan kemudian susun elemen dalam kumpulan yang sama sekali gus. Untuk meningkatkan kecekapan, kami terus menggunakan gelung for Setiap kali nombor dilalui, kumpulan di mana ia berada disisipkan dan diisih. Traversal ini juga memenuhi keperluan pesanan jenis sisipan. Dalam isihan sisipan, nilai subskrip semasa perlu diubah, jadi ind pembolehubah digunakan untuk menyimpan subskrip semasa untuk mengelakkannya daripada menjejaskan gelung for.

Isih sisipan biasa adalah bersamaan dengan isihan Bukit dengan kenaikan 1. Isih bukit merentas elemen sebenarnya hanya mengubah kenaikan, dan secara logiknya tidak berbeza dengan isihan sisipan biasa.

Kod isihan bukit:

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量为数组长度的一半
  while step > 0:　　　　　　　　　　 #增量必须是大于0的整数
   for i in range(step,len(nums)):　#遍历需要进行插入排序的数
     ind = i
     while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
      nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
      ind -= step
   step //= 2　　　　　　　　　　　#增量缩小一半
  print(nums)
ShellSort(nums)

Jalankan program, hasil output ialah:

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

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma isihan Hill dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!