Python编程中归并排序算法的实现步骤详解
基本思想：归并排序是一种典型的分治思想，把一个无序列表一分为二，对每个子序列再一分为二，继续下去，直到无法再进行划分为止。然后，就开始合并的过程，对每个子序列和另外一个子序列的元素进行比较，依次把小元素放入结果序列中进行合并，最终完成归并排序。
归并操作过程：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
上述说法是理论表述，下面用一个实际例子说明：
例如一个无序数组
[6,2,3,1,7]
首先将这个数组通过递归方式进行分解，直到：
[6],[2],[3],[1],[7]
然后开始合并排序，也是用递归的方式进行：
两个两个合并排序，得到：
[2,6],[1,3],[7]
上一步中，其实也是按照本步骤的方式合并的，只不过由于每个list中一个数，不能完全显示过程。下面则可以完全显示过程。
初始：
a = [2,6] b = [1,3] c = []
第1步，顺序从a,b中取出一个数字：2,1 比较大小后放入c中，并将该数字从原list中删除，结果是：
a = [2,6] b = [3] c = [1]
第2步，继续从a,b中按照顺序取出数字，也就是重复上面步骤，这次是：2,3 比较大小后放入c中，并将该数字从原list中删除，结果是：
a = [6] b = [3] c = [1,2]
第3步,再重复前边的步骤,结果是：
a = [6] b = [] c = [1,2,3]
最后一步，将6追加到c中，结果形成了：
a = [] b = [] c = [1,2,3,6]
通过反复应用上面的流程，实现[1,2,3,6]与[7]的合并
最终得到排序结果
[1,2,3,6,7]
本文列举了三种python的实现方法：
方法1：将前面讲述的过程翻译过来了，略先拙笨
#! /usr/bin/env python #coding:utf-8 def merge_sort(seq): if len(seq) ==1: return seq else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) i = 0 #left 计数 j = 0 #right 计数 k = 0 #总计数 while i < len(left) and j < len(right): if left[i] < right [j]: seq[k] = left[i] i +=1 k +=1 else: seq[k] = right[j] j +=1 k +=1 remain = left if i<j else right r = i if remain ==left else j while r<len(remain): seq[k] = remain[r] r +=1 k +=1 return seq
方法2：在按照顺序取数值方面，应用了list.pop()方法，代码更紧凑简洁
#! /usr/bin/env python #coding:utf-8 def merge_sort(lst): #此方法来自维基百科 if len(lst) <= 1: return lst def merge(left, right): merged = [] while left and right: merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) while left: merged.append(left.pop(0)) while right: merged.append(right.pop(0)) return merged middle = int(len(lst) / 2) left = merge_sort(lst[:middle]) right = merge_sort(lst[middle:]) return merge(left, right)
方法3：原来在python的模块heapq中就提供了归并排序的方法，只要将分解后的结果导入该方法即可。
#! /usr/bin/env python #coding:utf-8 from heapq import merge def merge_sort(seq): if len(seq) <= 1: return m else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) return list(merge(left, right)) #heapq.merge() if __name__=="__main__": seq = [1,3,6,2,4] print merge_sort(seq)
Alat AI Hot
Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik
AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.
Undress AI Tool
Gambar buka pakaian secara percuma
Clothoff.io
Penyingkiran pakaian AI
AI Hentai Generator
Menjana ai hentai secara percuma.
Artikel Panas
Alat panas
Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma
SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan
Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa
Dreamweaver CS6
Alat pembangunan web visual
SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)
Topik panas
1377
52
Adakah Mysql perlu membayar
Apr 08, 2025 pm 05:36 PM
MySQL mempunyai versi komuniti percuma dan versi perusahaan berbayar. Versi komuniti boleh digunakan dan diubahsuai secara percuma, tetapi sokongannya terhad dan sesuai untuk aplikasi dengan keperluan kestabilan yang rendah dan keupayaan teknikal yang kuat. Edisi Enterprise menyediakan sokongan komersil yang komprehensif untuk aplikasi yang memerlukan pangkalan data yang stabil, boleh dipercayai, berprestasi tinggi dan bersedia membayar sokongan. Faktor yang dipertimbangkan apabila memilih versi termasuk kritikal aplikasi, belanjawan, dan kemahiran teknikal. Tidak ada pilihan yang sempurna, hanya pilihan yang paling sesuai, dan anda perlu memilih dengan teliti mengikut keadaan tertentu.
Cara Menggunakan MySQL Selepas Pemasangan
Apr 08, 2025 am 11:48 AM
Artikel ini memperkenalkan operasi pangkalan data MySQL. Pertama, anda perlu memasang klien MySQL, seperti MySqlworkbench atau Command Line Client. 1. Gunakan perintah MySQL-Uroot-P untuk menyambung ke pelayan dan log masuk dengan kata laluan akaun root; 2. Gunakan CreateTatabase untuk membuat pangkalan data, dan gunakan Pilih pangkalan data; 3. Gunakan createtable untuk membuat jadual, menentukan medan dan jenis data; 4. Gunakan InsertInto untuk memasukkan data, data pertanyaan, kemas kini data dengan kemas kini, dan padam data dengan padam. Hanya dengan menguasai langkah -langkah ini, belajar menangani masalah biasa dan mengoptimumkan prestasi pangkalan data anda boleh menggunakan MySQL dengan cekap.
Bagaimana untuk mengoptimumkan prestasi MySQL untuk aplikasi beban tinggi?
Apr 08, 2025 pm 06:03 PM
Panduan Pengoptimuman Prestasi Pangkalan Data MySQL Dalam aplikasi yang berintensifkan sumber, pangkalan data MySQL memainkan peranan penting dan bertanggungjawab untuk menguruskan urus niaga besar-besaran. Walau bagaimanapun, apabila skala aplikasi berkembang, kemunculan prestasi pangkalan data sering menjadi kekangan. Artikel ini akan meneroka satu siri strategi pengoptimuman prestasi MySQL yang berkesan untuk memastikan aplikasi anda tetap cekap dan responsif di bawah beban tinggi. Kami akan menggabungkan kes-kes sebenar untuk menerangkan teknologi utama yang mendalam seperti pengindeksan, pengoptimuman pertanyaan, reka bentuk pangkalan data dan caching. 1. Reka bentuk seni bina pangkalan data dan seni bina pangkalan data yang dioptimumkan adalah asas pengoptimuman prestasi MySQL. Berikut adalah beberapa prinsip teras: Memilih jenis data yang betul dan memilih jenis data terkecil yang memenuhi keperluan bukan sahaja dapat menjimatkan ruang penyimpanan, tetapi juga meningkatkan kelajuan pemprosesan data.
Hadidb: Pangkalan data yang ringan dan berskala mendatar di Python
Apr 08, 2025 pm 06:12 PM
Hadidb: Pangkalan data Python yang ringan, tinggi, Hadidb (Hadidb) adalah pangkalan data ringan yang ditulis dalam Python, dengan tahap skalabilitas yang tinggi. Pasang HadIdb menggunakan pemasangan PIP: Pengurusan Pengguna PipInstallHadidB Buat Pengguna: CreateUser () Kaedah untuk membuat pengguna baru. Kaedah pengesahan () mengesahkan identiti pengguna. dariHadidb.OperationImportuserer_Obj = user ("admin", "admin") user_obj.
Adakah mysql memerlukan internet
Apr 08, 2025 pm 02:18 PM
MySQL boleh berjalan tanpa sambungan rangkaian untuk penyimpanan dan pengurusan data asas. Walau bagaimanapun, sambungan rangkaian diperlukan untuk interaksi dengan sistem lain, akses jauh, atau menggunakan ciri -ciri canggih seperti replikasi dan clustering. Di samping itu, langkah -langkah keselamatan (seperti firewall), pengoptimuman prestasi (pilih sambungan rangkaian yang betul), dan sandaran data adalah penting untuk menyambung ke Internet.
Kaedah Navicat untuk melihat kata laluan pangkalan data MongoDB
Apr 08, 2025 pm 09:39 PM
Tidak mustahil untuk melihat kata laluan MongoDB secara langsung melalui Navicat kerana ia disimpan sebagai nilai hash. Cara mendapatkan kata laluan yang hilang: 1. Tetapkan semula kata laluan; 2. Periksa fail konfigurasi (mungkin mengandungi nilai hash); 3. Semak Kod (boleh kata laluan Hardcode).
Bolehkah Mysql Workbench menyambung ke Mariadb
Apr 08, 2025 pm 02:33 PM
MySQL Workbench boleh menyambung ke MariaDB, dengan syarat bahawa konfigurasi adalah betul. Mula -mula pilih "MariaDB" sebagai jenis penyambung. Dalam konfigurasi sambungan, tetapkan host, port, pengguna, kata laluan, dan pangkalan data dengan betul. Apabila menguji sambungan, periksa bahawa perkhidmatan MariaDB dimulakan, sama ada nama pengguna dan kata laluan betul, sama ada nombor port betul, sama ada firewall membenarkan sambungan, dan sama ada pangkalan data itu wujud. Dalam penggunaan lanjutan, gunakan teknologi penyatuan sambungan untuk mengoptimumkan prestasi. Kesilapan biasa termasuk kebenaran yang tidak mencukupi, masalah sambungan rangkaian, dan lain -lain. Apabila kesilapan debugging, dengan teliti menganalisis maklumat ralat dan gunakan alat penyahpepijatan. Mengoptimumkan konfigurasi rangkaian dapat meningkatkan prestasi
Adakah mysql memerlukan pelayan
Apr 08, 2025 pm 02:12 PM
Untuk persekitaran pengeluaran, pelayan biasanya diperlukan untuk menjalankan MySQL, atas alasan termasuk prestasi, kebolehpercayaan, keselamatan, dan skalabilitas. Pelayan biasanya mempunyai perkakasan yang lebih kuat, konfigurasi berlebihan dan langkah keselamatan yang lebih ketat. Untuk aplikasi kecil, rendah, MySQL boleh dijalankan pada mesin tempatan, tetapi penggunaan sumber, risiko keselamatan dan kos penyelenggaraan perlu dipertimbangkan dengan teliti. Untuk kebolehpercayaan dan keselamatan yang lebih besar, MySQL harus digunakan di awan atau pelayan lain. Memilih konfigurasi pelayan yang sesuai memerlukan penilaian berdasarkan beban aplikasi dan jumlah data.
