江宁网站建设方案,石家庄市制作网站公司,泰安网站推广优化,六安人才招聘网官网一.时间复杂度分析
- **时间复杂度**#xff1a;对排序数据的总的操作次数。反应当n变化时#xff0c;操作次数呈现什么规律 - **空间复杂度**#xff1a;算法在计算机内执行时所需要的存储空间的容量#xff0c;它也是数据规模n的函数。
1.例题:
有一个字符串数组…一.时间复杂度分析
- **时间复杂度**对排序数据的总的操作次数。反应当n变化时操作次数呈现什么规律 - **空间复杂度**算法在计算机内执行时所需要的存储空间的容量它也是数据规模n的函数。
1.例题:
有一个字符串数组将数组中的每一个字符串按照字母序排序之后再将整个字符串数组按照字典序排序时间复杂度多少
假设最长字符串长度为s,有n个字符串则每个字符串按照字母序排序时间复杂度为O(n*slogs)
整个字符串数组按照字典序排序时间复杂度为:O(s*nlogn),所以总的时间复杂度为:O(n*slogss*nlogn)
各种排序算法复杂度: 二各种排序算法
冒泡排序
**复杂度分析**
- 时间复杂度若给定的数组刚好是排好序的数组采用改进后的冒泡排序算法只需循环一次就行了此时是最优时间复杂度O(n)若给定的是倒序此时是最差时间复杂度O(n^2) 因此综合平均时间复杂度为O(n^2) - 空间复杂度因为每次只需开辟一个temp的空间因此空间复杂度是O(1)是一个原地排序算法等于的话不做交换故是一个稳定的排序算法。
步骤
1. 比较相邻的元素。如果第一个比第二个大就交换它们两个 2. 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数 3. 针对所有的元素重复以上的步骤除了最后一个 4. 重复步骤1~3直到排序完成。
代码 冒泡排序:从小到大def BubbleSort(array):lengths len(array)for i in range(lengths-1):for j in range(lengths-1-i):if array[j] array[j1]:array[j1], array[j] array[j], array[j1]return arrayif __name__ __main__:# array[5,3,5,8,1,-4,56,87]# print(array)# QuickSort(array,0,len(array)-1)# print(array)array [5, 3, 5, 8, 1, -4, 56, 87]print(Original array: , array)array BubbleSort(array)print(BubbleSort: , array)
c实现:
//
// Created by fzh on 2021/4/29.
//
#include iostream
#include string
using namespace std;
void bubbleSort(int* p, int length){for(int i 0; i length - 1; i){for(int j 0; jlength - i - 1; j){if(p[j] p[j 1]){
// coutarr[j]:arr[j]endl;int temp p[j];p[j] p[j 1];p[j 1] temp;}}}
}
int main() {int arr[10] {2,2,3,5,19,6,7,8,9,10};int length sizeof(arr)/sizeof(arr[0]);coutlength:lengthendl;bubbleSort(arr, length);for(int i0; i10; i){cout arr[i]: arr[i] endl;}
}
2.插入排序
将未排序元素一个个插入到已排序列表中。对于未排序元素在已排序序列中从后向前扫描找到相应位置把它插进去在从后向前扫描过程中需要反复把已排序元素逐步向后挪为新元素提供插入空间。空间复杂度是O(1),也就是一个原地排序算法稳定的排序算法平均时间复杂度O(n2)相比冒泡排序其更受欢迎主要冒泡排序的数据交换要比插入排序复杂冒泡排序需要三个赋值操作而插入排序只需要一个。 插入排序从小到大def InsertionnSort(array):lengths len(array)# 从索引位置1开始for i in range(1, lengths):currentValue array[i] # 当前索引对应的元素数值preIndex i - 1 # 前一个索引位置# 循环条件: 前一个索引对应元素值大于当前值前一个索引值大于等于0while array[preIndex] currentValue and preIndex 0:array[preIndex 1] array[preIndex] # 前一个索引对应元素值赋值给当前值preIndex - 1 # 前一个索引位置-1# preIndex1实现元素交换array[preIndex 1] currentValuereturn arrayarray [1, 0, 8, -2, 3, 6, 9]
print(Original array{}.format(array))
array InsertionnSort(array)
print(InsertionSort{}.format(array))
def insert_sort():a [9, 8, 3, -3, -7, 1, -5]for i in range(1,len(a)):# value a[i]for j in range(0,i-1):if a[j]a[i]:a[j],a[i]a[i],a[j]print(a) 3.选择排序
说明首先在未排序序列中找到最小大元素与起始位置元素进行交换然后再从剩余未排序元素中继续寻找最小大元素然后在交换。以此类推直到所有元素均排序完毕。空间复杂度是O(1)是原地排序算法平均时间复杂度是O(n2)是不稳定的排序算法因为每次都要找未排序的最小值交换
比如 58529 这样一组数据使用选择排序算法来排序2要跟第一个5发生交换那么这两个5的顺序就发生了变化 def SelectionSort(arr):for i in range(len(arr)-1):minIndexifor j in range(i1,len(arr)):if arr[j]arr[minIndex]:minIndexjif i!minIndex:arr[i],arr[minIndex]arr[minIndex],arr[i]return arr
arr[-1,-3,-6,3,4,0,2]
print(arr)
arrSelectionSort(arr)
print(arr) 4.归并排序
归并排序和快速排序时间复杂度为O(nlogn)更适合大规模的数据排序采用了分治的思想由于借用temp数组故空间复杂度为O(n)是一个稳定的排序算法。 写法1:
def Merge(q, r):left, right 0, 0result []while left len(q) and right len(r):# 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置if q[left] r[right]:result.append(q[left])left 1else:result.append(r[right])right 1result q[left:] # 若最后left列表剩余则将其剩余部分加入到result后面result r[right:] # 若最后right列表剩余则将其剩余部分加入到result后面return resultdef Merge_Sort(L):if len(L) 1:return Lmid len(L) // 2 # 这里的//是python3中除以后取整的用法大家不要以为我打错了q Merge_Sort(L[:mid])r Merge_Sort(L[mid:])return Merge(q, r)a[1,2,9,0,8,2,3]
bMerge_Sort(a)
print(b)写法2:
class Solution:def mergeSort(self, nums, start, end):if start end:returnmid start (end - start) // 2self.mergeSort(nums, start, mid)self.mergeSort(nums, mid 1, end)self.merge(nums, start, mid, end)def merge(self, nums, start, mid, end):i, j, temp start, mid 1, []while i mid and j end:if nums[i] nums[j]:temp.append(nums[i])i 1else:self.cnt mid - i 1temp.append(nums[j])j 1while i mid:temp.append(nums[i])i 1while j end:temp.append(nums[j])j 1for i in range(len(temp)):nums[start i] temp[i]print(nums:, nums)def reversePairs(self, nums):self.cnt 0self.mergeSort(nums, 0, len(nums) - 1)print(after nums:, nums)return self.cntnums [7,5,6,4]
sol Solution()
sol.reversePairs(nums)
print(sol.cnt)k路归并排序:
给出K个有序的数组现在将其归并成一个有序数组怎么做最快。
def Merge(q, r):left, right 0, 0result []while left len(q) and right len(r):# 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置if q[left] r[right]:result.append(q[left])left 1else:result.append(r[right])right 1result q[left:] # 若最后left列表剩余则将其剩余部分加入到result后面result r[right:] # 若最后right列表剩余则将其剩余部分加入到result后面return resultdef Merge_Sort(L):if len(L) 1:return L[0]mid len(L) // 2q Merge_Sort(L[:mid])r Merge_Sort(L[mid:])print(q:, q)print(r:, r)return Merge(q, r)# a [1, 2, 9, 0, 8, 2, 3]
a [[1, 2],[0, 3],[-4, 8]]
b Merge_Sort(a)
print(b:, b) 快速排序
思想通过一趟排序将待排列表分成独立的两部分其中一部分的所有元素均比另一部分的元素小则分别对这两部分继续重复进行此操作以达到整个序列有序。
步骤
使用分治法把一个串分为两个子串具体算法描述如下
1从数列中挑出一个元素称为基准(privot)本文将第一个选为基准
2比基准数小的所有元素放在基准前面比基准数大的所有元素放在基准后面这样完成了分区操作;
3递归地把小于基准值元素的子数列和大于基准值元素的子数列按上述操作进行排序递归结束条件序列的大小为0或1。
根据分治递归的处理思想利用递归排序下标从p到q-1之间的数据和下标从q1到r之间的数据直至区间缩小为1说明所有的数据都有序了跟归并排序不同的是要做成原地排序算法不借用temp空间复杂度为O1时间复杂度为Onlogn。由于涉及到选择基准倘若基准是两个相同的数经过分区处理后顺序可能发生变化故是不稳定的算法。 流程 代码
def QuickSort(array,start,end):lengthlen(array)istartjendif ij:returnprivotarray[i]while ij:#从右往左while ij and privotarray[j]:j-1array[i]array[j]# print(array)# 从左往右while i j and privot array[i]:i 1array[j] array[i]# print(array)array[i]privot# print(array)#QuickSort(array,start,i-1)QuickSort(array, i1, end)
if __name__ __main__:array[5,3,5,8,1,-4,56,87]print(array)QuickSort(array,0,len(array)-1)print(array) 更快的方式
#选择中间的数作为基准
def quicksort(arr):if len(arr) 1:return arrpivot arr[len(arr) // 2]left [x for x in arr if x pivot]print(left,left)middle [x for x in arr if x pivot]print(middle, middle)right [x for x in arr if x pivot]print(right, right)return quicksort(left) middle quicksort(right)
if __name__ __main__:print(quicksort([9,8,7,6,5,43,2])) 桶排序
桶排序将要排序的数据分到几个有序的桶里每个桶里的数据单独进行排序。桶内排完序之后再把每个桶里的数据按照顺序依次取出组成的序列就是有序的了。桶排序的时间复杂度为什么是 O(n) 呢排序数据有n个均匀划分到m个桶内每个桶就有kn/m个元素每个桶使用快速排序时间复杂度为O(k*logk)。m个桶排序时复杂度就是O(m*k*logk),故整个桶排序时间复杂度就是O(n*(log(n/m))),m足够大时log(n/m)是一个很小的值故时间复杂度接近O(n)。极端情况下分到一个桶里就变为O(n*logn),其适合外部排序也就是数据存储在外部磁盘中数据量比较大内存有限无法将数据全部加载到内存中。其是一个稳定的排序算法。
计数排序
计数排序可以看成是桶排序的一种特设请情况考生的满分是 900 分最小是 0 分这个数据的范围很小,可以分成901个桶将50万考生划分到901个桶桶内的数据是相同分数的考生只需要依次扫描每个桶将桶内的考生依次输出到一个数组中即实现排序也就是计数排序其只适合于数据范围不大的场景如果数据范围k比排序数据n大很多就不是和计数排序了而且只适合给非负整数排序若有负数需要转换成正数归一化。其是一个稳定的排序算法时间复杂度O(n)
基数排序
基数排序假设有10万个手机号码希望将这10万个手机号码按下到大排序时间复杂度O(n)基数排序对要排序的数据是有要求的需要可以分割出独立的‘位’来比较而且具有递进的关系。其是一个稳定的排序算法。
下面用字母来代替。 总结Glibc的qsort函数会优先使用归并排序对于1k2k左右的数据完全可以用空间換时间因为其空间复杂度是O(n)时间复杂度是O(nlogn)。 对于小数量数据的排序O(n2)的排序算法并不一定比O(nlogn)排序算法执行时间长对于小数据的排序选择简单 不需要递归的插入排序算法递归过深容易导致堆栈溢出。
数据量较大的情况就用快速排序分区点的选择可以用三数取中法和随机法 1,三数取中法从区间的首尾中间分别取出一个数然后比对大小取这三个数的中间值作为分区点如果排序的数组很大可能就要用多个数来取中间值。 2,随机法每次从要排序的区间随机选择一个元素作为分区点从概率的角度讲不会出现每个分区点都会选的很差的情况。
