排序算法

sorting-algorithm

排序定义排序是计算机内将一组“无序”的记录序列调整为“有序”的记录序列根据时间先来后到的做排序使元素从无序到有序的方法
如商品根据不同条件排序搜索相关性排序及根据时间或以某规则的排序等

排序/Sorting 计算机将一个数据元素（或记录的任意序列重新排列成一个关键字有序的序列
排序算法是一种算法与语言无关

比较排序和非比较排序

排序的时候元素之间是否需要比较分为
比较排序和非比较排序
a 比较排序
需要通过元素之间比较之后再决定先后顺序
如冒泡排序每次都是选取两个元素进行比较
现实生活中按成绩排名或高矮顺序来安排座位
b 非比较排序
不需要通过元素之间的比较就确定每个元素的位置
如基数排序排序时每个元素并不需要比较而是有自己固定的位置
现实生活中非比较排序的例子如vip坐位

稳定和不稳定

排队时出现两个人同时抢占一个位置的情况在排序算法中也会遇到两元素相同的情况
假设有这样一组数据[7 5 2 5] 稳定排序算法和不稳定排序算法得出的结果
a 稳定
如果a原本在b前面而a=b 排序之后a仍然在b的前面
b 不稳定
如果a原本在b的前面而a=b 排序之后 a 可能会出现在 b 的后面

算法复杂度

算法复杂度分为时间复杂度和空间复杂度
时间复杂度是指执行算法所需要的计算工作量
空间复杂度是指执行这个算法所需要的内存空间
算法的复杂性体现在运行该算法时的计算机所需资源的多少上
计算机资源最重要的是时间和空间
即寄存器资源因此复杂度分为时间和空间复杂度
a 时间复杂度
时间复杂度(Time Complexity)是描述运行算法所花费的时间量的计算复杂度记做O(f(n))
n称为问题的规模当n不断变化时,时间频度T(n)也会不断变化
但是变化是有规律的所以引入时间复杂度这个概念
算法中的基本操作重复次数的是问题规模n的某个函数
用T(n)表示若有某个辅助函数f(n)
使得当n趋近于无穷大时 T（n)/f(n)的极限值为不等于零的常数
则称f(n)是T(n)的同数量级函数
记作T(n)=Ｏ(f(n))
称Ｏ(f(n)) 为算法的渐进时间复杂度简称时间复杂度
b 空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度
记做S(n)=O(f(n))