首页 > 其他 > 详细

经典排序算法

时间:2014-05-06 15:36:03      阅读:392      评论:0      收藏:0      [点我收藏+]

数值算法:解方程、微积分、数值分析   多用在工程设计

非数值算法:搜索、排序、拆分、合并   多用在系统

 

一、线性搜索

1.算法

1.1从头开始,依次将每一个元素与查找目标进行比较

1.2或者找到目标,或者找不到目标

2.评估

2.1平均时间复杂度:O(N),线性时间

2.2对数据没有任何规律性要求   穷举法

 

二、二分搜索(折半搜索)

1.算法

1.1假设表中的元素按升序排列

1.2若中间元素与查找目标相等,则查找成功,否则利用中间元素将表划分为前后两个子表

1.3若查找目标小于中间元素,则在前子表中继续查找,否则在后子表中继续查找

1.4重复以上过程,直到查找成功,或者因子表不存在,而宣告失败

2.评估

2.1平均时间复杂度:O(logN)

2.2限制:对数据有有序性要求

 

三、冒泡排序

两两比较,大的靠后排(向上冒泡),每趟冒一个

对N个元素,需要扫描N-1趟,第i趟做N-1-i次比较

1.算法

1.1对相邻元素做两两比较,前者大于后者,彼此交换;

1.2从第一对到最后一对,最大的元素沉降到最后;

1.3针对未排序部分,重复以上步骤,沉降次大元素;

1.4每次扫描越来越少的元素,直至不在发生交换

2.评估

2.1平均时间复杂度:O(N^2)

2.2是稳定排序(排序前后等值元素的数序不变)

2.3对数据的有序性敏感  如果排序接近有序,则排序非常快,且代码复杂度低

 

四 插入排序

1.算法

1.1首元素自然有序;

1.2取出下一个元素,对已排序序列,从后向前扫描;

1.3大于被取出元素者后移;

1.4小于被取出元素者,将被取出元素插入其后;

1.5重复2,直到2处理完所有元素

2.评估

2.平均时间复杂度:O(N^2)

2.2稳定排序、

2.3对数据的有序性非常敏感、

2.4不交换,只是移动,优于冒泡

 

五 选择排序

1.算法

1.1在整个序列中寻找最小元素,与首元素交换、

1.2在剩余序列中寻找最小元素,与剩余序列的首元素交换

1.3直到剩余序列中仅盛一个元素为止

2.评估

2.1不稳定排序 值相同的元素,前后顺序会发生变化

2.2平均时间复杂度  O(N^2)

2.3对数据的有序性不敏感

2.4交换次数少,优于冒泡排序

 

六 快速排序

1.算法

1.1从待排序序列中任意挑选一个元素,作为基准;

1.2将所有小于基准的元素放在基准之前,大于基准的元素放在基准之后,等于基准的元素放在基准之前或之后,这个过程称为分组;

1.3以递归的方式,分别对基准之前和基准之后的分组继续进行分组,知道每个分组内的元素个数不多于1个

2.评估

2.1平均时间复杂度:O(NlogN)线性增长

2.1非稳定排序

2.3如果每次都能均匀分组,速度达到极值

     通常选择中间位置作为基准,产生均匀分组的几率最高

 


 

q_sort原型

void qsort(void* base,            //数组首地址

              size_t nmemb,       //数组元素个数

              size_t size,            //数组元素字节数

              int (*compar)(const void*,const void*)   //比较函数

);

七、归并排序

平均时间复杂度:O(2NlogN)

稳定排序。

对数据的有序性不敏感。

非就地排序。需要额外的内存空间。

经典排序算法,布布扣,bubuko.com

经典排序算法

原文:http://blog.csdn.net/romancegirls/article/details/25037335

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!