三种基本排序

2022-11-30
河南
本文字数：1122 字
阅读完需：约 4 分钟

选择排序：数据中有序子序列是 0...i-1,无序子序列是 i...n-1,从无序子序列中选择一个最小值并记录其下标，然后将此最小值单元和第 i 个单元交换，使得有序部分变长为 0...i 单元，依次重复此过程直至整个序列有序。

核心思想：从未排好的部分的第一个作为最小（最大）的，然后依次和剩余的比较，如果有更小（更大）的，记下下标，以此作为新的最小（最大）值，继续比较，一趟结束后，然后和第一个进行交换。

例题 1. 给定一个数组，并对这些数据从小到大进行排序，要求使用选择排序完成。

#include<stdio.h>int main(){    int i,j,t,n=10;    int a[10]={100，34，12，23，34，35，56}；    for(i=0;i<=n-2;i++)    {      k=i;      for(j=i+1;j<=n-1;j++)       if(a[j]<a[k])         k=j;      if(k!=i)      {      t=a[i];       a[i]=a[j];      a[j]=t;      }      for(i=0;i<n;i++)      printf("%d",a[i]);      return 0;}

复制代码

插入排序：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。核心思想：假设第一个元素排好，之后的元素对排好的部分从后面比较并逐一移动。

例题：请输入 n 和 n 个整数，并对这些数据从小到大进行排序，要求使用插入排序完成。

#include<stdio.h>int main(){	int n,a[100],i,j,x;	scanf("%d",&n);	for(i=0;i<n;i++)	{		scanf("%d",&a[i]);	}	for(i=1;i<n;i++)	{		x=a[i]; 		for(j=i-1;a[j]>x&&j>=0;j--) 		{			a[j+1]=a[j];			a[j]=x;		}	}	for(i=0;i<n;i++)	{		printf("%d ",a[i]);	}	return 0; }

复制代码

冒泡排序：比较相邻的元素，如果第一个比第二个大，就交换他们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对；这步做完后，最后的元素会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。这样会使有序序列在后边而无序序列在前边，一趟冒泡只可产生一个最大值，因此需要进行 n-1 趟冒泡。此处 i 仅用于控制冒泡次数不再表示数组下标，核心点在于要使内循环保证相邻的数据两两比较交换，共进行 n-i 次的比较和交换。

例题：请输入 n 和 n 个整数，要求按照这些数据的个位从小到大进行排序，如果个位相等则按照十位从小到大排序,使用冒泡排序。

#include<stdio.h>int main(){	int a[20]={123,53,80,66,246,78,45,26};	int n=8,i,j,t;	for(i=1;i<n;i++)	{		for(j=0;j<n-i;j++)		{			if((a[j]%10>a[j+1]%10)||(a[j]%10==a[j+1]%10)&&(a[j]/10%10>a[j+1]/10%10))			{				t=a[j];				a[j]=a[j+1];				a[j+1]=t;			 } 		}	}	for(i=0;i<n;i++)	{		printf("%d ",a[i]);	}	return 0;}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/9a5a89483e3a04a988ddd4a8e】。未经作者许可，禁止转载。

我是一个茶壶

关注

还未添加个人签名 2022-11-01 加入

还未添加个人简介

发布

暂无评论

创作场景

三种基本排序

我是一个茶壶

评论