1.首先介紹下python的對(duì)象引用
創(chuàng)新互聯(lián)公司是專業(yè)的上街網(wǎng)站建設(shè)公司，上街接單;提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行上街網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!
1）Python中不存在傳值調(diào)用，一切傳遞的都是對(duì)象引用，也可以認(rèn)為是傳址調(diào)用。即Python不允許程序員選擇采用傳值或傳引用。Python參數(shù)傳遞采用的是“傳對(duì)象引用”的方式。實(shí)際上，這種方式相當(dāng)于傳值和傳引用的一種綜合。如果函數(shù)參數(shù)收到的是一個(gè)可變對(duì)象（比如字典或者列表）的引用，就能修改對(duì)象的原始值——相當(dāng)于通過(guò)“傳引用”來(lái)傳遞對(duì)象。如果函數(shù)收到的是一個(gè)不可變對(duì)象（比如數(shù)字、字符或者元組）的引用，就不能直接修改原始對(duì)象——相當(dāng)于通過(guò)"傳值"來(lái)傳遞對(duì)象。
2）當(dāng)復(fù)制列表或字典時(shí)，就復(fù)制了對(duì)象列表的引用，如果改變引用的值，則修改了原始的參數(shù)。
3）為了簡(jiǎn)化內(nèi)存管理，Python通過(guò)引用計(jì)數(shù)機(jī)制實(shí)現(xiàn)自動(dòng)垃圾回收功能，Python中的每個(gè)對(duì)象都有一個(gè)引用計(jì)數(shù)，用來(lái)計(jì)數(shù)該對(duì)象在不同場(chǎng)所分別被引用了多少次。每當(dāng)引用一次Python對(duì)象，相應(yīng)的引用計(jì)數(shù)就增1，每當(dāng)消毀一次Python對(duì)象，則相應(yīng)的引用就減1，只有當(dāng)引用計(jì)數(shù)為零時(shí)，才真正從內(nèi)存中刪除Python對(duì)象。
2. 可變對(duì)象與不可變對(duì)象的概念與分類
Python在heap中分配的對(duì)象分成2類：
不可變對(duì)象（immutable object）：Number（int、float、bool、complex）、String、Tuple. 采用等效于“傳引用”的方式。
可變對(duì)象（mutable object）：List、dictionary.采用等效于“傳值”的方式。
3. del 是刪除引用而不是刪除對(duì)象，對(duì)象由自動(dòng)垃圾回收機(jī)制（GC）刪除
看這個(gè)例子：
x = 1
del x x
Traceback (most recent call last):
File "pyshell#28", line 1, in module
x
NameError: name 'x' is not defined x = ['Hello','world'] y = x y
['Hello', 'world'] x
['Hello', 'world'] del x x
Traceback (most recent call last):
File "pyshell#32", line 1, in modulex
NameError: name 'x' is not defined y
['Hello', 'world']
可以看到x和y指向同一個(gè)列表，但是刪除x后，y并沒(méi)有受到影響。這是為什么呢？
The reason for this is that you only delete the name,not the list itself,In fact ,there is no way to delete values in python(and you don’t really need to because the python interpreter does it by itself whenever you don’t use the value anymore)
舉個(gè)例子，一個(gè)數(shù)據(jù)（比如例子中的列表），就是一個(gè)盒子，我們把它賦給一個(gè)變量x，就是好像把一個(gè)標(biāo)簽x貼到了盒子上，然后又貼上了y，用它們來(lái)代表這個(gè)數(shù)據(jù)，但是用del刪除這個(gè)變量x就像是把標(biāo)有x的標(biāo)簽給撕了，剩下了y的標(biāo)簽。
再看一個(gè)例子：
shoplist = ['apple', 'mango', 'carrot', 'banana']print ('The first item I will buy is', shoplist[0])
olditem = shoplist[0]del shoplist[0] ?#del的是引用，而不是對(duì)象print ('I bought the',olditem)print ('My shopping list is now', shoplist)print(shoplist[0])
結(jié)果為：
The first item I will buy is apple
I bought the apple
My shopping list is now ['mango', 'carrot', 'banana']
mango
實(shí)例補(bǔ)充：
#!/usr/bin/evn python# -*- coding:utf-8 -*-# Author: antcolonies'''python中的內(nèi)置方法del不同于C語(yǔ)言中的free和C++中的delete
（free和delete直接回收內(nèi)存，當(dāng)然存儲(chǔ)于該內(nèi)存的對(duì)象也就掛了）
Python都是引用，垃圾回收為GC機(jī)制'''
'''if __name__ == '__main__':
a = 1 ? ? ? ? ?# 對(duì)象 1 被 變量a引用，對(duì)象1的引用計(jì)數(shù)器為1
b = a ? ? ? ? ?# 對(duì)象1 被變量b引用，對(duì)象1的引用計(jì)數(shù)器加1
c = a ? ? ? ? ?# 對(duì)象1 被變量c引用，對(duì)象1的引用計(jì)數(shù)器加1
del a ? ? ? ? ?# 刪除變量a，解除a對(duì)1的引用，對(duì)象1的引用計(jì)數(shù)器減1
del b ? ? ? ? ?# 刪除變量b，解除b對(duì)1的引用，對(duì)象1的引用計(jì)數(shù)器減1
print(c) ? ? ? # 1'''
if __name__=='__main__':
li=['one','two','three','four','five'] ?# 列表本身不包含數(shù)據(jù)'one','two','three','four','five'，而是包含變量：li[0] li[1] li[2] li[3] li[4]
first=li[0] ? ? ? # 拷貝列表，也不會(huì)有數(shù)據(jù)對(duì)象的復(fù)制，而是創(chuàng)建新的變量引用
del li[0] ? ?print(li) ? ? ? ? # ['two','three','four','five']
print(first) ? ? ?# one
list1 = li ? ?del li ? ?print(list1) ? ? ?# ['two', 'three', 'four', 'five']# ? print(type(li)) ? # NameError: name 'li' is not defined
在一個(gè) 最小堆 (min heap) 中，如果 P 是 C 的一個(gè)父級(jí)節(jié)點(diǎn)，那么 P 的 key（或 value) 應(yīng)小于或等于 C 的對(duì)應(yīng)值。 正因?yàn)榇耍秧斣匾欢ㄊ亲钚〉?，我們?huì)利用這個(gè)特點(diǎn)求最小值或者第 k 小的值。
在一個(gè) 最大堆 (max heap) 中，P 的 key（或 value) 大于或等于 C 的對(duì)應(yīng)值。
以python為例，說(shuō)明堆的幾個(gè)常見(jiàn)操作，這里需要用到一個(gè)內(nèi)置的包：heapq
python中使用堆是通過(guò)傳入一個(gè)數(shù)組，然后調(diào)用一個(gè)函數(shù)，在原地讓傳入的數(shù)據(jù)具備堆的特性
需要注意的是，heapify默認(rèn)構(gòu)造的是小頂堆（min heap），如果要構(gòu)造大頂堆，思路是把所有的數(shù)值倒轉(zhuǎn)，既* -1，例如：
使用heapq提供的函數(shù)： heappop 來(lái)實(shí)現(xiàn)
具體使用方式參考 初始化Heapify
使用heapq提供的函數(shù)： heappush 來(lái)實(shí)現(xiàn)
同時(shí)heapq還提供另外一個(gè)函數(shù)： heappushpop ，能夠在一個(gè)函數(shù)實(shí)現(xiàn)pushpop兩個(gè)操作；順序是：先push再pop
根據(jù)官方文檔的描述，這個(gè)函數(shù)會(huì)比先在外圍先調(diào)用heappush，再調(diào)用heappop，效率更高
先pop數(shù)據(jù)再push數(shù)據(jù)，和heappushpop的順序是反著的； 同樣的，這樣調(diào)用的性能也會(huì)比先調(diào)用heappop再調(diào)用heappush更好
如果pop的時(shí)候隊(duì)列是空的，會(huì)拋出一個(gè)異常
可以通過(guò) heapq.merge 將多個(gè) 已排序 的輸入合并為一個(gè)已排序的輸出，這個(gè)本質(zhì)上不是堆；其實(shí)就是用兩個(gè)指針迭代
對(duì)于這個(gè)問(wèn)題，有一個(gè)算法題可以實(shí)現(xiàn)相同的功能
從 iterable 所定義的數(shù)據(jù)集中返回前 n 個(gè)最大/小元素組成的列表。
函數(shù)為： heapq.nlargest() | heapq.nsmallest()
heapq - Heap queue algorithm - Python 3.10.4 documentation
class SortMethod:
'''
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。
插入算法把要排序的數(shù)組分成兩部分：
第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置）
第二部分就只包含這一個(gè)元素（即待插入元素）。
在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。
'''
def insert_sort(lists):
# 插入排序
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j = 0:
if lists[j] key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
'''
希爾排序 (Shell Sort) 是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 DL．Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至 1 時(shí)，整個(gè)文件恰被分成一組，算法便終止。
'''
def shell_sort(lists):
# 希爾排序
count = len(lists)
step = 2
group = count / step
while group 0:
for i in range(0, group):
j = i + group
while j count:
k = j - group
key = lists[j]
while k = 0:
if lists[k] key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return lists
'''
冒泡排序重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。
'''
def bubble_sort(lists):
# 冒泡排序
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] lists[j]:
temp = lists[j]
lists[j] = lists[i]
lists[i] = temp
return lists
'''
快速排序
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
'''
def quick_sort(lists, left, right):
# 快速排序
if left = right:
return lists
key = lists[left]
low = left
high = right
while left right:
while left right and lists[right] = key:
right -= 1
lists[left] = lists[right]
while left right and lists[left] = key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
'''
直接選擇排序
第 1 趟，在待排序記錄 r[1] ~ r[n] 中選出最小的記錄，將它與 r[1] 交換；
第 2 趟，在待排序記錄 r[2] ~ r[n] 中選出最小的記錄，將它與 r[2] 交換；
以此類推，第 i 趟在待排序記錄 r[i] ~ r[n] 中選出最小的記錄，將它與 r[i] 交換，使有序序列不斷增長(zhǎng)直到全部排序完畢。
'''
def select_sort(lists):
# 選擇排序
count = len(lists)
for i in range(0, count):
min = i
for j in range(i + 1, count):
if lists[min] lists[j]:
min = j
temp = lists[min]
lists[min] = lists[i]
lists[i] = temp
return lists
'''
堆排序 (Heapsort) 是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。
可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹(shù)。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即 A[PARENT[i]] = A[i]。
在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。
'''
# 調(diào)整堆
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i size / 2:
if lchild size and lists[lchild] lists[max]:
max = lchild
if rchild size and lists[rchild] lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
# 創(chuàng)建堆
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
# 堆排序
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
'''
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法 （Divide and Conquer） 的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
歸并過(guò)程為：
比較 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，則將第一個(gè)有序表中的元素 a[i] 復(fù)制到 r[k] 中，并令 i 和 k 分別加上 1；
否則將第二個(gè)有序表中的元素 a[j] 復(fù)制到 r[k] 中，并令 j 和 k 分別加上 1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到 r 中從下標(biāo) k 到下標(biāo) t 的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間 [s,t] 以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間 [s,t]。
'''
def merge(left, right):
i, j = 0, 0
result = []
while i len(left) and j len(right):
if left[i] = right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
# 歸并排序
if len(lists) = 1:
return lists
num = len(lists) / 2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)
'''
基數(shù)排序 （radix sort） 屬于“分配式排序” （distribution sort），又稱“桶子法” （bucket sort） 或 bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序。
其時(shí)間復(fù)雜度為 O (nlog(r)m)，其中 r 為所采取的基數(shù)，而 m 為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
'''
import math
def radix_sort(lists, radix=10):
k = int(math.ceil(math.log(max(lists), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, k+1):
for j in lists:
bucket[j/(radix**(i-1)) % (radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists
---------------------
作者：CRazyDOgen
來(lái)源：CSDN
原文：
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！
重慶分公司
重慶分公司
