插入排序(双向链表实现) - 数据结构与算法
算法思想
把所有需要排序的数据分成两个集合,一个是待排序集合,一个是已排序的集合,算法每次从未排序集合顺序或随机拿取一个数据,把它加入到已排序集合使其有序,直到未排序集合中的数据被取走完,算法结束
案例代码:
数组a是未排序集合,已排序的集合是逻辑上的一个集合,可以看作是head,实现是一个双向链表,add方法向集合添加数据,每次找到对应的位置,使链表有序,toArray方法使已排序的集合输出成int数组。
public class Test5{
public static void main(String args[]){
int[] a=new int[]{1,9,5,4,2,5,1,5,6,8,7,4,1,5,4,5,1,2,1,2};
a=sort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public static int[] sort(int[] a){
for(int i=0;i<a.length;i++){
add(a[i]);
}
return toArray(a.length);
}
public static int[] toArray(int size){
int a[]=new int[size];
Node p=head;
int i=0;
while(p!=null){
a[i++]=p.data;
p=p.next;
}
return a;
}
public static void add(int data){
Node n=new Node(data);
if(head==null){
head=n;
return;
}else{
Node p=head;
while(p!=null){
if(n.data<=p.data){
if(p!=head){
n.next=p;
p.prev.next=n;
n.prev=p.prev;
p.prev=n;
return;
}else{
p.prev=n;
n.next=p;
head=n;
return;
}
}else{
if(p.next!=null){
p=p.next;
}else{
break;
}
}
}
p.next=n;
n.prev=p;
}
}
public static Node head;
static class Node{
public int data;
public Node next;
public Node prev;
public Node(int data){
this.data=data;
}
}
}
评论区
请写下您的评论...
猜你喜欢
blog
插入排序 - 数据结构与算法
数据结构与算法
1389
算法思想:把所有需要排序的数据分成两个集合,一个是待排序集合,一个是已排序的集合,算法每次从未排序集合顺序或随机拿取一个数据,把它加入到已排序集合使其有序,直到未排序集合中的数据被取走完,算法结束
blog
希尔排序 - 数据结构与算法
数据结构与算法
1505
算法思想:希尔排序是插入排序的增强版,其主要的算法思想还是插入排序的思想。算法描述:在插入排序的基础上,对待排序数组进行间隔为inc的分组,然后对每个分组进行直接插入排序,一次排序完成后,减小inc
blog
归并排序(递归)- 数据结构与算法
数据结构与算法
1487
算法思想该算法使用递归法实现,思路为:每次递归将待排序数组在中间位置分成左右两组,分别对左右两个数组进行归并排序,递归的条件是数组长度必须大于等于3,所以当数组中只有两个数据的时候可以直接进行比较排
blog
快速排序 - 数据结构与算法
数据结构与算法
1687
算法思想将待排序集合以该集合中随机的一个数为分界点分成左右两个集合,一次排序使其右边的集合的数据全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述排序操作,直到递归集合没有数据,递归结束完
blog
数据结构与算法-反转链表-递归法
数据结构与算法
7986
反转链表有一个单向链表t如下:t=1-2-3-4-5-6-7-8-9写一个方法反转链表t如下:1-2-3-4-5-6-7-8-9=tjava代码:packagetest;/*** 节点类
blog
数据结构+算法-堆排序
数据结构与算法
4919
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
blog
冒泡排序 - 数据结构与算法
数据结构与算法
1314
算法思想:每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完算法描述:用变量i遍历整个数组,用变量j遍历i后面的数组,每次交换i比j大的元素,使得i遍历过
blog
程序员必须掌握的数据结构和算法
数据结构与算法
2142
原文链接:https://www.zhihu.com/question/23148377?sort=created算法基础 时间复杂度 空间复杂度基础数据结构 线性表 列表(必学) 链表(必学
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
2024-08
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。