前言
本文介绍了几种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;
}结语
以上就是四种数组排序方式的全部内容，以及在例题中的应用。
文章出处登录后可见！
