排序的定义
排序就是重新排列表中的元素,使表中的元素满足关键字有序的过程
算法的稳定性:若待排序表中有两个元素相等,经过排序后原来位置这两个元素的相对位置不变,则称这个算法是稳定的
根据在排序过程中数据元素是否完全放在内存中,可以将排序算法分为两类:内部排序和外部排序。内部排序是指在排序期间元素全部存放在内存中的排序,外部排序是指在排序期间元素无法同时存放在内存中,必须在排序的过程中根据要求不断地在内外存之间移动的排序
不同排序的比较
时间复杂度、空间复杂度、稳定性
解释说明:快排所需要的额外空间来自其递归栈
算法简要描述
非常抱歉,之前的回答可能有误。以下是正确识别的表格内容:
算法种类 | 算法简要描述 | 备注 |
---|---|---|
直接插入排序 | 第i趟排序开始之前,前i-1个元素有序,将第i个元素插入到这个序列中 | - |
冒泡排序 | 每次排序将待排序序列的最大值或者最小值放到最终的位置 | - |
简单选择排序 | 每次选出最大值或者最小值放到最终的位置 | |
希尔排序 | 构造一个增量序列,在子序列内部选用插入排序 | - |
快速排序 | 选择一个枢轴,每趟排序将比枢轴大的数都放到枢轴一边,比枢轴小的数放到另一边 | - |
堆排序 | 构造堆这种数据结构,利用堆来进行排序 | 注意每次弹出的元素是放到最后一个位置,所以构造递增序列要用大根堆 |
二路归并排序 | 每次合并两个有序序列 | - |
基数排序 | 按照每一位的大小来构造排序 | 注意在第二趟排序完成后,最低位将可能不再有序 |
各排序算法的其他性质
算法种类 | 比较次数是否与序列相关 | 备注 |
---|---|---|
直接插入排序 | 是 | - |
冒泡排序 | 是 | - |
简单选择排序 | 否 | |
希尔排序 | 是 | - |
快速排序 | 是 | - |
堆排序 | 是 | - |
二路归并排序 | 是 | - |
基数排序 | - | 基数排序不依赖于元素之间的比较 |