亲宝软件园·资讯

展开

C语言中数组排序浅析

wsbydmm 人气:0

前言

本文介绍了几种c语言中对乱序数组的排序方式。

具体的内容有:

具体内容详见下文。

一、插入排序

1、思路

首先假设数组的的前n位元素是有序的,然后从第n+1位开始,将此元素插入到前面,使得前n+1位元素有序,以此类推,直至整个数组有序。

在对第n+1位元素操作时,使用临时变量存放该元素的值,从第n位元素开始向前比较,同时将与其比较的元素向后移动,直到与其比较的元素比其小时,将临时变量中的值放入该元素后的一个数组元素中。

2、具体步骤

1.从第一个元素开始,该元素可以认为已经被排序。

2.取下一个元素存入临时变量temp,对前方有序序列从后往前扫描。

3.如果该元素大于temp,则将该元素移到下一位。

4.重复步骤3,直到找到已于等于temp的元素。

5.temp插入到该元素的后面一位,如果所有有序元素都大于temp,则将temp插入到下标为0的位置(既数组的首位,说明该元素是目前最小的元素)。

6.重复以上的2~5步骤,直至操作完整个数组中的所有元素。

3、代码实现

void insertsort(int arr[], int len)
{
	int j;
	for(j=0; j<len-1; j++)
	{
		int end=j;    //前end位为有序部分
		int temp=arr[j+1];    //临时变量存放
		while(end>=0)
		{
			if(arr[end]>temp)    //将temp变量与前面一位元素比较
			{
				arr[end+1]=arr[end];    //将比temp变量大的元素向后移动一位
				end--;    //继续向前比较
			}
			else    //找到比temp变量小的元素
			{
				break;
			}
		}
		arr[end+1]=temp;    //将temp变量插入有序部分
	}
}

4、复杂度

时间复杂度: O(N)~O(N^2)

空间复杂度:O(1)

二、冒泡排序

1、思路

通过对数组内相邻元素的比较,使较大的元素向后移动,较小的元素向前移动,不断循环此过程,直至整个数组有序。

当第n次循环结束后,数组的最后n位为有序,所以每循环一次,就可以将循环的范围(后界)向前减少一位元素。

2、具体步骤

1.将数组中的第一个元素与下一个元素进行比较,若第一个元素较大,则交换位置。

2.继续比较下两个元素的大小,将较大的元素放在靠后的位置。

3.重复步骤2,直至完成第n-1个元素与第n个元素的比较。

4.将循环的后界减一,重复1~5步骤。

5.当循环的范围减为1时,此时的为有序数组。

3、代码实现

void bubblesort(int arr[], int len)
{
	int j,k;    //定义循环因子,嵌套双层循环
	for(j=0; j<len-1; j++)    //设置循环后界
	{
		for(k=0; k<len-j-1; k++)    //不断向后进行比较
		{
			if(arr[k]>arr[k+1])    //比较相邻的元素
			{
				int temp=arr[k];    //三杯水交换法
				arr[k]=arr[k+1];
				arr[k+1]=temp;
			}
		}
	}
}

4、复杂度

时间复杂度: O(N)~O(N^2)

空间复杂度: O(1)

三、选择排序

1、思路

不断扫描数组,每次选出一个最小值和一个最大值,分别放在序列的首位置和末位置,然后将序列的首位置与末位置分别向后与前移动一位。直至排完整个数组。

2、具体步骤

1.定义序列的首末位置。

2.扫描首末位置之间的序列,选出一个最小值min和一个最大值max,记录下标值。

3.将最小值放入首位置start,最大值放入末位置end。

4.将首位置向后移动一位,末位置向前移动一位。

5.重复2~4步骤,直至首末位置重合(start>=end),此时的数组为有序数组。

3、代码实现

void selectsort(int arr[], int len)
{
	int start=0, end=len-1;    //定义首末位置
	while(start<end)
	{
		int max=start;    
		int min=start;
		int j;
		for(j=start; j<=end; j++)    //扫描首末位置之间的序列
		{
			if (arr[j] < arr[min])    //选取最小值
			{
				min = j;    //记录最小值的下标
			}
			if (arr[j] > arr[max])    //选取最大值
			{
				max = j;    //记录最大值的下标
			}
		}
		int temp=arr[min];    //三杯水交换,将最小值放入首位置
		arr[min]=arr[start];
		arr[start]=temp;
		if (start == max)    //防止最大值在首位置被换走
		{
			max = min;
		}
		temp=arr[max];    //三杯水交换,将最大值放入末位置
		arr[max]=arr[end];
		arr[end]=temp;
		start++;    //首位置后移一位
		end--;    //末位置前移一位
	}
}

4、复杂度

时间复杂度: O(N^2)

空间复杂度: O(1)

四、希尔排序

1、思路

定义一个小于数组长度增量,将整个数组中每隔一个增量的元素分为一组,对每组中的元素进行插入排序,再将增量减小,之后重复以上过程,直至增量减小为1时,对已经进行过预处理的数组进行插入排序,达到减小复杂度的目的。

2、具体步骤

1.定义一个小于数组长度的增量gap(通常为数组长度的一半),将数组进行分组。

2.对每组中的元素进行插入排序的操作,使之有序。

3.减小增量gap(通常为减为一半),将数组再度细分。

4.重复2~3步骤,直至增量gap减小为1。

5.此时对整个数组再做插入排序操作,使整个数组有序。

3、代码实现

void shellsort(int arr[], int len)
{
	int gap=len;    //定义增量
	while(gap>1)
	{
		gap=gap/2;    //将增量减小
		int j;
		for(j=0; j<len-gap; j++)    //将数组分组
		{
			int end=j;
			int temp=arr[end+gap];    //对每组元素进行插入排序
			while(end>=0)
			{
				if(arr[end]>temp)
				{
					arr[gap+end]=arr[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap]=temp;
		}
	}
}

4、复杂度

时间复杂度: 平均 O(N^1.3)

空间复杂度: O(1)

具体使用

#include<stdio.h>
void insertsort(int arr[], int len)    //选择排序
{
	int j;
	for(j=0; j<len-1; j++)
	{
		int end=j;
		int temp=arr[j+1];
		while(end>=0)
		{
			if(arr[end]>temp)
			{
				arr[end+1]=arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end+1]=temp;
	}
}
void bubblesort(int arr[], int len)    //冒泡排序
{
	int j,k;
	for(j=0; j<len-1; j++)
	{
		for(k=0; k<len-j-1; k++)
		{
			if(arr[k]>arr[k+1])
			{
				int temp=arr[k];
				arr[k]=arr[k+1];
				arr[k+1]=temp;
			}
		}
	}
}
void shellsort(int arr[], int len)    //希尔排序
{
	int gap=len;
	while(gap>1)
	{
		gap=gap/2;
		int j;
		for(j=0; j<len-gap; j++)
		{
			int end=j;
			int temp=arr[end+gap];
			while(end>=0)
			{
				if(arr[end]>temp)
				{
					arr[gap+end]=arr[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap]=temp;
		}
	}
}
void selectsort(int arr[], int len)    //选择排序
{
	int start=0, end=len-1;
	while(start<end)
	{
		int max=start;
		int min=start;
		int j;
		for(j=start; j<=end; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
			if (arr[j] > arr[max])
			{
				max = j;
			}
		}
		int temp=arr[min];
		arr[min]=arr[start];
		arr[start]=temp;
		if (start == max)
		{
			max = min;
		}
		temp=arr[max];
		arr[max]=arr[end];
		arr[end]=temp;
		start++;
		end--;
	}
}
int main()
{
	int arr[10]={9,8,7,6,5,4,3,2,1,0};    //乱序数组
	int len=sizeof(arr)/4;
	int i;
	for(i=0; i<len; i++)
	{
		printf("%d\t", arr[i]);    //输出初始数组,用于比较
	}
	putchar('\n');
	selectsort(arr, len);    //调用函数对数组进行排序,这里选用的是选择排序的方式
	for(i=0; i<len; i++)
	{
		printf("%d\t", arr[i]);    //输出排完序后的数组
	}
	putchar('\n');
	return 0;
 } 

例题及其解答

题目描述

来源:牛客网

小明平时学习太用功了,闲暇时间就喜欢玩一种数字游戏,在这个游戏中,他每次会使用n个正整数先构造一个数列(x1,……,xn),并可以根据需要无限次执行以下操作:

选择两个不同的i,j,其中xi>xj,然后将xi改为xi-xj。

请你帮小明算一下,通过这样的一系列操作,求出最终处理过数列的总和最小值是多少?

输入描述

第一行一个整数n代表数列的长度,2<=n<=100,

第二行包含n个正整数x1 x2 x3 ... xi, 1<=xi<=100.

输出描述

经过多次操作后,数列总和的最小值(整数)。

示例1

输入

5
45 12 27 30 18

输出

15

示例2

输入

3 2 4 6

3
2 4 6

输出

6

说明

在输出样例2中进行了以下操作:x3 = x3 - x2, x2 = x2 - x1,经过这两步操作后,所有的数字都相等,因此操作不能再进行下去了,每个数都是2,因此6就是总和的最小值。

解答

#include<stdio.h>
void sort(int arr[], int n)    //本题我使用的是冒泡排序,也可使用其他排序方式
{
    int i,j;
    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n-1-i; j++)
        {
            if(arr[j]<arr[j+1])
            {
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);    //输入数列长度
    int arr[n];    //定义相应长度的数组
    int i;
    for(i=0; i<n; i++)
    {
        scanf("%d", &arr[i]);    //将输入的数据存入数组
    }
    while(1)
    {
        sort(arr,n);    //对数组进行排序
        if(arr[0]==arr[n-1])    //判断数组的首末元素是否相等
        {
            break;    //若相等,则无法再进行作差操作
        }
        for(i=0;i<n-1; i++)    //对数组中的相邻且不相等的元素作差
        {
            if(arr[i]>arr[i+1])
            {
                arr[i]=arr[i]-arr[i+1];
            }
        }
    }
    int sum=0;
    for(i=0; i<n; i++)    //对最终的数组进行求和
    {
        sum=sum+arr[i];
    }
    printf("%d\n", sum);    //输出答案
    return 0;
}

结语

以上就是四种数组排序方式的全部内容,以及在例题中的应用。

加载全部内容

相关教程
猜你喜欢
用户评论