名称
|
复杂度
|
说明
|
备注
|
冒泡排序 BubbleSort
|
O(N*N)
|
将待排序的元素看作是竖着排列的
“
气泡
”
,较小的元素比较轻,从而要往上浮
|
|
插入排序 InsertionSort
|
O(N*N)
|
逐一取出元素,在已经排序的元素序列中从后向前扫描,放到适当的位置
|
起初,已经排序的元素序列为空
|
选择排序 SelcetionSort
|
O(N*N)
|
首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此递归。
|
|
快速排序 QuickSort
|
O(n*log2
(n))
|
先选择中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(递归)。
|
|
堆排序 HeapSort
|
O(n*log2
(n))
|
利用堆(
heaps
)这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或者大于)它的父节点。
|
近似完全二叉树
|
希尔排序 ShellSort
|
O(n1+
£
)
0<
£
<1
|
选择一个步长
(Step) ,
然后按间隔为步长的单元进行排序
.
递归
,
步长逐渐变小
,
直至为
1.
|
|
箱排序 BinSort
|
O(n)
|
设置若干个箱子,把关键字等于
k
的记录全都装入到第
k
个箱子里
(
分配
)
,然后按序号依次将各非空的箱子首尾连接起来
(
收集
)
。
|
分配排序的一种:通过
"
分配
"
和
"
收集
"
过程来实现排序。
|
桶排序 BucketSort
|
O(n)
|
桶排序的思想是把
[0
,
1)
划分为
n
个大小相同的子区间,每一子区间是一个桶。
|
分配排序的一种:通过
"
分配
"
和
"
收集
"
过程来实现排序。
|
冒泡排序
冒泡排序算法的思想:很简单,每次遍历完序列都把最大(小)的元素放在最前面,然后再对剩下的序列重复前面的一个过程,每次遍历完之后待排序序列就少一个元素,当待排序序列减小为只有一个元素的时候排序就结束了。因此,复杂度在最坏的情况下是O(N ^ 2)。
public static void BubbleSort(int[] array){
if(array==null || array.length==0){
return;
}
int size = array.length;
for(int i=0; i<size-1; i++){
boolean hasSwap = false;
for(int j=i+1; j<size; j++){
if(array[j]<array[i]){
// swap
int temp = array[i];
array[i] = array[j];
array[j] = temp;
hasSwap = true;
}
if(!hasSwap){
break;
}
}
}
}
选择排序
选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
public static void SelectionSort(int[] array){
if(array==null || array.length==0){
return;
}
int size = array.length;
for(int i=0; i<size-1; i++){
int minIndex = i;
for(int j=i+1; j<size; j++){
if(array[j]<array[minIndex]){
minIndex = j;
}
}
// 将最小值置于最前端
if(minIndex!=i){
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
}
*与冒泡排序的区别,交换次数。每次遍历找到最小值,只交换一次。冒泡是每次比较都进行交换。
插入排序
插入排序是最简单最直观的排序算法了,它的依据是:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止。
算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是1 + 2 + 3 + …… + N = O(N ^ 2)的复杂度。
public static void InsertionSort(int[] array){
if(array==null || array.length==0){
return;
}
int size = array.length;
// 默认认为第一位是有序的
for(int i=1; i<size; i++){
int key = array[i];
// 对有序列从后向前扫描
int j=0;
for(j=i-1; j>=0; j--){
if(key<array[j]){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = key;
}
}
希尔排序
shell排序是对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了。
public static void ShellSort(int array[])
{
if(array==null || array.length==0){
return;
}
int temp;
int size = array.length;
// 增量从数组长度的一半开始,每次减小一倍
for (int increment = size / 2; increment > 0; increment /= 2)
{
for (int i = increment; i < size; ++i)
{
temp = array[i];
// 对一组增量为increment的元素进行插入排序
int j = 0;
for (j = i; j >= increment; j -= increment)
{
// 把i之前大于array[i]的数据向后移动
if (temp < array[j - increment])
{
array[j] = array[j - increment];
} else
{
break;
}
}
// 在合适位置安放当前元素
array[j] = temp;
}
}
}
快速排序
快速排序的算法思想: 选定一个枢轴元素,对待排序序列进行分割,分割之后的序列一个部分小于枢轴元素,一个部分大于枢轴元素,再对这两个分割好的子序列进行上述的过程。
public static void QuickSort(int[] array, int low, int hight){
if(array==null || array.length==0){
return;
}
if(low<hight){
int n = Partition(array, low, hight);
QuickSort(array, 0, n);
QuickSort(array, n+1, hight);
}
}
// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
private static int Partition(int[] array, int low, int hight){
// 采用子序列的第一个元素为枢纽元素
int pivot = array[low];
int temp = 0;
while(low<hight){
// 从后往前在后半部分中寻找第一个小于枢纽元素的元素
while(low<hight && array[hight]>=pivot){
hight--;
}
// 将这个比枢纽元素小的元素交换到前半部分
temp = array[low];
array[low] = array[hight];
array[hight] = pivot;
// 从前往后在前半部分中寻找第一个大于枢纽元素的元素
while(low<hight && array[low]<=pivot){
low++;
}
// 将这个比枢纽元素大的元素交换到后半部分
temp = array[low];
array[low] = array[hight];
array[hight] = temp;
}
// 返回枢纽元素所在的位置
return low;
}
分享到:
相关推荐
自己整理的八大排序算法的实现以及其各自的特点,希望能帮助需要的人
数据结构教材8种常见排序算法用c++代码编码实现,而且测试过啦,都能够正确运行
常见的十种排序算法(冒泡/选择/插入/计数/基数/堆/归并/快速/桶/希尔排序)
常见的排序算法进行整理,包括:插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、二叉树排序、计数 排序、桶排序、基数排序。
呵呵,只是把几种常见的排序算法,集中自己整理了一下,需要的,可以看看!
it面试算法题整理 全 包括笔试面试常考的 剑指offer 程序员面试宝典 各种排序算法等 自己总结的 自己总结的 找工作笔试面试用
包含了常见算法的实现,有详细的注释和输入输出截图
前言:前两天腾讯笔试受到1万点暴击,感觉浪费我两天时间去牛客网做题……这篇博客介绍几种简单/常见的排序算法,算是整理下。 时间复杂度 (1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须...
因此,我们很有必要对所有常见的排序算法进行归纳。 我不喜欢死记硬背,我更偏向于弄清来龙去脉,理解性地记忆。比如下面这张时间复杂度图,我们将围绕这张图来分析。 上面的这张图来自一个PPT。它概括了数据结构...
一些常见的排序算法,自己整理的,关键地方有注释
十大滤波算法程序大全(精心整理版).pdf
整理了几种常见的排序动态图和代码
此文档是作者收集整理的数据结构中常见的排序算法,包括算法实现的图解及Java代码,如有错误的地方还望指出,大家相互学习。
这是一个前端面试盒子,侧重于 JS 代码,里面整理了一些有用的前端代码,包括剑指 offer 的 JS 版、JS 设计模式、常见排序查找算法、《深入浅出 Nodejs》、《JS 高级程序设计》中的代码,希望对大家春招、秋招求职有...
常见的数据结构Flash动画演示有: 1 二叉树的删除、建立、查找,中序线索化二叉树等 ...3 多种排序算法 4 常见的图算法演示 5 hash算法演示 6 B数的生成、删除的演示 7 栈队列的演示 8 字符串匹配算法演示
★★★字符串去除字符串首尾空格 ★算法算法需要掌握基本的数据结构,例如栈、队列、链表、树、排序算法等等,建议去 LeetCode 上刷题。不过不要为了刷题而刷题,最重要的是归纳与总结,刷十道不如一道刷十遍。归并...
冒泡排序是常用的排序算法,笔试中非常常见。 算法重复地走访过排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换,使越大的元素会经有交换慢慢“冒泡”到顶端。 步骤: 1、先比较开始相邻的两个元素,...
主要介绍了PHP经典算法集锦,整理了各种常见的算法,包括排序、查找、遍历、运算等各种常见算法原理与实现技巧,需要的朋友可以参考下
并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1、数据结构(1)基本数据结构数据结构基本概念(时间复杂度和空间复杂度的计算方法)数组链表集合队列栈关联数组跳表倒排索引BitSet(2)树...
整理的一些常见互联网海量数据排序面试题。