冒泡,选择,插入,希尔,归并,快速,堆,计数,桶,基数注意快排的时间复杂度错了是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[j1]:nums[j],nums[j1]nums[j1],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)):kiforjinrange(i1,len(nums)):ifnums[j]nums[k]:kj 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)):curnums[i]preidxi-1whilepreidx0andnums[preidx]cur:nums[preidx1]nums[preidx]preidx-1nums[preidx1]cur4. 希尔平均O(n1.5)O(n^{1.5})O(n1.5)?空间O(1)O(1)O(1)不稳定gapint(len(nums)/2)whilegap0:foriinrange(gap,len(nums)):preidxi-gap curnums[i]whilepreidx0andnums[preidx]cur:nums[preidxgap]nums[preidx]preidx-gap nums[preidxgap]cur gapint(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):idxleft left_numnums[left:mid1]right_numnums[mid1:right1]whileleft_numandright_num:ifleft_num[0]right_num[0]:nums[idx]left_num.pop(0)idx1else:nums[idx]right_num.pop(0)idx1whileleft_num:nums[idx]left_num.pop(0)idx1whileright_num:nums[idx]right_num.pop(0)idx1defmergeSort(nums,left,right):ifleftright:returnmid(leftright)//2mergeSort(nums,left,mid)mergeSort(nums,mid1,right)merge(nums,left,mid,right)numsmergeSort(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:ansleftifright:ansrightreturnansdefmergeSort(nums):iflen(nums)2:returnnums interval1whileintervallen(nums):low0whilelowlen(nums):midlowinterval highmin(low2*interval,len(nums))ifmidhigh:nums[low:high]merge(nums[low:mid],nums[mid:high])low2*interval interval*2returnnums numsmergeSort(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):pivotnums[left]whileleftright:whileleftrightandnums[right]pivot:right-1nums[left]nums[right]whileleftrightandnums[left]pivot:left1nums[right]nums[left]nums[left]pivotreturnleftdefquickSort(nums,left,right):ifleftright:midpartition(nums,left,right)quickSort(nums,left,mid-1)quickSort(nums,mid1,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):ifleftright:returnpivotnums[left]ileft1jrightwhileTrue:whileijandnums[i]pivot:i1whileijandnums[j]pivot:j-1ifij:breaknums[i],nums[j]nums[j],nums[i]i1j-1nums[left],nums[j]nums[j],nums[left]returnjdefquick2way(nums,left,right):ifleftright:returnidxpartition(nums,left,right)quick2way(nums,left,idx-1)quick2way(nums,idx1,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):left2*idx1right2*idx2maxidxidxifleftlengthandnums[left]nums[maxidx]:maxidxleftifrightlengthandnums[right]nums[maxidx]:maxidxrightifmaxidx!idx:nums[maxidx],nums[idx]nums[idx],nums[maxidx]heapify(maxidx,length)defheapSort(nums):lengthlen(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 numsheapSort(nums)8. 计数平均O(nk)O(nk)O(nk)最好O(nk)O(nk)O(nk)最差O(nk)O(nk)O(nk)空间O(nk)O(nk)O(nk)稳定defcountSort(nums):cnt[0]*(max(nums)1)fornuminnums:cnt[num]1ans[]fornuminrange(len(cnt)):foriinrange(cnt[num]):ans.append(num)returnans numscountSort(nums)9. 桶平均O(nk)O(nk)O(nk)最好O(n)O(n)O(n)最差O(n2)O(n^2)O(n2)空间O(nk)O(nk)O(nk)稳定deffindpivot(nums,left,right):pivotnums[left]whileleftright:whileleftrightandnums[right]pivot:right-1nums[left]nums[right]whileleftrightandnums[left]pivot:left1nums[right]nums[left]nums[left]pivotreturnleftdefquickSort(nums,left,right):ifleftright:returnpivotfindpivot(nums,left,right)quickSort(nums,left,pivot-1)quickSort(nums,pivot1,right)defbucketSort(nums):bucket_nummax(nums)//21buckets[[]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 numsbucketSort(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(nk)O(nk)O(nk)稳定
python 常用7种排序算法
冒泡,选择,插入,希尔,归并,快速,堆,计数,桶,基数注意快排的时间复杂度错了是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[j1]:nums[j],nums[j1]nums[j1],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)):kiforjinrange(i1,len(nums)):ifnums[j]nums[k]:kj 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)):curnums[i]preidxi-1whilepreidx0andnums[preidx]cur:nums[preidx1]nums[preidx]preidx-1nums[preidx1]cur4. 希尔平均O(n1.5)O(n^{1.5})O(n1.5)?空间O(1)O(1)O(1)不稳定gapint(len(nums)/2)whilegap0:foriinrange(gap,len(nums)):preidxi-gap curnums[i]whilepreidx0andnums[preidx]cur:nums[preidxgap]nums[preidx]preidx-gap nums[preidxgap]cur gapint(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):idxleft left_numnums[left:mid1]right_numnums[mid1:right1]whileleft_numandright_num:ifleft_num[0]right_num[0]:nums[idx]left_num.pop(0)idx1else:nums[idx]right_num.pop(0)idx1whileleft_num:nums[idx]left_num.pop(0)idx1whileright_num:nums[idx]right_num.pop(0)idx1defmergeSort(nums,left,right):ifleftright:returnmid(leftright)//2mergeSort(nums,left,mid)mergeSort(nums,mid1,right)merge(nums,left,mid,right)numsmergeSort(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:ansleftifright:ansrightreturnansdefmergeSort(nums):iflen(nums)2:returnnums interval1whileintervallen(nums):low0whilelowlen(nums):midlowinterval highmin(low2*interval,len(nums))ifmidhigh:nums[low:high]merge(nums[low:mid],nums[mid:high])low2*interval interval*2returnnums numsmergeSort(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):pivotnums[left]whileleftright:whileleftrightandnums[right]pivot:right-1nums[left]nums[right]whileleftrightandnums[left]pivot:left1nums[right]nums[left]nums[left]pivotreturnleftdefquickSort(nums,left,right):ifleftright:midpartition(nums,left,right)quickSort(nums,left,mid-1)quickSort(nums,mid1,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):ifleftright:returnpivotnums[left]ileft1jrightwhileTrue:whileijandnums[i]pivot:i1whileijandnums[j]pivot:j-1ifij:breaknums[i],nums[j]nums[j],nums[i]i1j-1nums[left],nums[j]nums[j],nums[left]returnjdefquick2way(nums,left,right):ifleftright:returnidxpartition(nums,left,right)quick2way(nums,left,idx-1)quick2way(nums,idx1,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):left2*idx1right2*idx2maxidxidxifleftlengthandnums[left]nums[maxidx]:maxidxleftifrightlengthandnums[right]nums[maxidx]:maxidxrightifmaxidx!idx:nums[maxidx],nums[idx]nums[idx],nums[maxidx]heapify(maxidx,length)defheapSort(nums):lengthlen(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 numsheapSort(nums)8. 计数平均O(nk)O(nk)O(nk)最好O(nk)O(nk)O(nk)最差O(nk)O(nk)O(nk)空间O(nk)O(nk)O(nk)稳定defcountSort(nums):cnt[0]*(max(nums)1)fornuminnums:cnt[num]1ans[]fornuminrange(len(cnt)):foriinrange(cnt[num]):ans.append(num)returnans numscountSort(nums)9. 桶平均O(nk)O(nk)O(nk)最好O(n)O(n)O(n)最差O(n2)O(n^2)O(n2)空间O(nk)O(nk)O(nk)稳定deffindpivot(nums,left,right):pivotnums[left]whileleftright:whileleftrightandnums[right]pivot:right-1nums[left]nums[right]whileleftrightandnums[left]pivot:left1nums[right]nums[left]nums[left]pivotreturnleftdefquickSort(nums,left,right):ifleftright:returnpivotfindpivot(nums,left,right)quickSort(nums,left,pivot-1)quickSort(nums,pivot1,right)defbucketSort(nums):bucket_nummax(nums)//21buckets[[]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 numsbucketSort(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(nk)O(nk)O(nk)稳定
