写点什么

三种基本排序

  • 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
用户头像

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

还未添加个人简介

评论

发布
暂无评论
三种基本排序_排序算法_我是一个茶壶_InfoQ写作社区