文章目录
- 插入排序
- 希尔排序
- 冒泡排序
- 选择排序
- 快速排序
本文主要介绍用C语言实现的一些排序方法，有插入排序、希尔排序、冒泡排序、选择排序和快速排序，文章中给出的例子都是按照升序排列的。
插入排序
若数组只有一个元素，自然不用排序，插入排序从数组的第二个元素开始，先将当前的元素存起来，然后将它和前面的元素依次比较，大于它的元素依次向后移动，直到找到小于或等于它的元素，将存放的这个元素赋值给经过比较找到的数组位置中，就完成了一次插入排序，每完成一次插入排序，前面的(n+1)个数就已经是顺序的了，其中n为当前完成插入排序的次数。让一个有n个元素的数组顺序排列，需要n-1次插入排序。
插入排序的完整代码如下。
#include <stdio.h>
#include <stdlib.h>
void print_array(int *a,int n)
{
int i;
for (i=0; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void InsertSort(int *a,int n)
{
int i,j,temp;
if(n==1)
{
printf("After InsertSort array : \n");
print_array(a,n);
}
for(i=1;i<n;i++)
{
temp = a[i]; //保存当前值
for(j=i-1;j>=0;j--)
{
if(a[j] > temp)
a[j+1] = a[j]; //前面的值比当前值大，向后移动
else
break; //找到了当前值该插入的位置
}
a[j+1] = temp; //将当前值插入在找到的位置
printf("After %d InsertSort array : ",i);
print_array(a,n);
if(i==n-1)
{
printf("After InsertSort array : \n");
print_array(a,n);
}
}
}
void main()
{
int n,i;
int *a;
printf("Please input the number of the integer : ");
scanf("%d",&n);
a = (int*)malloc(n*sizeof(int));
printf("Please input %d integer numbers : \n",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("Original array : \n");
print_array(a,n);
InsertSort(a,n);
}
运行结果如下图所示。
希尔排序
希尔排序是比较特殊的插入排序，上面提到的插入排序每次的步长为1，希尔排序是将待排序列分为若干个子序列，对这些子序列分别进行插入排序，初始的步长是要排列元素数量的一半（取整），之后每次折半，最后一次排序是步长为1的插入排序。
希尔排序的完整代码如下。
#include <stdio.h>
#include <stdlib.h>
void print_array(int *a,int n)
{
int i;
for (i=0; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void ShellSort(int *a,int n)
{
int i,j,k,temp,gap;
if(n==1) //数组只有一个元素
{
printf("After ShellSort array : \n");
print_array(a,n);
}
gap = n/2; //初始值为数组长度的一半取整
while(gap > 0) //退出循环的条件是 gap = 0
{
for(i=0;i<gap;i++) //i为每组第一个元素的下标
{
for(j=gap+i;j<n;j+=gap) //j的初始值为每组第二个元素的下标
{
temp = a[j]; //保存需要插入的值
for(k=j-gap;k>=0;k-=gap) //从j的前一个元素j-gap开始比
{
if(a[k]>temp)
a[k+gap] = a[k]; //注意gap的值
else
break;
}
a[k+gap] = temp; //插入到指定位置
}
}
printf("After gap=%d ShellSort array : ",gap);
print_array(a,n);
gap = gap/2; //gap的值在每次过后减半
}
printf("After ShellSort array : \n");
print_array(a,n);
}
void main()
{
int n,i;
int *a;
printf("Please input the number of the integer : ");
scanf("%d",&n);
a = (int*)malloc(n*sizeof(int));
printf("Please input %d integer numbers : \n",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("Original array : \n");
print_array(a,n);
ShellSort(a,n);
}
运行结果如下图所示。
冒泡排序
冒泡排序相对比较简单，每趟冒泡排序从头开始，相邻两元素比大小，前面的元素比后面的元素大就交换，否则不交换继续往后比较，可以控制循环不用从头比较到尾，因为每经过一趟冒泡排序，所剩下元素中最大的数会被移动到数组末端，后面序列是有序的。
冒泡排序的完整代码如下。
#include <stdio.h>
#include <stdlib.h>
void print_array(int *a,int n)
{
int i;
for (i=0; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void BubbleSort(int *a,int n)
{
int i,j,temp;
if(n==1) //数组只有一个元素
{
printf("After BubbleSort array : \n");
print_array(a,n);
}
for(i=0;i<n-1;i++) //外层循环执行次数比元素个数小1
{
for(j=0;j<n-i-1;j++) //内层循环每次执行的次数跟i值有关
{
if(a[j]>a[j+1]) //相邻元素做比较，根据比较结果决定交换与否
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
printf("After %d BubbleSort array : ",i+1);
print_array(a,n);
}
printf("After BubbleSort array : \n");
print_array(a,n);
}
void main()
{
int n,i;
int *a;
printf("Please input the number of the integer : ");
scanf("%d",&n);
a = (int*)malloc(n*sizeof(int));
printf("Please input %d integer numbers : \n",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("Original array : \n");
print_array(a,n);
BubbleSort(a,n);
}
运行结果如下图所示。
选择排序
选择排序就是在每一趟排序中找到剩余元素中的最小值，然后将其与数组中第n个元素(第n趟排序就是第n个元素)进行交换(如果最小的是自己，不用交换)，为了优化，可以在一次循环中同时找到最大值和最小值分别交换，这样只需执行元素数量的一半即可完成最终排序。
选择排序的完整代码如下。
#include <stdio.h>
#include <stdlib.h>
void print_array(int *a,int n)
{
int i;
for (i=0; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void SelectSort(int *a,int n)
{
int i,j,k,min;
if(n==1) //数组只有一个元素
{
printf("After SelectSort array : \n");
print_array(a,n);
}
for(i=0;i<n-1;i++) //外层循环执行次数比元素个数小1
{
k = i;
min = a[i]; //选定当前值为最小值
for(j=i+1;j<n;j++) //内层循环每次执行的次数跟i值有关
{
if(a[j]<min) //找出最小值的下标
{
min = a[j]; //更新当前最小值
k = j; //记录下标
}
}
if(k != i) //当前元素不是最小值，交换
{
a[k] = a[i];
a[i] = min;
}
printf("After %d SelectSort array : ",i+1);
print_array(a,n);
}
printf("After SelectSort array : \n");
print_array(a,n);
}
void main()
{
int n,i;
int *a;
printf("Please input the number of the integer : ");
scanf("%d",&n);
a = (int*)malloc(n*sizeof(int));
printf("Please input %d integer numbers : \n",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("Original array : \n");
print_array(a,n);
SelectSort(a,n);
}
运行结果如下图所示。
在一趟排序中同时找出最大值和最小值进行替换，这种情况下一定要注意，如果最大值出现在当前最小值将要存放的位置，如果你先交换了最小值，那么在交换最大值时就会出现问题，一定要在代码中进行判断，如果最大值出现在当前最小值将要存放的位置，那么在先交换了最小值后，在交换最大值时需要和交换最小值的那个位置进行交换。
同时找出最大值和最小值的选择排序的完整代码如下。
#include <stdio.h>
#include <stdlib.h>
void print_array(int *a,int n)
{
int i;
for (i=0; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void SelectSort(int *a,int n)
{
int i,j,k,l,min,max;
if(n==1) //数组只有一个元素
{
printf("After SelectSort array : \n");
print_array(a,n);
}
for(i=0;i<n/2;i++) //外层循环执行次数是元素个数的一半
{
k = i;
l = n-i-1;
min = a[i]; //选定最小值
max = a[n-i-1]; //选定最大值
for(j=i;j<n-i;j++) //内层循环每次执行的次数跟i值有关
{
if(a[j]<min) //找出最小值的下标
{
min = a[j]; //更新当前最小值
k = j; //记录下标
}
else if(a[j]>max)
{
max = a[j];
l = j;
}
}
if(k != i)
{
a[k] = a[i];
a[i] = min;
}
if(l != n-i-1)
{
if(l != i)
{
a[l] = a[n-i-1];
a[n-i-1] = max;
}
else //最大值位置已经被最小值填充，找到最大值被交换的位置再交换
{
a[k] = a[n-i-1];
a[n-i-1] = max;
}
}
printf("After %d SelectSort array : ",i+1);
print_array(a,n);
}
printf("After SelectSort array : \n");
print_array(a,n);
}
void main()
{
int n,i;
int *a;
printf("Please input the number of the integer : ");
scanf("%d",&n);
a = (int*)malloc(n*sizeof(int));
printf("Please input %d integer numbers : \n",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("Original array : \n");
print_array(a,n);
SelectSort(a,n);
}
运行结果如下图所示。
快速排序
快速排序需要选择一个基准值key，一般选择最左边的，定义两个下标值，一个是最左边值的一个是最右边值的下标low和high，每次开始的时候，high先往左边移动，遇到比key值小的就停下，然后low开始往右边移动，遇到比key值大的就停下，此时，如果low<high，就交换low和high下标对应的值，然后依然是high先移动，low后移动，当low=high时，将这个位置的值和key值进行交换。交换完成后，key值左边的值都已经比它小，右边的值都比它大，然后在左右两边再选择基准值递归。注意，在移动时，先移动的是远离key值的那个下标值。
快速排序的完整代码如下。
#include <stdio.h>
#include <stdlib.h>
int n,count = 1;
void print_array(int *a,int n)
{
int i;
for (i=0; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void QuickSort(int *a,int low,int high)
{
int key,temp;
int start,end;
if(low>=high) //涉及递归，根据low和high的关系决定是否执行下面的代码
return;
start = low; //记录起始位置
end = high;
key = a[low]; //基准值设定
while(low < high)
{
while(low < high && a[high] >= key) //一定是大于等于
high--;
while(low < high && a[low] <= key) //一定是小于等于
low++;
//low<high时交换low和high对应的值
temp = a[high];
a[high] = a[low];
a[low] = temp;
}
//退出循环即low=high,交换其与key的值
temp = a[high];
a[high] = key;
a[start] = temp;
printf("After %d QuickSort array : ",count);
print_array(a,n);
count++;
QuickSort(a,start,low-1); //一分为二进行递归
QuickSort(a,low+1,end);
}
void main()
{
int i;
int *a;
printf("Please input the number of the integer : ");
scanf("%d",&n);
a = (int*)malloc(n*sizeof(int));
printf("Please input %d integer numbers : \n",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("Original array : \n");
print_array(a,n);
QuickSort(a,0,n-1);
printf("After QuickSort array : \n");
print_array(a,n);
}
运行结果如下图所示。
以上就是用C语言实现插入排序、希尔排序、冒泡排序、选择排序和快速排序的所有内容了！
