首页 > 代码库 > 各种排序的实现与复杂度分析(持续更新)
各种排序的实现与复杂度分析(持续更新)
稳定性:
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
复杂度
冒泡法: 复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。不说了。
直接插入排序:O(n*n)
希尔排序:算法的复杂度为n的1.2次幂
选择排序:O(n*n)
快速排序:不稳定,平均时间复杂度O(nlogn),最坏情况时间复杂度为O(n2)。所有内部排序方法中最高好的,大多数情况下总是最好的。空间复杂度主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)
归并排序:log2(n)*n
堆排序:log2(n)*n
算法实现:
首先是快速排序的实现
void quickSort(int A[], int low, int high){ if(low < high){ int i = low, j = high, key = A[i]; while(i < j){ while(i < j && A[j] > key) // 从右向左找第一个小于key的数 --j; if(i < j) A[i++] = A[j]; while(i < j && A[i] < key) // 从左向右找第一个大于等于key的数 ++i; if(i < j) A[j--] = A[i]; } A[i] = key; //mid quickSort(A,low,i-1); quickSort(A,i+1,high); } }
各种排序的实现与复杂度分析(持续更新)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。