13518219792
1.首先介紹下python的對象引用
創(chuàng)新互聯(lián)公司是專業(yè)的上街網站建設公司，上街接單;提供成都網站設計、做網站,網頁設計,網站設計,建網站,PHP網站建設等專業(yè)做網站服務;采用PHP框架,可快速的進行上街網站開發(fā)網頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網站,專業(yè)的做網站團隊,希望更多企業(yè)前來合作!
1）Python中不存在傳值調用，一切傳遞的都是對象引用，也可以認為是傳址調用。即Python不允許程序員選擇采用傳值或傳引用。Python參數(shù)傳遞采用的是“傳對象引用”的方式。實際上，這種方式相當于傳值和傳引用的一種綜合。如果函數(shù)參數(shù)收到的是一個可變對象（比如字典或者列表）的引用，就能修改對象的原始值——相當于通過“傳引用”來傳遞對象。如果函數(shù)收到的是一個不可變對象（比如數(shù)字、字符或者元組）的引用，就不能直接修改原始對象——相當于通過"傳值"來傳遞對象。
2）當復制列表或字典時，就復制了對象列表的引用，如果改變引用的值，則修改了原始的參數(shù)。
3）為了簡化內存管理，Python通過引用計數(shù)機制實現(xiàn)自動垃圾回收功能，Python中的每個對象都有一個引用計數(shù)，用來計數(shù)該對象在不同場所分別被引用了多少次。每當引用一次Python對象，相應的引用計數(shù)就增1，每當消毀一次Python對象，則相應的引用就減1，只有當引用計數(shù)為零時，才真正從內存中刪除Python對象。
2. 可變對象與不可變對象的概念與分類
Python在heap中分配的對象分成2類：
不可變對象（immutable object）：Number（int、float、bool、complex）、String、Tuple. 采用等效于“傳引用”的方式。
可變對象（mutable object）：List、dictionary.采用等效于“傳值”的方式。
3. del 是刪除引用而不是刪除對象，對象由自動垃圾回收機制（GC）刪除
看這個例子：
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指向同一個列表，但是刪除x后，y并沒有受到影響。這是為什么呢？
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)
舉個例子，一個數(shù)據(jù)（比如例子中的列表），就是一個盒子，我們把它賦給一個變量x，就是好像把一個標簽x貼到了盒子上，然后又貼上了y，用它們來代表這個數(shù)據(jù)，但是用del刪除這個變量x就像是把標有x的標簽給撕了，剩下了y的標簽。
再看一個例子：
shoplist = ['apple', 'mango', 'carrot', 'banana']print ('The first item I will buy is', shoplist[0])
olditem = shoplist[0]del shoplist[0] ?#del的是引用，而不是對象print ('I bought the',olditem)print ('My shopping list is now', shoplist)print(shoplist[0])
結果為：
The first item I will buy is apple
I bought the apple
My shopping list is now ['mango', 'carrot', 'banana']
mango
實例補充：
#!/usr/bin/evn python# -*- coding:utf-8 -*-# Author: antcolonies'''python中的內置方法del不同于C語言中的free和C++中的delete
（free和delete直接回收內存，當然存儲于該內存的對象也就掛了）
Python都是引用，垃圾回收為GC機制'''
'''if __name__ == '__main__':
a = 1 ? ? ? ? ?# 對象 1 被 變量a引用，對象1的引用計數(shù)器為1
b = a ? ? ? ? ?# 對象1 被變量b引用，對象1的引用計數(shù)器加1
c = a ? ? ? ? ?# 對象1 被變量c引用，對象1的引用計數(shù)器加1
del a ? ? ? ? ?# 刪除變量a，解除a對1的引用，對象1的引用計數(shù)器減1
del b ? ? ? ? ?# 刪除變量b，解除b對1的引用，對象1的引用計數(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] ? ? ? # 拷貝列表，也不會有數(shù)據(jù)對象的復制，而是創(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
在一個 最小堆 (min heap) 中，如果 P 是 C 的一個父級節(jié)點，那么 P 的 key（或 value) 應小于或等于 C 的對應值。 正因為此，堆頂元素一定是最小的，我們會利用這個特點求最小值或者第 k 小的值。
在一個 最大堆 (max heap) 中，P 的 key（或 value) 大于或等于 C 的對應值。
以python為例，說明堆的幾個常見操作，這里需要用到一個內置的包：heapq
python中使用堆是通過傳入一個數(shù)組，然后調用一個函數(shù)，在原地讓傳入的數(shù)據(jù)具備堆的特性
需要注意的是，heapify默認構造的是小頂堆（min heap），如果要構造大頂堆，思路是把所有的數(shù)值倒轉，既* -1，例如：
使用heapq提供的函數(shù)： heappop 來實現(xiàn)
具體使用方式參考 初始化Heapify
使用heapq提供的函數(shù)： heappush 來實現(xiàn)
同時heapq還提供另外一個函數(shù)： heappushpop ，能夠在一個函數(shù)實現(xiàn)pushpop兩個操作；順序是：先push再pop
根據(jù)官方文檔的描述，這個函數(shù)會比先在外圍先調用heappush，再調用heappop，效率更高
先pop數(shù)據(jù)再push數(shù)據(jù)，和heappushpop的順序是反著的； 同樣的，這樣調用的性能也會比先調用heappop再調用heappush更好
如果pop的時候隊列是空的，會拋出一個異常
可以通過 heapq.merge 將多個 已排序 的輸入合并為一個已排序的輸出，這個本質上不是堆；其實就是用兩個指針迭代
對于這個問題，有一個算法題可以實現(xiàn)相同的功能
從 iterable 所定義的數(shù)據(jù)集中返回前 n 個最大/小元素組成的列表。
函數(shù)為： heapq.nlargest() | heapq.nsmallest()
heapq - Heap queue algorithm - Python 3.10.4 documentation
class SortMethod:
'''
插入排序的基本操作就是將一個數(shù)據(jù)插入到已經排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復雜度為O(n^2)。是穩(wěn)定的排序方法。
插入算法把要排序的數(shù)組分成兩部分：
第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外（讓數(shù)組多一個空間才有插入的位置）
第二部分就只包含這一個元素（即待插入元素）。
在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。
'''
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) 是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。該方法因 DL．Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。
'''
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
'''
冒泡排序重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到沒有再需要交換，也就是說該數(shù)列已經排序完成。
'''
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
'''
快速排序
通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(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] 交換，使有序序列不斷增長直到全部排序完畢。
'''
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ù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。
可以利用數(shù)組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值，即 A[PARENT[i]] = A[i]。
在數(shù)組的非降序排序中，需要使用的就是大根堆，因為根據(jù)大根堆的要求可知，最大的值一定在堆頂。
'''
# 調整堆
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） 的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并過程為：
比較 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，則將第一個有序表中的元素 a[i] 復制到 r[k] 中，并令 i 和 k 分別加上 1；
否則將第二個有序表中的元素 a[j] 復制到 r[k] 中，并令 j 和 k 分別加上 1，如此循環(huán)下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到 r 中從下標 k 到下標 t 的單元。歸并排序的算法我們通常用遞歸實現(xiàn)，先把待排序區(qū)間 [s,t] 以中點二分，接著把左邊子區(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，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序。
其時間復雜度為 O (nlog(r)m)，其中 r 為所采取的基數(shù)，而 m 為堆數(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
來源：CSDN
原文：
版權聲明：本文為博主原創(chuàng)文章，轉載請附上博文鏈接！
