1、冒泡排序
数组存储：
输入：输入长度为N的整型数组arr
输出：输出arr冒泡排序后的升序序列
优化目标：提高效率
#include <stdio.h>
void BubbleSort(int arr[],int len){int i,j;for(i=0;i<len-1;i++){//一共n-1轮 int flag=0; for(j=n-1;j>i;j--){ if(arr[j-1]>arr[j]){ //前一个比后一个大int temp;temp=arr[j-1];arr[j-1]=arr[j];arr[j]=temp; //交换两个数据flag=1;} }if(flag==0){break;//若本轮没发生交换，说明已经有序}}}
int main(){int N,arr[100]={0};scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d", &arr[i]);}BubbleSort(arr,N);for(int j=0; j<N; j++) {printf("%d ",arr[j]);}}
链表存储：
输入：输入多个整型数创造链表L
输出：输出L冒泡排序后的升序序列
优化目标：提高效率
#include <stdio.h>
#include <stdlib.h>
struct ListNode {int data;struct ListNode *next;
};void BubbleSort(struct ListNode *L)
{int flag;struct ListNode *count=L;struct ListNode *tail=NULL;while(tail!=L){struct ListNode *cur=L;flag=0;for(;cur->next!=tail;cur=cur->next){//cur每轮最终位置在tail之前if(cur->data>cur->next-> data){flag=1;int temp;temp=cur->data;cur->data=cur->next->data;cur->next->data=temp; //交换}}tail=cur;//tail往前if (flag==0)//若没发生交换，则排序完成{return;}}}struct ListNode* readlist()//创建链表
{struct ListNode *head=NULL,*tail=NULL,*p=NULL;int data;scanf("%d", &data);while (data!=-1){p=(struct ListNode*)malloc(sizeof(struct ListNode));p->data=data;p->next=NULL;if (head==NULL)head=p;elsetail->next=p;tail=p;scanf("%d", &data);}return head;
}void printlist(struct ListNode *L )//打印链表
{struct ListNode *p=L;while (p) {printf("%d ", p->data);p=p->next;}printf("\n");
}int main()
{int m;struct ListNode *L=readlist();printlist(L);BubbleSort(L);printlist(L);return 0;
}
2、简单选择排序
数组存储：
输入：输入长度为N的整型数组arr
输出：输出arr选择排序后的升序序列
优化目标：无
#include <stdio.h>
void SelectSort(int arr[],int len){int i,j;for(i=0;i<len-1;i++){//一共n-1趟int min=i; //初始化for(j=i+1;j<len;j++){if(arr[min]>arr[j]){ //找到最小值的下标min=j; } }if(min!=i){ int temp;temp=arr[min];arr[min]=arr[i];arr[i]=temp; //交换两个数据}}
int main(){int N,arr[100]={0};scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d", &arr[i]);}SelectSort(arr,N);for(int j=0; j<N; j++) {printf("%d ",arr[j]);}}
链表存储：
输入：输入多个整型数创造链表L
输出：输出L选择排序后的升序序列
优化目标：无
#include <stdio.h>
#include <stdlib.h>
struct ListNode {int data;struct ListNode *next;
};void selectsort(struct ListNode *L)
{struct ListNode *i=L;struct ListNode *min,*j;int temp;for(;i->next!=NULL;i=i->next){//依次遍历，直到倒数第二个结点min=i;//记录当前结点for(j=i->next;j!=NULL;j=j->next){//找到本次最小值结点if(min->data>j->data){min=j;//有更小的则更新指针}}if(min!=i){temp=min->data;min->data=i->data;i->data=temp;}}
}
struct ListNode* readlist()//创建链表
{struct ListNode *head=NULL,*tail=NULL,*p=NULL;int data;scanf("%d", &data);while (data!=-1){p=(struct ListNode*)malloc(sizeof(struct ListNode));p->data=data;p->next=NULL;if (head==NULL)head=p;elsetail->next=p;tail=p;scanf("%d", &data);}return head;
}
void printlist(struct ListNode *L )//打印链表
{struct ListNode *p=L;while (p) {printf("%d ", p->data);p=p->next;}printf("\n");
}
int main()
{int m;struct ListNode *L=readlist();printlist(L);selectsort(L);printlist(L);return 0;
}
总结：今天复习了冒泡排序和简单选择排序在数组上和链表上的操作，加深了印象。
