C语言数据结构经典10大排序算法实例分析

今天小编给大家分享一下C语言数据结构经典10大排序算法实例分析的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

1、冒泡排序

// 冒泡排序#include #include // 采用两层循环实现的方法。// 参数arr是待排序数组的首地址，len是数组元素的个数。void bubblesort1(int *arr,unsigned int len){  if (len<2) return; // 数组小于2个元素不需要排序。  int ii;    // 排序的趟数的计数器。  int jj;    // 每趟排序的元素位置计数器。  int itmp;  // 比较两个元素大小时交换位置用到的临时变量。  // 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48    for (ii=len-1;ii>0;ii--)  // 一共进行len-1趟比较。  {    for (jj=0;jjarr[jj+1])  // 如果前面的元素大于后面的元素，则交换它位的位置。      {        itmp=arr[jj+1];        arr[jj+1]=arr[jj];        arr[jj]=itmp;      }    }  }}// 采用递归实现的方法。// 参数arr是待排序数组的首地址，len是数组元素的个数。void bubblesort2(int *arr,unsigned int len){  if (len<2) return; // 数组小于2个元素不需要排序。  int ii;    // 排序的元素位置计数器。  int itmp;  // 比较两个元素大小时交换位置用到的临时变量。  for (ii=0;iiarr[ii+1])  // 如果前面的元素大于后面的元素，则交换它位的位置。    {      itmp=arr[ii+1];      arr[ii+1]=arr[ii];      arr[ii]=itmp;    }  }  bubblesort2(arr,--len);}int main(int argc,char *argv[]){  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};  int len=sizeof(arr)/sizeof(int);  bubblesort1(arr,len);  // 显示排序结果。  int ii;  for (ii=0;ii
2、选择排序
// 选择排序#include #include // 交换两个变量的值。void swap(int *x,int *y){  int itmp=*x;  *x=*y;  *y=itmp;}// 采用两层循环实现的方法。// 参数arr是待排序数组的首地址，len是数组元素的个数。void selectsort1(int *arr,unsigned int len){  if (len<2) return; // 数组小于2个元素不需要排序。  int ii;      // 排序的趟数的计数器。  int jj;      // 每趟排序的元素位置计数器。  int iminpos; // 每趟循环选出的最小值的位置（数组的下标）。  // 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48    for (ii=0;ii
3、插入排序
// 插入排序#include #include // 参数arr是待排序数组的首地址，len是数组元素的个数。void insertsort(int *arr,unsigned int len){  if (len<2) return; // 数组小于2个元素不需要排序。  int itmp;  // 当前需要排序的元素的值。  int ii;    // 需要排序元素的计数器。  int jj;    // 插入排序时，需要后移元素的计数器。  for (ii=1;ii=0&&arr[jj]>itmp);jj--)    for (jj=ii-1;jj>=0;jj--)    {      if (arr[jj]<=itmp) break;      arr[jj+1]=arr[jj]; // 逐个元素后移。    }    arr[jj+1]=itmp; // 插入当前排序元素。  }}int main(int argc,char *argv[]){  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};  int len=sizeof(arr)/sizeof(int);  insertsort(arr,len);   // 调用插入排序函数对数组排序。  // 显示排序结果。  int yy; for (yy=0;yy
4、希尔排序
// 希尔排序#include #include // 对希尔排序中的单个组进行排序。// arr-待排序的数组，len-数组总的长度，ipos-分组的起始位置，istep-分组的步长（增量）。void groupsort(int *arr, int len, int ipos,int istep){  int itmp;  // 当前需要排序的元素的值。  int ii;    // 需要排序元素的计数器。  int jj;    // 插入排序时，需要后移元素的计数器。  for (ii=ipos+istep;ii=0&&arr[jj]>itmp);jj=jj-istep)    for (jj=ii-istep;jj>=0;jj=jj-istep)    {      if (arr[jj]<=itmp) break;        arr[jj+istep]=arr[jj];  // 逐个元素后移。    }    arr[jj+istep]=itmp; // 插入当前排序元素。  }}// 希尔排序，arr是待排序数组的首地址，len是数组的大小。void shellsort(int *arr,unsigned int len){  int ii,istep;  // istep为步长，每次减为原来的一半取整数，最后一次必定为1。  for (istep=len/2;istep>0;istep=istep/2)  {    // 共istep个组，对每一组都执行插入排序。    for (ii=0;ii
5、快速排序
// 快速排序#include #include void quicksort(int *arr,unsigned int len){  if (len<2) return;  // 数组的元素小于2个就不用排序了。  int itmp=arr[0];  // 选取最左边的数作为中心轴。  int ileft=0;      // 左下标。  int iright=len-1; // 右下标。  int imoving=2;    // 当前应该移动的下标，1-左下标；2-右下标。  while (ileft=itmp) { iright--; continue; }            // 如果右下标位置元素的值小于中心轴，把它填到左下标的坑中。      arr[ileft]=arr[iright];      ileft++;    // 左下标向右移动。      imoving=1;  // 下次循环将移动左下标。      continue;    }    if (imoving==1) // 移动左下标的情况。    {      // 如果左下标位置元素的值小等于中心轴，继续移动左下标。      if (arr[ileft]<=itmp) { ileft++; continue; }      // 如果左下标位置元素的值大于中心轴，把它填到右下标的坑中。      arr[iright]=arr[ileft];      iright--;   // 右下标向左移动。      imoving=2;  // 下次循环将移动右下标。      continue;    }  }  // 如果循环结束，左右下标重合，把中心轴的值填进去。  arr[ileft]=itmp;  quicksort(arr,ileft);             // 对中心轴左边的序列进行排序。  quicksort(arr+ileft+1,len-ileft-1); // 对中心轴右边的序列进行排序。}int main(int argc,char *argv[]){  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};  int len=sizeof(arr)/sizeof(int);  quicksort(arr,len);   // 调用插入排序函数对数组排序。  // 显示排序结果。  int yy; for (yy=0;yy
6、归并排序
// 采用递归的方法实现归并排序#include #include #include // 采用递归的方法实现归并排序函数。// arr-待排序数组的首地址，arrtmp-用于排序的临时数组的首地址// start-排序区间第一个元素的位置，end-排序区间最后一个元素的位置。void _mergesort(int *arr,int *arrtmp,int start,int end) {  // 如果start>=end，表示该区间的元素少于两个，递归终止。  if (start>=end) return;   int mid=start+(end-start)/2;  // 计算排序区间中间的位置。  int istart1=start,iend1=mid;  // 区间左边元素的第一和最后一个元素的位置。  int istart2=mid+1,iend2=end;  // 区间右边元素的第一和最后一个元素的位置。  _mergesort(arr,arrtmp,istart1,iend1);   // 对区间左边元素递归排序。  _mergesort(arr,arrtmp,istart2,iend2);   // 对区间右边元素递归排序。  int ii=start; // 已排序数组arrtmp的计数器。  // 把区间左右两边数列合并到已排序数组arrtmp中。  while (istart1<=iend1 && istart2<=iend2)    arrtmp[ii++]=arr[istart1]
// 采用循环的方法实现归并排序函数#include #include #include int min(int x,int y) { return x
7、堆排序
// 堆排序#include #include // 交换两个元素的值。void swap(int *a,int *b) { int temp=*b; *b=*a; *a=temp; }// 采用循环实现heapify（元素下沉）。// arr-待排序数组的地址，start-待heapify节点的下标，end-待排序数组最后一个元素的下标。void heapify(int *arr,int start,int end) {  // 确定父节点和左子节点的数组下标。  int dad=start;  int son=dad*2+1;  // 如果子节点的下标没有超出范围，循环继续。  while (son<=end)   {     // 先比较两個子节点大小，选择最大的。    if ((son+1<=end) && (arr[son]arr[son]) return;    // 否则交换父子內容再继续子节点和孙节点比较。    swap(&arr[dad],&arr[son]);    dad=son;    son=dad*2+1;  }}// 采用递归实现heapify。void heapify1(int *arr,int start,int end) {  // 确定父节点和左子节点的数组下标。  int dad=start;  int son=dad*2+1;  // 如果子节点的下标没有超出范围，循环继续。  if (son>end ) return;  // 先比较两個子节点大小，选择最大的。  if ((son+1<=end) && (arr[son]arr[son]) return;  // 否则交换父子內容再继续子节点和孙节点比较。  swap(&arr[dad],&arr[son]);  heapify(arr,son,end);}void heapsort(int *arr, int len) {  int ii;  // 初始化堆，从最后一個父节点开始调整。  for (ii=(len-1)/2;ii>=0;ii--) heapify(arr,ii,len-1);  // 把第一个元素和堆最后一个元素交换，然后重新调整，直到排序完毕。  for (ii=len-1;ii>0;ii--)   {    swap(&arr[0],&arr[ii]);    heapify(arr,0,ii-1);  }}int main() {  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};  int len=sizeof(arr)/sizeof(int);  heapsort(arr,len);  // 显示排序结果。  int yy; for (yy=0;yy
8、计数排序
// 计数排序（基础版）#include #include #include // 获取待排序数组的最大元素的值。int arrmax(int *arr,unsigned int len){  int ii=0;  int imax=0;  for (ii=0;ii
9、桶排序
// 桶排序#include #include #include // 采用两层循环实现冒泡排序的方法。// 参数arr是待排序数组的首地址，len是数组元素的个数。void bubblesort(int *arr,unsigned int len){  if (len<2) return; // 数组小于2个元素不需要排序。  int ii;    // 排序的趟数的计数器。  int jj;    // 每趟排序的元素位置计数器。  int itmp;  // 比较两个元素大小时交换位置用到的临时变量。  // 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48    for (ii=len-1;ii>0;ii--)  // 一共进行len-1趟比较。  {    for (jj=0;jjarr[jj+1])  // 如果前面的元素大于后面的元素，则交换它位的位置。      {        itmp=arr[jj+1];        arr[jj+1]=arr[jj];        arr[jj]=itmp;      }    }  }}// 桶排序主函数，参数arr是待排序数组的首地址，len是数组元素的个数。void bucketsort(int *arr,unsigned int len){  int buckets[5][5];   // 分配五个桶。  int bucketssize[5];  // 每个桶中元素个数的计数器。  // 初始化桶和桶计数器。  memset(buckets,0,sizeof(buckets));  memset(bucketssize,0,sizeof(bucketssize));  // 把数组arr的数据放入桶中。  int ii=0;  for (ii=0;ii
10、基数排序
#include #include #include // 获取数组arr中最大值，arr-待排序的数组，len-数组arr的长度。int arrmax(int *arr,unsigned int len){  int ii,imax;  imax=arr[0];  for (ii=1;iiimax) imax=arr[ii];  return imax;}// 对数组arr按指数位进行排序。// arr-待排序的数组，len-数组arr的长度。// exp-排序指数，exp=1：按个位排序；exp=10：按十位排序；......void _radixsort(int *arr,unsigned int len,unsigned int exp){  int ii;  int result[len];       // 存放从桶中收集后数据的临时数组。  int buckets[10]={0};   // 初始化10个桶。  // 遍历arr，将数据出现的次数存储在buckets中。  for (ii=0;ii=0;ii--)  {    int iexp=(arr[ii]/exp);    result[buckets[iexp]-1]=arr[ii];    buckets[iexp]--;  }    // 将排序好的数组result复制到数组arr中。  memcpy(arr,result,len*sizeof(int));}// 基数排序主函数，arr-待排序的数组，len-数组arr的长度。void radixsort(int *arr,unsigned int len){  int imax=arrmax(arr,len);    // 获取数组arr中的最大值。  int iexp;    // 排序指数，iexp=1：按个位排序；iexp=10：按十位排序；......  // 从个位开始，对数组arr按指数位进行排序。  for (iexp=1;imax/iexp>0;iexp=iexp*10)  {    _radixsort(arr,len,iexp);    int yy; printf("exp=%-5d  ",iexp); for (yy=0;yy
以上就是"C语言数据结构经典10大排序算法实例分析"这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注行业资讯频道。