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

1、冒泡排序

// 冒泡排序
#include <stdlib.h>
#include <stdio.h>

// 采用两层循环实现的方法。
// 参数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;jj<ii;jj++)  // 每趟只需要比较0......ii之间的元素,ii之后的元素是已经排序好的。
    {
      if (arr[jj]>arr[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;ii<len-1;ii++)  // 每趟只需要比较0......len-1之间的元素,len-1之后的元素是已经排序好的。
  {
    if (arr[ii]>arr[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<len;ii++) printf("%2d ",arr[ii]);

  printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

2、选择排序

// 选择排序
#include <stdlib.h>
#include <stdio.h>

// 交换两个变量的值。
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<len-1;ii++)  // 一共进行len-1趟比较。
  {
    iminpos=ii;

    for (jj=ii+1;jj<len;jj++)  // 每趟只需要比较ii+1......len-1之间的元素,ii之前的元素是已经排序好的。
    {
      // 找出值更小的元素,记下它的位置。
      if (arr[jj]<arr[iminpos])  iminpos=jj;
    }

    // 如果本趟循环的最小的元素不是起始位置的元素,则交换它们的位置。
    if (iminpos!=ii) swap(&arr[ii],&arr[iminpos]);
  }
}

// 采用递归实现的方法。
// 参数arr是待排序数组的首地址,len是数组元素的个数。
void selectsort2(int *arr,unsigned int len)
{
  if (len<2) return; // 数组小于2个元素不需要排序。

  int ii;        // 排序的趟数的计数器。
  int iminpos=0; // 每趟循环选出的最小值的位置(数组的下标)。

  for (ii=1;ii<len;ii++)
  {
    // 找出值更小的元素,记下它的位置。
    if (arr[ii]<arr[iminpos])  iminpos=ii;
  }

  // 如果本趟循环的最小的元素不是起始位置的元素,则交换它们的位置。
  if (iminpos!=0) swap(&arr[0],&arr[iminpos]);

  selectsort2(arr+1,--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 arr[]={3,4,5,1};
  int len=sizeof(arr)/sizeof(int);

  // selectsort1(arr,len);  // 采用两层循环排序的方法。
  selectsort2(arr,len);  // 采用递归排序的方法。

  // 显示排序结果。
  int ii; for (ii=0;ii<len;ii++) printf("%2d ",arr[ii]);

  printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

3、插入排序

// 插入排序
#include <stdlib.h>
#include <stdio.h>

// 参数arr是待排序数组的首地址,len是数组元素的个数。
void insertsort(int *arr,unsigned int len)
{
  if (len<2) return; // 数组小于2个元素不需要排序。

  int itmp;  // 当前需要排序的元素的值。
  int ii;    // 需要排序元素的计数器。
  int jj;    // 插入排序时,需要后移元素的计数器。

  for (ii=1;ii<len;ii++)
  {
    itmp=arr[ii];    // 待排序元素

    // 从已排序的最右边开始,把大于当前排序的元素后移。
    // for (jj=ii-1;(jj>=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<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

4、希尔排序

// 希尔排序
#include <stdlib.h>
#include <stdio.h>

// 对希尔排序中的单个组进行排序。
// 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<len;ii=ii+istep)
  {
    itmp=arr[ii];    // 待排序元素

    // 从已排序的最右边开始,把大于当前排序的元素后移。
    // for (jj=ii-istep;(jj>=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<istep;ii++)
    {
      groupsort(arr,len,ii,istep);
    }
  }
}

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);

  shellsort(arr,len);   // 调用插入排序函数对数组排序。

  // 显示排序结果。
  int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

5、快速排序

// 快速排序
#include <stdlib.h>
#include <stdio.h>

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<iright)
  {
    if (imoving==2) // 移动右下标的情况。
    {
      // 如果右下标位置元素的值大于等于中心轴,继续移动右下标。
      if (arr[iright]>=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<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

6、归并排序

// 采用递归的方法实现归并排序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// 采用递归的方法实现归并排序函数。
// 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]<arr[istart2] ? arr[istart1++] : arr[istart2++];

  // 把左边数列其它的元素追加到已排序数组。
  while (istart1<=iend1) arrtmp[ii++]=arr[istart1++];

  // 把右边数列其它的元素追加到已排序数组。
  while (istart2<=iend2) arrtmp[ii++]=arr[istart2++];

  // 把已排序数组arrtmp中的元素复制到arr中。
  memcpy(arr+start,arrtmp+start,(end-start+1)*sizeof(int));
}

// 排序主函数,arr为待排序的数组的地址,len为数组的长度。
void mergesort(int *arr,unsigned int len)
{
  if (len<2) return;  // 小于两个元素不需要排序。

  int arrtmp[len];  // 分配一个与待排序数组相同大小的数组。

  _mergesort(arr,arrtmp,0,len-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);

  mergesort(arr,len);

  // 显示排序结果。
  int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}
// 采用循环的方法实现归并排序函数
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int min(int x,int y) { return x<y ? x : y; }  // 取x和y中的较小者的值。

// 采用循环实现归并排序,arr-待排序数组的首地址,len--待排序数组的长度。
void mergesort(int *arr,unsigned int len)
{
  if (len<2) return;  // 小于两个元素不需要排序。

  int *aa=arr;     // aa指向待排序的数组。
  int *bb=(int *)malloc(len*sizeof(int)); // bb指向已排序的数组。

  int iseg;    // 区间分段的计数器,1,2,4,8,16,...
  int istart;  // 区间起始位置的计数器。

  // 排序的趟数的循环。
  for (iseg=1;iseg<len;iseg=iseg*2)
  {
    // 每趟排序选取区间的循环。
    for (istart=0;istart<len;istart=istart+iseg*2)
    {
      // 把每个区间分成两部分,ilow是起始位置,imid是中间位置,imax是结束位置。
      int ilow=istart;
      int imid=min(istart+iseg,len);     // 考虑分段不均的情况,imid不能超出len。
      int imax=min(istart+iseg*2,len);   // 考虑分段不均的情况,imax也不能超出len。

      int ii=ilow; // 已排序数组的计数器。
      int istart1=ilow,iend1=imid;  // 待排序左边数列的起始和结束位置。
      int istart2=imid,iend2=imax;  // 待排序右边数列的起始和结束位置。

      // 把待排序左右两边数列合并到已排序数组。
      while ((istart1<iend1) && (istart2<iend2))
        bb[ii++]=aa[istart1]<aa[istart2] ? aa[istart1++] : aa[istart2++];

      // 把左边数列其它的元素追加到已排序数组。
      while (istart1<iend1) bb[ii++]=aa[istart1++];

      // 把右边数列其它的元素追加到已排序数组。
      while (istart2<iend2) bb[ii++]=aa[istart2++];
    }

    // 交换一下两个数组的指针,准备下一趟的排序。
    int *ptmp=aa; aa=bb; bb=ptmp;
  }

  // 如果aa指向的不是原始数组的指针,把aa中的内容复制到arr中。
  if (aa != arr)
  {
    memcpy(arr,aa,len*sizeof(int));

    bb = aa;
  }

  free(bb);
}

int main(int argc,char *argv[])
{
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48,10};
  int len=sizeof(arr)/sizeof(int);

  mergesort(arr,len);

  // 显示排序结果。
  int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

7、堆排序

// 堆排序
#include <stdio.h>
#include <stdlib.h>

// 交换两个元素的值。
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+1])) son++;

    // 如果父节点大于子节点代表调整完毕,直接跳出函数。
    if (arr[dad]>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+1])) son++;

  // 如果父节点大于子节点代表调整完毕,直接跳出函数。
  if (arr[dad]>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<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

8、计数排序

// 计数排序(基础版)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 获取待排序数组的最大元素的值。
int arrmax(int *arr,unsigned int len)
{
  int ii=0;
  int imax=0;

  for (ii=0;ii<len;ii++) if (imax<arr[ii]) imax=arr[ii];

  return imax;
}

// 计数排序主函数,arr-待排序数组的地址,len-数组的长度。
void countsort(int *arr,unsigned int len)
{
  if (len<2) return;

  int imax=arrmax(arr,len);  // 获取待排序数组的最大元素的值。
  int arrtmp[imax+1];        // 临时数组的大小为imax+1。

  memset(arrtmp,0,sizeof(arrtmp));  // 初始化临时数组。

  int ii,jj,kk;

  // 临时数组计数。
  for (ii=0;ii<len;ii++) arrtmp[arr[ii]]++;

  // 把临时数组计数的内容填充到arr中。
  ii=0;
  for (jj=0;jj<imax+1;jj++)
  {
    for (kk=0;kk<arrtmp[jj];kk++) arr[ii++]=jj;
  }
}

int main()
{
  int arr[]={2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2};

  int len=sizeof(arr)/sizeof(int);

  int xx; for (xx=0;xx<len;xx++) printf("%2d ",arr[xx]); printf("\n");

  countsort(arr,len);

  // 显示排序结果。
  int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

9、桶排序

// 桶排序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// 采用两层循环实现冒泡排序的方法。
// 参数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;jj<ii;jj++)  // 每趟只需要比较0......ii之间的元素,ii之后的元素是已经排序好的。
    {
      if (arr[jj]>arr[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<len;ii++)
  {
    buckets[arr[ii]/10][bucketssize[arr[ii]/10]++]=arr[ii];
  }

  // 对每个桶进行冒泡排序。
  for (ii=0;ii<5;ii++)
  {
    bubblesort(buckets[ii],bucketssize[ii]);
  }

  // 把每个桶中的数据填充到数组arr中。
  int jj=0,kk=0;
  for (ii=0;ii<5;ii++)
  {
    for (jj=0;jj<bucketssize[ii];jj++)
      arr[kk++]=buckets[ii][jj];
  }
}

int main(int argc,char *argv[])
{
  int arr[]={21,3,30,44,15,36,6,10,9,19,25,48,5,23,47};
  int len=sizeof(arr)/sizeof(int);

  int xx; for (xx=0;xx<len;xx++) printf("%2d ",arr[xx]); printf("\n");

  bucketsort(arr,len);

  // 显示排序结果。
  int ii; for (ii=0;ii<len;ii++) printf("%2d ",arr[ii]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

10、基数排序

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// 获取数组arr中最大值,arr-待排序的数组,len-数组arr的长度。
int arrmax(int *arr,unsigned int len)
{
  int ii,imax;

  imax=arr[0];

  for (ii=1;ii<len;ii++)
    if (arr[ii]>imax) 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<len;ii++)
    buckets[(arr[ii]/exp)%10]++;

  // 调整buckets各元素的值,调整后的值就是arr中元素在result中的位置。
  for (ii=1;ii<10;ii++)
    buckets[ii]=buckets[ii]+buckets[ii-1];

  // 将arr中的元素填充到result中。
  for (ii=len-1;ii>=0;ii--)
  {
    int iexp=(arr[ii]/exp)%10;
    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<len;yy++) printf("%2d ",arr[yy]); printf("\n");
  }
}

int main(int argc,char *argv[])
{
  int arr[]={144,203,738,905,347,215,836,26,527,602,946,504,219,750,848};
  int len=sizeof(arr)/sizeof(int);

  radixsort(arr,len);  // 基数排序。

  // 显示排序结果。
  int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return 0;
}

到此这篇关于C语言数据结构经典10大排序算法刨析的文章就介绍到这了,更多相关C语言 排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言中冒泡排序算法详解

    目录 一.算法描述 二.算法分析 三.完整代码 总结 一.算法描述 比较相邻两个元素,如果第一个比第二个大则交换两个值.遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面.假设数组有 n 个元素,那么需要遍历 n - 1 次,因为剩下的一个元素一定是最小的,无需再遍历一次.因此需要两层循环,第一层是遍历次数,第二层是遍历未排序数组. 动图如下: 黄色部分表示已排好序的数组,蓝色部分表示未排序数组 核心代码如下: /** * @brief 冒泡排序 * * @param arr 待排序的数

  • C语言直接插入排序算法

    目录 1.算法模板 2.算法介绍 3.实例 总结 1.算法模板 void InsertSort(SqList *L) { int j; for (int i = 2; i <= L->length; i ++ ) { if (L->arr[i] < L->arr[i-1]) { L->arr[0] = L->arr[i]; // 设置哨兵 for (j = i - 1; L->arr[j] > L->arr[0]; j -- ) L->ar

  • C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第

  • C语言实现单链表的快速排序算法

    目录 背景 设计思路 算法主要步骤 快速排序算法实现 整个程序源代码 测试案例 总结 背景 传统QuickSort算法最大不足之处在于,由于其基于可索引存储结构设计(一般为数组或索引表),因而无法用于链式存储结构,而链式存储结构的实际应用非常广泛,例如动态存储管理.动态优先级调度等等,故本文针对于单向链表,以QuickSort的分治策略为基础,提出一种可用于单向链表的快速排序算法. 设计思路 将单向链表的首节点作为枢轴节点,然后从单向链表首部的第二个节点开始,逐一遍历所有后续节点,并将这些已遍历

  • C语言冒泡排序算法代码详解

    今天我们来用C语言实现一下冒泡排序 首先我们来了解一下什么叫做冒泡排序,冒泡顾名思义把质量轻的气体(如二氧化碳一样)浮到水面上(如可乐中的二氧化碳),因此冒泡排序的原理就是N个元素在一个周期中,微观上依次进行两两元素的比较,小的元素就被放在前面,大的元素放在后面,以此来进行N-1个周期,来完成冒泡排序. 上文中的一个周期,即外循环,依次进行比较,即内循环. 文字看着很迷糊?没事儿,上图 如图所示,两两元素依次进行比较,小的元素往前移动,大的元素往后移动,直至元素顺序是升序的形式,即移动了 元素-

  • C语言直接插入排序算法介绍

    目录 前言 一.什么是直接插入排序 二.代码讲解 总结 前言 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i =

  • C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

  • C语言之直接插入排序算法的方法

    目录 一.什么是直接插入排序 二.代码讲解 总结 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i = 0; i

  • C语言之快速排序算法(递归Hoare版)介绍

    废话不多说,先看代码 #define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标 int key =

  • C语言数据结构经典10大排序算法刨析

    1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp

  • C语言的10大基础算法

    算法是一个程序和软件的灵魂,作为一名优秀的程序员,只有对一些基础的算法有着全面的掌握,才会在设计程序和编写代码的过程中显得得心应手.本文是近百个C语言算法系列的第二篇,包括了经典的Fibonacci数列.简易计算器.回文检查.质数检查等算法.也许他们能在你的毕业设计或者面试中派上用场. 1.计算Fibonacci数列 Fibonacci数列又称斐波那契数列,又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21. C语言实现的代码如下: /* Displaying Fibona

  • C语言实现九大排序算法的实例代码

    直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分.从无序部分中依次取出元素插入到有序部分中.过程就是遍历有序部分,实现起来比较简单. #include <stdio.h> void insertion_sort(int arr[], int array_length) { for (int i = 0; i < array_length; ++i) { int data = arr[i]; int j = 0; while (arr[j] < arr[i]) { j

  • c语言5个常用的排序算法实例代码

    1.插入排序 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =

  •  Java数据结构的十大排序

    目录 1.直接插入排序 1.1 动图演示 1.2 插入排序的思路 1.3 代码实现 1.4 性能分析 2.希尔排序 2.1 原理 2.2 动图演示 2.3 代码实现 2.4 性能分析 3.直接选择排序 3.1 动图演示 3.2 代码实现 3.3 性能分析 4.堆排序 4.1 动图演示 4.2 代码实现 4.3 性能分析 5.冒泡排序 5.1 动图演示 5.2 代码实现 5.3 性能分析 6.快速排序 6.1 原理 6.2 动图演示 6.3 实现方法 6.3.1 Hoare法 6.3.2 挖坑法

  • C语言完整实现12种排序算法(小结)

    目录 1.冒泡排序 2.插入排序 3.折半插入排序 4.希尔排序 5.选择排序 6.鸡尾酒排序 7.堆排序 8.快速排序 9.归并排序 10.计数排序 11.桶排序 12.基数排序 1.冒泡排序 思路:比较相邻的两个数字,如果前一个数字大,那么就交换两个数字,直到有序.时间复杂度O(n^2),稳定性:这是一种稳定的算法.代码实现: void bubble_sort(int arr[],size_t len){ size_t i,j; for(i=0;i<len;i++){ bool hasSwa

  • 可能是你看过最全的十大排序算法详解(完整版代码)

    目录 前言 交集排序 冒泡 简单 快速排序 插入排序 直接插入排序 希尔排序 选择排序 简单选择排序 堆排序 归并排序 二路 多路 非比较类 计数排序 桶排序 基数排序 最后 前言 兄弟们,应上篇数据结构的各位要求,今天我开始工作了,开始肝算法,剑指offer还在路上,我真想开车去接它,奈何码神没有驾照的开车,算了,弄排序算法吧,有点长,耐心看啊,原创不易,你们懂的,先上一张图 可以看出排序算法,还是比较多的,算了,不多说了,你我肝完就是出门自带4年实习经验的! 交集排序 冒泡 冒泡我一般也将它

  • Java 十大排序算法之选择排序刨析

    目录 选择排序原理 选择排序API设计 选择排序代码实现 选择排序的时间复杂度 选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值 选择排序API设计 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a):对

  • Java 十大排序算法之插入排序刨析

    目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort

  • C++实现十大排序算法及排序算法常见问题

    目录 前言 0 概述 1 冒泡排序 2 选择排序 3 插入排序 4 希尔排序 5 归并排序 6 堆排序 7 快速排序 8 计数排序 9 桶排序 10 基数排序 总结 前言 本文为C++实现的十大排序算法及基于排序算法解决的一些常见问题,每一种算法均实际运行,确保正确无误.文中内容为自己的一些理解,如有错误,请大家指正. 0 概述 在十种排序算法中,前七种是比较类排序,后三种是非比较类排序,每种算法的最好.最坏.平均时间复杂度,空间复杂度以及稳定性如下表所示.稳定性是指排序前后相等的元素相对位置保

随机推荐