1.什么是冒泡排序



下面这个是百度百科的解释:

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

按我的理解就是将相邻的两个元素进行比较,不符合要求的就进行交换位置,交换之后就继续进行下一个的元素的比较,比较一圈之后,最大或者最小的元素就会出现在末端。
冒泡排序

由上图就可以看出,每每相邻就比较,就像一个个泡泡冒起来,我就是这样理解冒泡排序的。

2.链表的冒泡排序思路


1)先讨论下不加虚拟头的情况

在不加虚拟头时候,我们就需要单独讨论当前节点是不是在链表头部,如果是头部的时候,就需要单独创建一个节点来暂时保存头节点,然后就进行交换
无虚拟头交换第一步

在交换之后,这时就可以创建两个引用,分别指向头节点和头节点的下一个节点。

然后通过使用该两个节点的下一个节点就行比较,上面的这两个引用只是为了方便比较和记录。

去掉头节点后

前面的两个节点在第一次进行比较时,符合位置要求,所以向下移一个位置,第二次比较时就需要进行交换位置了,如上图所示,步骤就不多说了,上面都有。

交换位置记得顺序不能改变,变了就会造成引用混乱。

在交换后这时两个节点也可以在上图看出,所以我们只需要移动当前节点即可(currentNode),然后进行下一次比较。

2)接着说带虚拟头的

如果带了虚拟头了,就比上面少了一步,因为不需要进行判断头节点了,这个时候头节点变成了虚拟的,不需要管的了,步骤就和上面的第二步一样。

比较完了,那什么时候停止呢?

因为有时候无法轻易得出链表的长度,这时我引进了一个整型变量,负责记录一次冒泡排序后的交换次数,如果交换次数大于 0,说明链表还需要进行比较,反之就可以直接跳出循环了。

3.代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 链表的冒泡排序
public Node sort(Node head){
// 链表没有元素或者只有一个元素
if(head == null || head.next == null)
return head;

// 创建一个虚拟头结点,便于节点交换,这样子就不需要单独考虑头结点
Node dummyHead = new Node(head, -1);

int num = 0; // 记录交换次数
while( true){
// 用两个变量分别记录当前节点和下一节点
// 然后再用他们的下一节点进行比较
Node currentNode = dummyHead;
Node nextNode = dummyHead.next;
// 跳出条件为下一个节点不存在
while(nextNode.next != null){
// 需要进行交换
if(currentNode.next.data > nextNode.next.data){
// 这个有点难说,需要自己画图
currentNode.next = nextNode.next;
nextNode.next = currentNode.next.next;
currentNode.next.next = nextNode;
currentNode = currentNode.next;
num ++;
}
else{
currentNode = currentNode.next;
nextNode = nextNode.next;
}

}
// 判断是否进行交换
if(num == 0) // 等于 0 说明没有进行交换
break;
else
num = 0; // 归 0 下次再进行交换
}

return dummyHead.next;
}

4. 复杂度分析


  • 时间复杂度 O(n^2):假设最坏情况,比较到最后两个元素还需要进行交换位置,这时外圈循环就是 n - 1 次了,内层永远都是比较到最后一个元素,就是 n。所以时间复杂度为 O(n^2)。就是 n 的平方
  • 空间复杂度 O(1)。