time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C++基础 > 总结了一些常见的排序算法,面试必备啊!

总结了一些常见的排序算法,面试必备啊!

时间:2009-09-21 00:00 点击:429次 字体:[ ]




 名称

 复杂度  说明  备注
 冒泡排序
Bubble Sort

O(N*N)

 

将待排序的元素看作是竖着排列的气泡,较小的元素比较轻,从而要往上浮

 
 

插入排序

Insertion sort

 

O(N*N)

 

逐一取出元素,在已经排序的元素序列中从后向前扫描,放到适当的位置

 

起初,已经排序的元素序列为空

 

选择排序

 

O(N*N)

 

首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此递归。

 
 

快速排序

Quick Sort

 

O(n *log2(n))

 

先选择中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(递归)。

 
 

堆排序Heap Sort

 

O(n *log2(n))

 

利用堆(heaps)这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或者大于)它的父节点。

近似完全二叉树

 

希尔排

SHELL

 

O(n1+)

0<<1

 

选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1.

 
 

箱排序
Bin Sort

 

O(n)

 

设置若干个箱子,把关键字等于 k 的记录全都装入到第 k 个箱子里 ( 分配 ) ,然后按序号依次将各非空的箱子首尾连接起来 ( 收集 )

 

分配排序的一种:通过 " 分配 " " 收集 " 过程来实现排序。

 

桶排序

Bucket Sort

 

O(n)

 

桶排序的思想是把 [0 1) 划分为 n 个大小相同的子区间,每一子区间是一个桶。



本文地址 : http://www.fengfly.com/plus/view-78134-1.html
标签:
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码: