深圳做分销网站设计,网站建设几层结构,长沙专业建设网站,中国互联网络信息中心网站快速排序是冒泡排序的改进算法
它采用的是分治法#xff0c;基本思想是把原问题分解为若干规模更小但结构与原问题相似的子问题#xff0c;通过递归解决这些子问题#xff0c;然后将这些子问题的解组合成原问题的解。
它的步骤是
1.在待排序的n个记录中任取一个记录…快速排序是冒泡排序的改进算法
它采用的是分治法基本思想是把原问题分解为若干规模更小但结构与原问题相似的子问题通过递归解决这些子问题然后将这些子问题的解组合成原问题的解。
它的步骤是
1.在待排序的n个记录中任取一个记录以该记录的排序码为准将所有记录都分成两组第1组都小于该数第2组都大于该数。
2.采用相同方法对左右两组分别进行排序直到所有记录都排到相应位置。
以数组57685952为例
选择57作为基准数组
57和52比较52小57和52交换位置
52685957
选择68和57比较57小57和68交换位置
52575968。
由于元素数量小已经完成排序了。同样初始顺序数组需要操作的次数比冒泡排序少多了。
快速排序的基准元素:一般是第一个元素也可以是中位数。
快速排序是一种不稳定的排序方法平均和最优情况下时间复杂度是O(nlog(2)n)
最差的情况此时数组基本有序以第一个时间复杂度是O(n^2)。以中位数为基准情况时间复杂度是O(nlog(2)n)
空间复杂度是O(1)
需要辅助空间存储左侧数据和右侧数据空间复杂度为O(n)
需要记录所有基准元素时空间复杂度为O(log(2)n)
