當前位置:成語大全網 - 新華字典 - 在python中,如i=

在python中,如i=

歸並排序

歸並排序也稱合並排序,是分治法的典型應用。分治思想是將每個問題分解成個個小問題,將每個小問題解決,然後合並。

具體的歸並排序就是,將壹組無序數按n/2遞歸分解成只有壹個元素的子項,壹個元素就是已經排好序的了。然後將這些有序的子元素進行合並。

合並的過程就是 對 兩個已經排好序的子序列,先選取兩個子序列中最小的元素進行比較,選取兩個元素中最小的那個子序列並將其從子序列中

去掉添加到最終的結果集中,直到兩個子序列歸並完成。

代碼如下:

#!/usr/bin/python?import sysdef merge(nums, first, middle, last):?''''' merge '''?# 切片邊界,左閉右開並且是了0為開始?lnums = nums[first:middle+1]?rnums = nums[middle+1:last+1]?lnums.append(sys.maxint)?rnums.append(sys.maxint)?l = 0?r = 0?for i in range(first, last+1):?if lnums[l] < rnums[r]:?nums[i] = lnums[l]?l+=1?else:?nums[i] = rnums[r]?r+=1?def merge_sort(nums, first, last):?''''' merge sortmerge_sort函數中傳遞的是下標,不是元素個數'''?if first < last:?middle = (first + last)/2?merge_sort(nums, first, middle)?merge_sort(nums, middle+1, last)?merge(nums, first, middle,last)if __name__ == '__main__':?nums = [10,8,4,-1,2,6,7,3]?print 'nums is:', nums?merge_sort(nums, 0, 7)?print 'merge sort:', nums

穩定,時間復雜度 O(nlog n)

插入排序

代碼如下:

#!/usr/bin/python?importsysdefinsert_sort(a):?''''' 插入排序有壹個已經有序的數據序列,要求在這個已經排好的數據序列中插入壹個數,但要求插入後此數據序列仍然有序。剛開始 壹個元素顯然有序,然後插入壹個元素到適當位置,然後再插入第三個元素,依次類推'''?a_len = len(a)?if a_len = 0 and a[j] > key:?a[j+1] = a[j]?j-=1?a[j+1] = key?return aif __name__ == '__main__':?nums = [10,8,4,-1,2,6,7,3]?print 'nums is:', nums?insert_sort(nums)?print 'insert sort:', nums

穩定,時間復雜度 O(n^2)

交換兩個元素的值python中妳可以這麽寫:a, b = b, a,其實這是因為賦值符號的左右兩邊都是元組

(這裏需要強調的是,在python中,元組其實是由逗號“,”來界定的,而不是括號)。

選擇排序

選擇排序(Selection sort)是壹種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到

排序序列的起始位置,然後,再從剩余未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所

有元素均排序完畢。