企业官网建设流程全解析

冒泡,选择,插入,希尔,归并,快速,堆,计数,桶,基数

注意：快排的时间复杂度错了，是O(logn)，最差O(n)，就是递归的空间占用

1. 冒泡

平均O(n2)O(n^{2})O(n2)，最好O(n)O(n)O(n)，最差O(n2)O(n^{2})O(n2)，空间O(1)O(1)O(1)，稳定

foriinrange(1,len(nums)):forjinrange(len(nums)-i):ifnums[j]>nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]

2. 选择

平均O(n2)O(n^{2})O(n2)，最好O(n2)O(n^{2})O(n2)，最差O(n2)O(n^{2})O(n2)，空间O(1)O(1)O(1)，不稳定

foriinrange(len(nums)):k=iforjinrange(i+1,len(nums)):ifnums[j]<nums[k]:k=j nums[i],nums[k]=nums[k],nums[i]

3. 插入

平均O(n2)O(n^{2})O(n2)，最好O(n)O(n)O(n)，最差O(n2)O(n^{2})O(n2)，空间O(1)O(1)O(1)，稳定

foriinrange(len(nums)):cur=nums[i]preidx=i-1whilepreidx>=0andnums[preidx]>cur:nums[preidx+1]=nums[preidx]preidx-=1nums[preidx+1]=cur

4. 希尔

平均O(n1.5)O(n^{1.5})O(n1.5)?，空间O(1)O(1)O(1)，不稳定

gap=int(len(nums)/2)whilegap>0:foriinrange(gap,len(nums)):preidx=i-gap cur=nums[i]whilepreidx>=0andnums[preidx]>cur:nums[preidx+gap]=nums[preidx]preidx-=gap nums[preidx+gap]=cur gap=int(gap/2)

5. 归并

平均O(nlogn)O(nlogn)O(nlogn)，最好O(nlogn)O(nlogn)O(nlogn)，最差O(nlogn)O(nlogn)O(nlogn)，空间O(n)O(n)O(n)，稳定

第一种：自上而下的递归

defmerge(nums,left,mid,right):idx=left left_num=nums[left:mid+1]right_num=nums[mid+1:right+1]whileleft_numandright_num:ifleft_num[0]<right_num[0]:nums[idx]=left_num.pop(0)idx+=1else:nums[idx]=right_num.pop(0)idx+=1whileleft_num:nums[idx]=left_num.pop(0)idx+=1whileright_num:nums[idx]=right_num.pop(0)idx+=1defmergeSort(nums,left,right):ifleft>=right:returnmid=(left+right)//2mergeSort(nums,left,mid)mergeSort(nums,mid+1,right)merge(nums,left,mid,right)nums=mergeSort(nums,0,len(nums)-1)

第二种：自下而上的迭代

defmerge(left,right):ans=[]whileleftandright:ifleft[0]<right[0]:ans.append(left.pop(0))else:ans.append(right.pop(0))ifleft:ans+=leftifright:ans+=rightreturnansdefmergeSort(nums):iflen(nums)<2:returnnums interval=1whileinterval<len(nums):low=0whilelow<len(nums):mid=low+interval high=min(low+2*interval,len(nums))ifmid<high:nums[low:high]=merge(nums[low:mid],nums[mid:high])low+=2*interval interval*=2returnnums nums=mergeSort(nums)

6. 快速

平均O(nlogn)O(nlogn)O(nlogn)，最好O(nlogn)O(nlogn)O(nlogn)，最差O(n2)O(n^{2})O(n2)，空间O(nlogn)O(nlogn)O(nlogn)，不稳定

defpartition(nums,left,right):pivot=nums[left]whileleft<right:whileleft<rightandnums[right]>pivot:right-=1nums[left]=nums[right]whileleft<rightandnums[left]<=pivot:left+=1nums[right]=nums[left]nums[left]=pivotreturnleftdefquickSort(nums,left,right):ifleft<right:mid=partition(nums,left,right)quickSort(nums,left,mid-1)quickSort(nums,mid+1,right)returnnums# 使用nums=[3,6,8,10,1,2,1]quickSort(nums,0,len(nums)-1)print(nums)# [1, 1, 2, 3, 6, 8, 10]

双路快排，当数组中存在大量重复元素的时候，一般的快排会退化为O(n2)O(n^2)O(n2)的时间复杂度，双路快排和一般快排的区别就在于partition的方式，它是将大于pivot的值放到左边，小于pivot的值放到右边，而等于pivot的值可以在左边，也可以在右边，从而防止极端划分情况的发生。

defpartition(nums,left,right):ifleft>=right:returnpivot=nums[left]i=left+1j=rightwhileTrue:whilei<=jandnums[i]<pivot:i+=1whilei<=jandnums[j]>pivot:j-=1ifi>=j:breaknums[i],nums[j]=nums[j],nums[i]i+=1j-=1nums[left],nums[j]=nums[j],nums[left]returnjdefquick2way(nums,left,right):ifleft>=right:returnidx=partition(nums,left,right)quick2way(nums,left,idx-1)quick2way(nums,idx+1,right)quick2way(nums,0,len(nums)-1)

7. 堆

平均O(nlogn)O(nlogn)O(nlogn)，最好O(nlogn)O(nlogn)O(nlogn)，最差O(nlogn)O(nlogn)O(nlogn)，空间O(1)O(1)O(1)，不稳定

defheapify(idx,length):left=2*idx+1right=2*idx+2maxidx=idxifleft<lengthandnums[left]>nums[maxidx]:maxidx=leftifright<lengthandnums[right]>nums[maxidx]:maxidx=rightifmaxidx!=idx:nums[maxidx],nums[idx]=nums[idx],nums[maxidx]heapify(maxidx,length)defheapSort(nums):length=len(nums)# 建最大堆foriinrange(length//2-1,-1,-1):heapify(i,length)foriinrange(len(nums)-1,0,-1):nums[0],nums[i]=nums[i],nums[0]length-=1heapify(0,length)returnnums nums=heapSort(nums)

8. 计数

平均O(n+k)O(n+k)O(n+k)，最好O(n+k)O(n+k)O(n+k)，最差O(n+k)O(n+k)O(n+k)，空间O(n+k)O(n+k)O(n+k)，稳定

defcountSort(nums):cnt=[0]*(max(nums)+1)fornuminnums:cnt[num]+=1ans=[]fornuminrange(len(cnt)):foriinrange(cnt[num]):ans.append(num)returnans nums=countSort(nums)

9. 桶

平均O(n+k)O(n+k)O(n+k)，最好O(n)O(n)O(n)，最差O(n2)O(n^2)O(n2)，空间O(n+k)O(n+k)O(n+k)，稳定

deffindpivot(nums,left,right):pivot=nums[left]whileleft<right:whileleft<rightandnums[right]>pivot:right-=1nums[left]=nums[right]whileleft<rightandnums[left]<=pivot:left+=1nums[right]=nums[left]nums[left]=pivotreturnleftdefquickSort(nums,left,right):ifleft>=right:returnpivot=findpivot(nums,left,right)quickSort(nums,left,pivot-1)quickSort(nums,pivot+1,right)defbucketSort(nums):bucket_num=max(nums)//2+1buckets=[[]for_inrange(bucket_num)]fornuminnums:buckets[num//2].append(num)ans=[]forbucket_iinbuckets:quickSort(bucket_i,0,len(bucket_i)-1)fornuminbucket_i:ans.append(num)returnans nums=bucketSort(nums)

10. 基数排序

平均O(n∗k)O(n*k)O(n∗k)，最好O(n∗k)O(n*k)O(n∗k)，最差O(n∗k)O(n*k)O(n∗k)，空间O(n+k)O(n+k)O(n+k)，稳定