C语言---插入排序、希尔排序、冒泡排序、选择排序、快速排序简单介绍
文章目录
- 插入排序
- 希尔排序
- 冒泡排序
- 选择排序
- 快速排序
本文主要介绍用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]; //前面的值比当前值大，向后移动elsebreak; //找到了当前值该插入的位置}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的值elsebreak;}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语言实现插入排序、希尔排序、冒泡排序、选择排序和快速排序的所有内容了！