链表排序问题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

链表与数组一样也有许多排序方式
今天介绍链表的插入排序。

冒泡排序

1.思想

在数组中冒泡排序之所以容易实现的原因在于： 数组中数据在内存中的存储是连续的，并且通过下标的改变就可以轻松改变指针所指的地址

但在链表中，每个节点在内存中的位置是不确定的，所以不容易改变指针所指地址，来重复对链表内相邻节点的数据进行比较。

2.代码

数组

void bubble(int a[],int len)
{
	int i,j,t;
	for(i = 0; i < len; i++)
	{
		for(j = 0; j < len - i -1; j++)
		{
			if(a[j] > a[j + 1])
			{
				t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}                                                                     
	}
} 

链表

struct listnode* bubblesort(struct listnode *head)
{
	if(head == NULL)
	return head; 
	struct listnode *p,*q,*dummyhead;
	int temp;
	dummyhead = (struct listnode*)malloc(sizeof(struct listnode));
	dummyhead->data = NULL;
	dummyhead->next = head;
	p = dummyhead;//p为冒牌中的交换趟数 
	q = head;
	while(p != NULL)
	{
		q = head;//每次q都应该重新回到最初点 
		while(q->next != NULL)
		{
			if(q->data > q->next->data)//冒泡里的交换 
			{
				temp = q->data;
				q->data = q->next->data;
				q->next->data = temp;
			}
			q = q->next;
		}
		p = p->next;
	}
	return dummyhead->next;
}

插入排序

1.思想

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 11，直到全部元素都加入到有序序列中

如果是数组的插入排序，则数组的前面部分是有序序列，每次找到有序序列后面的第一个元素（待插入元素）的插入位置，将有序序列中的插入位置后面的元素都往后移动一位，然后将待插入元素置于插入位置。

对于链表而言，插入元素时只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动。

对于单向链表而言，只有指向后一个节点的指针，因此需要从链表的头节点开始往后遍历链表中的节点，寻找插入位置。

2.代码

数组插入排序

代码如下（示例）：

void insert(int arr[],int len)
{
	int i,j,temp;
	for(i = 1; i < len; i++)
	{
		temp = arr[i]; 
		for(j = i - 1; j >= 0 && arr[j] > temp; j--)//找到比前一个大的值 
		{
			arr[j + 1] = arr[j];//将数组往后移一位 
		}
		arr[j + 1] = temp;//将temp储存的值赋予 
	}
}

链表代码

struct listnode *insertsort(struct listnode *head)
{
	if(head == NULL) return head;//链表为空 
	struct listnode* phead;//一个记录头结点的结点 
	phead = (struct listnode*)malloc(sizeof(struct listnode));
	phead->data = 0;
	phead->next = head;
	struct listnode *p,*q;
	p = head;
	q = p->next;
	while(q != NULL)
	{
		if(p->data <= q->data)
		{
			p = p->next;
		}
		else
		{
			struct listnode* pre;
			pre = phead;
			while(pre->next->data <= q->data)//找到要插入位置的前一个结点 
			{
				pre = pre->next;
			} 
			p->next = q->next;
			q->next = pre->next;
			pre->next = q;//插入结点                                              
		}
		q = p->next;
	}
	return phead->next;
	//return head;
}

总结

学习了一下链表排序问题

1 一维数组

2 冒泡的概念

3 代码实现

1一维数组

一维数组 ：存放字符型数据的数组

一维数组的定义

首先 定义int arr[5](int类型的一维数组 )， 5 是数组的长度 也就是大小 但是我们 在访问数组元素的地址 时候， 不存在 有 arr[5]

也就是说 定义arr[5]只是 为了 让你知道这个数组大小是 5 而已    我们在访问 数组的元素地址时候  是用下标来访问的 （从0开始 ）  上述的两种定义的方法 都可以适用 在我们的元素长度和数组大小对不上时 他们自动补充 元素  我们有个这些概念之后  后面讲到的理解起来 都不会很吃力

2 冒泡 的概念

 拿图中的五个数相比较   只要满足 前<后   我们就可以进行 交换  也就是 用下标法来比较   

我们可以得出 我们拿五个数比较 第一轮 比较四次 得出 最大值  除去最大值 就是第二轮要比较的数   第二轮就是要比较 （比较的数量-1）就可以得本轮的最大值   其实第五轮 是没有比较的 因为只有一个数 （只是为了更直观 看到  全部 ）

3 代码实现 

计算 数组大小的 关键字   sizeof  

计算公式 

 int  len=sizeof(arr)/sizeof(arr[0]);

  函数声明

    void scan(int arr[],int len);
    void MaoPao(int arr[],int len);
    void print(int arr[],int len);

函数声明 只是为了 养成 良好的 编程习惯  

 输入函数 

//输入函数
    void scan(int arr[],int len)
    {
     for(int i=0;i<len;i++)
     {
     scanf("%d",arr+i);//输入五位数
     }

因为 数组名就是 入口 地址  所以 我不用常规的方式 来写  输入函数    其实都一样的 

冒泡排序 

     //冒泡 排序 函数
    void MaoPao(int arr[],int len)
    {

     int temp;

     for(int i=0;i<len-1;i++)
       {

     for(int j=0;j<len-i-1;j++)
     {
         if(arr[j]<arr[j+1])//满足条件 交换 到了下一次  并且 相应改变 位置
         {
             temp=arr[j]; //开始交换 
             arr[j]=arr[j+1];
             arr[j+1]=temp;


         }

     }

       }

    }

 i 是轮次 我拿了 五个 数 可以发现 我只用了 四轮 就完成了 大小排序    

j是 比较的次数  第一轮  用了 四次 （最开始有五个数 ）所以 要 长度-1-i 

如果 不减i的话 会导致  每一轮的比较次数都是一样的  这个要特别注意 

输出 函数 

  
    void print(int arr[],int len)
    {
    printf("大小排序是：\n");
    for(int i=0;i<len;i++)
     {
      printf(" %d",*(arr+i));

     }

    }

这里再说一次  输入 和输出 能用 arr+i 和 *（arr+i） 写的原因   常规写法 应该分别是 &arr[I] 和 arr[i]       我们这里要知道一个概念  数组名就是数组 的入口地址（首地址）

主函数 的 调用 

void main(void)//无参主函数 
    {
    int arr[5];
    int len;
    len=sizeof(arr)/sizeof(arr[0]);//计算数组大小

    scan(arr,len);//输入 
    MaoPao(arr,len);//排序
    print(arr,len);//输出 

    }

最后结果

           冲冲冲冲冲冲 ！！！！！！！！！！！！！！！！！！！！！！！！

                                               最 后 感 谢 大 家 的 阅 读  

冒泡排序

对一个元素个数为20个的随机数组进行冒泡排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
}

void Display(int *a, int n){
	for (register int i = 0; i < n; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
}

void bubble_sort(int *a, int n){
	register int i, j;
	int flag;
	//最多排序n-1次
	for (i = 0; i < n - 1; i++){
		flag = 0;
		//每排序一次，都会有一个元素放在了正确的位置，所以j<n-i-1
		for (j = 0; j < n - i - 1; j++){
			if (a[j] > a[j + 1]){
				swap(a[j], a[j + 1]);
				flag = 1;
			}
		}
		printf("第%d次冒泡排序后:", i + 1);
		Display(a, n);
		if (flag == 0) return;//如果一次交换都没有，则说明数组已经排好序，返回;
	}
}

int main(){
	int a[20];
	//生成一个有20个元素的随机数组
	srand((unsigned int)time(0));//修改种子
	for (register int i = 0; i < 20; i++){	
		a[i] = rand();
	}
	printf("原数组为：\n");
	Display(a, 20);
	printf("\n");
	bubble_sort(a, 20);
	printf("\n冒泡排序后：\n");
	Display(a, 20);
	return 0;
}

如有不足，欢迎各位大佬指正