关于数据结构:排序

54次阅读

共计 513 个字符,预计需要花费 2 分钟才能阅读完成。

一. 间接插入排序

相当于把大的元素挪到前面去

优化:折半插入排序

如果是对链表进行间接插入排序,尽管挪动元素的次数变少了,然而最坏状况的比拟次数仍为 n 的平方,所以工夫复杂度仍为 n 的平方

二. 希尔排序

工夫复杂度最坏为 n 的平方,某个状况为 n 的 1.3 次方,但优于间接插入排序。不能对链表应用且不稳固

三. 替换排序(冒泡和疾速)

冒泡排序:

工夫复杂度最坏为 n 的平方(逆序),最好状况为 n(程序),所以均匀为 n 的平方

疾速排序:

但数组为程序或者逆序时,因为枢纽每次都会变成最靠边的元素,会把数组划分成很不平均的两份,所以工夫复杂度很高。但当枢纽能够把数组划分成两个比拟平均的局部时工夫复杂度会比拟低。

优化思路:(1)选头中尾三个元素,而后选两头的作为枢纽(2)随机选一个作为枢纽

均匀工夫复杂度:nlog2n

不稳固

一次划分不等于一次排序,一次排序是对所有未确定地位元素的一次解决,而一次划分只是对一个枢纽元素的解决,所以一次排序可能能够确定多个元素的地位。

四. 抉择排序(简略抉择排序和堆排序)

简略抉择排序:

工夫复杂度为 n 的平方,不稳固,程序表链表皆可

堆排序:

堆的删除与插入

五. 归并排序

六. 基数排序

稳固排序

七. 内部排序

败者树:

置换归并:

归并树的重要性质:

正文完
 0