数组冒泡排序

冒泡排序的原理

从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

举例

假如有一堆数据：

进行第一轮比较

第一次：80与31比较，80 > 31，交换

第二次:80与-4比较，80 > -4，交换

第三次:80与36比较，80 > 36，交换

第四次:80与-8比较，80 > -8，交换

此时，第一轮结束，最大值80已经到了最右边，一共进行了四次比较

第二轮比较 （下面就不添加图片了）

第一次：31与-4比较，31 > -4，交换：-4 31 36 -8 80
第二次:31与36比较，31 < 36，不交换: -4 31 36 -8 80
第三次：36与-8比较，36 > -8, 交换：-4 31 -8 36 80
80已经排序好，所以不用比较

经过第二轮，数据为

第三轮比较

第一次:-4与31比较，-4 < 31，不交换：-4 31 -8 36 80
第二次：31与-8比较，31 > -8，交换: -4 -8 31 36 80
36、80已经排序好，所以不用比较

经过第三轮，数据为：

第四轮比较

第一次：-4与-8比较，-4 > -8,交换：-8 -4 31 36 80

由上面四轮比较此数据已经排序完成，可以得出结论：假设一个数组长为n，则需要进行n-1轮比较，并且只有第一轮比较全部

代码如下

void Sort(int arr[])
{
int i,j;

for (i=1;i<size;i++)
{
	for (j=0;j<size-i;j++)
	{
		if (arr[j] > arr[j+1])
		{
			int temp = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = temp;
		}
	}
//下面代码可以看到排序过程	
/*	printf("\n");
	for (int i=0;i<size;i++)
		printf("%d ",arr[i]);
	printf("\n");
	printf("\n");
*/
}

}

size为数组的长度

单链表冒泡排序

假如有一个链表，数据如下：

但数组存储方式是连续的，容易操作，而链表存储方式非连续，所以操作起来会比较麻烦，下面我说一下我的思路

链表实现：

令 t = Head_Node->next

第一轮
父循环从Head_Node->next->next开始，一直到不等于tail

子循环从t开始一直到t->next不等于tail

此过程可以用t->data与t->neaxt->data来进行两两相互比较，最后t会指向tail的前面，于是可以减小父循环与子循环tail = t

经过第一轮比较，最大值80移到到了最右端，并且减小了循环次数

第二轮
父循环从Head_Node->next->next开始，一直到不等于tail,也即执行了m-2次

子循环从t开始一直到t->next不等于tail

此过程可以用t->data与t->neaxt->data来进行两两相互比较，最后t会指向tail的前面，于是可以减小父循环与子循环tail = t

经过第二轮比较，36移到到了右端，并减小循环次数

第三轮
父循环从Head_Node->next->next开始，一直到不等于tail

子循环从t开始一直到t->next不等于tail

此过程可以用t->data与t->neaxt->data来进行两两相互比较，最后t会指向tail的前面，于是可以减小父循环与子循环tail = t

经过第三轮比较，31移到到了右端，并减小循环次数

第四轮

父循环从Head_Node->next->next开始，一直到不等于tail

子循环从t开始一直到t->next不等于tail

此过程可以用t->data与t->neaxt->data来进行两两相互比较，最后t会指向tail的前面，于是可以减小父循环与子循环tail = t

经过第四轮比较，-4移到到了右端，并减小循环次数

至此，冒泡排序全过程已经结束，一共执行了四轮，同样满足：n个数据进行n-1轮比较。

代码如下

节点
typedef struct Node
{
int data;
struct Node* next;
}LNODE,*LPNODE;

冒泡算法
void Sort(LPNODE Head_Node)
{
LPNODE r,t,tail;
tail = NULL;

while (Head_Node->next->next != tail)
{
	r = Head_Node;
	t = Head_Node->next;

	while (t->next != tail)
	{
		if (t->data > t->next->data)
		{
			r->next = t->next;
			t->next = t->next->next;
			r->next->next = t;
			t = r->next;
		}
		r = r->next;
		t = t->next;
	}
	tail = t;
}

}