在单链表上执行气泡排序，C ++解决方案

要执行气泡排序，请按照以下步骤操作：

第1步： 检查两个相邻节点上的数据是否按升序排列。如果不是，请交换2个相邻节点的数据。

第2步： 在通道1的末尾，最大的元素将在列表的末尾。在2^nd pass 2^nd 最大的元素将处于其位置。

第三步： 当所有元素都启动时，我们终止循环。

C ++解决方案

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
	int data;
	Node *next;

	Node(int x)
	{
		data = x;
		next = NULL;
	}
};

void print_list(Node *head)
{
	Node *start = head;

	while(start)
	{
		cout<<start->data<<" -> ";
		start = start->next;
	}
	cout<<"\n\n";
}

void my_swap (Node *node_1, Node *node_2)
{
	int temp = node_1->data;
	node_1->data = node_2 -> data;
	node_2 -> data = temp;
}

void bubble_sort(Node *head)
{
	int swapped;

	Node *lPtr; // left pointer will always point to the start of the list
	Node *rPrt = NULL; // right pointer will always point to the end of the list
	do
	{	
		swapped = 0;
		lPtr = head;
		while(lPtr->next != rPrt)
		{
			if (lPtr->data > lPtr->next->data) 
			{
				my_swap(lPtr, lPtr->next); 
                swapped = 1; 
			}
			lPtr = lPtr->next;
		}
		//as the largest element is at the end of the list, assign that to rPtr as there is no need to
		//check already sorted list
		rPrt = lPtr;

	}while(swapped);
}

int main()
{
	Node *head = new Node(2);
	head -> next = new Node(1);
	head -> next -> next = new Node(4);
	head -> next -> next -> next = new Node(3);
	head -> next -> next -> next  -> next = new Node(6);
	head -> next -> next -> next  -> next -> next = new Node(5);

	cout<<"The original list = "<<endl;
	print_list(head);


	bubble_sort(head);

	cout<<"The Sorted list = "<<endl;
	print_list(head);

	return 0;
}

输出：

The original list =
2 -> 1 -> 4 -> 3 -> 6 -> 5 ->

The Sorted list =
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->

该网站上可用的教程列表：