双向冒泡排序是一种对于冒泡排序的优化,虽然时间复杂度没有改进,但是整体上是对冒泡排序的改进。
最近某些考试中出现了基于双向链表的双向冒泡排序,故学习一下,并在这里给出具体实现。
思路:
冒泡排序是一种基于比较的排序方法,以从小到大排序为例。
每一轮排序,会将最大的元素冒泡到序列的最后。但是有些情况下,最大的元素已经位于序列末尾,那么这一轮的比较就是一种浪费,如何将这部分多余的轮次优化掉是需要解决的。
如数组:a = [3, 2, 1, 4, 9, 7, 8]
第一轮:a = [2, 1, 3, 4, 7, 8, 9]
第二轮:a = [1, 2, 3, 4, 7, 8, 9]
第三轮:a = [1, 2, 3, 4, 7, 8, 9]
第四轮:a = [1, 2, 3, 4, 7, 8, 9]
第五轮:a = [1, 2, 3, 4, 7, 8, 9]
第六轮:a = [1, 2, 3, 4, 7, 8, 9]
在第二轮结束后,整个数组就已经有序了,第三轮到第六轮都是多余的。
在第一轮结束后,a[3~7]
已经有序,之后这部分就不用再排序了
我们需要有一个标记 R = 2
,去记录 a[R+1~7]
的元素都已经有序
在第二轮结束后,a[1~2]
已经有序,之后这部分就不用再排序了
我们需要有一个标记 L = 3
,去记录 a[1~L-1]
的元素都已经有序
这里就用到了双向冒泡排序,上述的 $R$ 用来记录之后还需要对 a[1~R]
排序,上述的 $L$ 用来记录之后还需要对 a[L~n]
排序,结合一下即之后还需要对 a[L~R]
排序。
代码:
下面的代码给出了双向数组和双向链表两种版本的双向冒泡排序,
由于双向链表排序中对于链表结点交换的部分较为复杂,因此采用临时变量作为中介进行交换。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
void cocktail_sort_array(int a[], int l, int r) {
int bottom = l, top = r;
int found = 1;
int bound;
while (found) {
found = 0;
// 从前往后找,这样保证结束时最大的会到达top
for (int i = bottom; i < top; ++i) {
if (a[i + 1] < a[i]) {
swap(a[i + 1], a[i]);
found = 1;
bound = i;
}
}
top = bound;
// 从后往前找,这样保证结束时最大的会到达bottom
for (int i = top; i > bottom; --i) {
if (a[i] < a[i - 1]) {
swap(a[i], a[i - 1]);
found = 1;
bound = i;
}
}
bottom = bound;
}
}
struct ListNode {
int val;
ListNode* prev;
ListNode* next;
ListNode(int _val): val(_val), prev(nullptr), next(nullptr) {}
};
ListNode* nodes[1010];
void output(ListNode* p) {
while (p != nullptr && p->val != -1) printf("%d ", p->val), p = p->next;
printf("\n");
}
void cocktail_sort_linklist(ListNode* _head, int l, int r) {
// 带头结点
ListNode* thead = _head;
ListNode* head = _head;
ListNode* tail = _head;
while (l > 0) head = head->next, l -= 1;
while (r >= -1) tail = tail->next, r -= 1;
ListNode* bound = nullptr;
int found = 1;
while (found) {
// output(_head->next);
found = 0;
ListNode* p = head->next;
while (p->next != tail) {
if (p->val > p->next->val) {
found = 1;
// 找到相关的四个结点
ListNode* A = p->prev;
ListNode* B = p->next;
ListNode* C = p;
ListNode* D = B->next;
A->next = B;
B->prev = A;
B->next = C;
C->prev = B;
C->next = D;
D->prev = C;
p = C;
bound = B;
} else {
p = p->next;
}
}
if (bound == nullptr) break;
tail = bound->next;
p = tail;
while (p->prev != head) {
if (p->prev->val > p->val) {
found = 1;
// 找到相关的四个结点
ListNode* A = p->prev->prev;
ListNode* B = p;
ListNode* C = p->prev;
ListNode* D = B->next;
A->next = B;
B->prev = A;
B->next = C;
C->prev = B;
C->next = D;
D->prev = C;
p = B;
bound = C;
} else {
p = p->prev;
}
}
head = bound->prev;
}
}
int main()
{
int n, l, r;
scanf("%d%d%d", &n, &l, &r);
ListNode* head = new ListNode(-1);
ListNode* tail = new ListNode(-1);
ListNode* temp = head;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
nodes[i] = new ListNode(a[i]);
}
tail->prev = nodes[n - 1];
nodes[n - 1]->next = tail;
nodes[0]->prev = head;
head->next = nodes[0];
for (int i = 0; i + 1 < n; ++i) nodes[i]->next = nodes[i + 1];
for (int i = n - 1; i > 0; --i) nodes[i]->prev = nodes[i - 1];
cocktail_sort_linklist(head, l, r);
ListNode* p = head->next;
for (int i = 0; i < n; ++i) {
printf("%d%c", p->val, " \n"[i + 1 == n]);
p = p->next;
}
return 0;
}
提交测试题目:
AcWing 818. 数组排序