devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法中的排序算法_t=a[i] a[i]=a[6-i] a[6-i]=t

作者：盐析白兔 | 2024-04-30 04:21:51

赞

踩

t=a[i] a[i]=a[6-i] a[6-i]=t

目录

一.直接插入排序

二.希尔排序

三.简单选择排序

四.堆排序

五.冒泡排序

六.快速排序

七.归并排序

八.基数排序

九.算法的稳定性和复杂度

一.直接插入排序

  1. #include <stdio.h>
  2.  
  3. void Insertsort(int a[],int n){
  4.     int i,j,t;
  5.     for(i=1;i<n;i++){
  6.         if(a[i]<a[i-1]){
  7.             t=a[i];
  8.             j=i-1;
  9.             do{
  10.                 a[j+1]=a[j];
  11.                 j--;
  12.             }while(j>=0 && a[j]>t);
  13.         }
  14.         a[j+1]=t;
  15.     }
  16. }
  17.  
  18. int main()
  19. {
  20.     int a[9];
  21.     int n;
  22.     printf("请输入n个数:\nn=");
  23.     scanf("%d",&n);
  24.     printf("请输入：");
  25.     for(int i=0;i<n;i++)
  26.         scanf("%d",&a[i]);
  27.     Insertsort(a,n);
  28.     printf("排序后的数字顺序为：");
  29.     for(int i=0;i<n;i++)
  30.         printf("%d,",a[i]);
  31.     return 0;
  32. }

二.希尔排序

  1. #include <stdio.h>
  2.  
  3. void Shellsort(int a[],int n){
  4.     int i,j,d,t;
  5.     d=n/2;
  6.     while(d>0){
  7.         for(i=d;i<n;i++){
  8.             t=a[i];
  9.             j=i-d;
  10.             while(j>=0 && t<a[j]){
  11.                 a[j+d]=a[j];
  12.                 j=j-d;
  13.             }
  14.             a[j+d]=t;
  15.         }
  16.         d=d/2;
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.      int a[9];
  23.     int n;
  24.     printf("请输入n个数:\nn=");
  25.     scanf("%d",&n);
  26.     printf("请输入：");
  27.     for(int i=0;i<n;i++)
  28.         scanf("%d",&a[i]);
  29.     Shellsort(a,n);
  30.     printf("排序后的数字顺序为：");
  31.     for(int i=0;i<n;i++)
  32.         printf("%d,",a[i]);
  33.     return 0;
  34. }

三.简单选择排序

  1. #include <stdio.h>
  2.  
  3. void SelectSort(int a[],int n)
  4. {
  5.     int t,k;
  6.     for(int i=0;i<n-1;i++)
  7.     {
  8.         k=i;
  9.         for(int j=i;j<n;j++)
  10.         {
  11.             if(a[j]<a[k])
  12.             {
  13.                 k=j;//记录最小值的下标
  14.             }
  15.         }
  16.         if(k!=i)
  17.         {
  18.             t=a[k];
  19.             a[k]=a[i];
  20.             a[i]=t;
  21.         }
  22.     }
  23. }
  24.  
  25. int main()
  26. {
  27.     int n=5;
  28.     int a[n];
  29.     printf("请输入%d个数：",n);
  30.     for(int i=0;i<n;i++)
  31.         scanf("%d",&a[i]);
  32.     SelectSort(a,n);
  33.     printf("排序后的顺序为：");
  34.     for(int i=0;i<n;i++)
  35.         printf("%d,",a[i]);
  36.     return 0;
  37. }

四.堆排序

  1. #include <stdio.h>
  2.  
  3. void sift(int a[],int low,int high)
  4. {
  5.     int i=low,j=2*i;
  6.     int t=a[i];
  7.     while(j<=high)
  8.     {
  9.         if(j<high && a[j]<a[j+1])
  10.             j++;
  11.         if(t<a[j])
  12.         {
  13.             a[i]=a[j];
  14.             i=j;
  15.             j=2*i;
  16.         }
  17.         else
  18.             break;
  19.     }
  20.     a[i]=t;
  21. }
  22.  
  23.  
  24.  
  25. void HeapSort(int a[],int n)
  26. {
  27.     int i,t;
  28.     for(i=n/2;i>=1;i--)
  29.         sift(a,i,n);
  30.     for(i=n;i>=2;i--)
  31.     {
  32.         t=a[1];
  33.         a[1]=a[i];
  34.         a[i]=t;
  35.         //swap(a,0,i);
  36.         sift(a,1,i-1);
  37.     }
  38. }
  39.  
  40.  
  41. int  main(){
  42.     int a[]={6,8,7,9,0,1,3,2,4,5};
  43.     int n = sizeof(a) / sizeof(a[0]);
  44.     printf("%d\n",n);
  45.     HeapSort(a,n);
  46.     printf("排序好的数值顺序为：");
  47.     for(int i=0;i<n;i++)
  48.         printf("%d,",a[i]);
  49.     return 0;
  50. }

五.冒泡排序

  1. #include <stdio.h>
  2.  
  3. void MaopaoSort(int a[],int n)
  4. {
  5.     int t;
  6.     for(int i=0;i<n-1;i++)  //4个数比较3次，n个数执行n-1次
  7.     {
  8.         for(int j=0;j<n-1-i;j++) 
  9.         //第n次比较中要比上一次少比较1次
  10.  
  11.         //如序列 3 2 4 1
  12.         //第一次 4_1 2_1 3_1 交换位置，比较3次
  13.         //第二次 4_2 3_4 交换位置，比较2次
  14.         //第三次 3_4 交换位置,比较1次
  15.         {
  16.             if(a[j]>a[j+1])
  17.             {
  18.                 t=a[j];
  19.                 a[j]=a[j+1];
  20.                 a[j+1]=t;
  21.             }
  22.         }
  23.     }
  24. }
  25.  
  26. int main()
  27. {
  28.     int a[]={4,53,2,135,21,13,315,124};
  29.     int n=sizeof(a)/sizeof(a[0]);
  30.     MaopaoSort(a,n);
  31.     for(int i=0;i<n;i++)
  32.         printf("%d,",a[i]);
  33.     return 0;
  34. }

六.快速排序

  1. #include <stdio.h>
  2.  
  3. int partition(int a[],int s,int t)
  4. {
  5.     int i=s,j=t;
  6.     int tmp=a[i];
  7.     while(i<j)//从两端交替向中间扫描，直至i=j为止
  8.     {
  9.         while(j>i && a[j]>=tmp)//从右向左扫描，找到一个小于tmp的值
  10.             j--;
  11.         a[i]=a[j];//找到这样的a[j]放到a[i]处
  12.         while(i<j && a[i]<=tmp)
  13.             i++;
  14.         a[j]=a[i];
  15.     }
  16.     a[i]=tmp;
  17.     return i;
  18. }
  19.  
  20. void quickSort(int a[],int s,int t)
  21. {
  22.     int i;
  23.     if(s<t)//区间至少存在两个元素的情况
  24.     {
  25.         i=partition(a,s,t);
  26.         quickSort(a,s,i-1);//对左区间递归排序
  27.         quickSort(a,i+1,t);//对右区间递归排序
  28.     }
  29. }
  30.  
  31. int main()
  32. {
  33.     int a[]={54,4671,134,124,315};
  34.     int n=sizeof(a)/sizeof(a[0]);
  35.     quickSort(a,0,n-1);//对a[0,n-1]的元素进行快速排序
  36.     for(int i=0;i<n;i++)
  37.         printf("%d,",a[i]);
  38.     return 0;
  39. }

七.归并排序

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void Merge(int a[],int low,int mid,int high)//归并R[low..high]
  4. {
  5.     int *R1;
  6.     int i=low,j=mid+1,k=0;//k是R1的下标，i,j分别是第1、2段的下标
  7.     R1=(int *)malloc((high-low+1)*sizeof(int));
  8.     while(i<=mid && j<=high)//在第1段和第2段均未扫描完时循环
  9.     {
  10.         if(a[i]<=a[j])//将第1段中的元素放入R1中
  11.         {
  12.             R1[k]=a[i];
  13.             i++;
  14.             k++;
  15.         }
  16.         else//将第2段中的元素放入R1中
  17.         {
  18.             R1[k]=a[j];
  19.             j++;k++;
  20.         }
  21.     }
  22.     while(i<=mid)//将第1段余下的部分复制到R1
  23.     {
  24.         R1[k]=a[i];
  25.         i++;k++;
  26.     }
  27.     while(j<=high)//将第2段余下的部分复制到R1
  28.     {
  29.         R1[k]=a[j];
  30.         j++;
  31.         k++;
  32.     }
  33.     for(k=0,i=low;i<=high;k++,i++)将R1复制到R[low..high]中
  34.         a[i]=R1[k];
  35.     free(R1);
  36. }
  37.  
  38. void MergePass(int a[],int length,int n)//对整个排序序列进行一趟归并
  39. {
  40.     int i;
  41.     for(i=0;i+2*length-1<n;i=i+2*length)//归并length长的两相邻子表
  42.         Merge(a,i,i+length-1,i+2*length-1);
  43.     if(i+length-1<n-1)//余下两个子表，后者的长度小于length
  44.         Merge(a,i,i+length-1,n-1);//归并这两个子表
  45. }
  46.  
  47. void MergeSort(int a[],int n)//二路归并排序
  48. {
  49.     int length;
  50.     for(length=1;length<n;length=2*length)//进行log2n(向上取整)趟归并
  51.         MergePass(a,length,n);
  52. }
  53.  
  54.  
  55. int main()
  56. {
  57.     int a[]={14,673,25,1314,525,1,2,3,4,7};
  58.     int n=sizeof(a)/sizeof(a[0]);
  59.     MergeSort(a,n);
  60.     for(int i=0;i<n;i++)
  61.         printf("%d,",a[i]);
  62.     return 0;
  63. }

八.基数排序

  1. #include <stdio.h>
  2. #include <string.h>
  3. #define  size 10    // 数组长度
  4. #define  D 5        // 最大位数
  5.  
  6. //取整数M的第i位数
  7. int GetDigit(int M, int i) 
  8. {
  9. 	while(i > 1)
  10. 	{
  11. 		M /= 10;
  12. 		i--;
  13. 	}
  14. 	return M % 10;
  15. }
  16.  
  17. // 基数排序
  18. void RadixSort(int *num, int len)
  19. {
  20.     int i, j, k, l, digit;
  21.     int allot[10][size];   // 分配数组
  22.     
  23.     // 初始化分配数组全为0
  24.     memset(allot, 0, sizeof(allot));
  25.     
  26.     // 遍历
  27.     for (i = 1; i <= D; i++)
  28.     {
  29.         // 将每个数据的第i位数分配到allot数组中
  30.         for (j = 0; j < len; j++)
  31.         {
  32.             // 获取当前数据 num[j] 的 第i位数
  33.             digit = GetDigit(num[j], i);  
  34.             k = 0;
  35.             // 查找插入的位置
  36.             while (allot[digit][k])
  37.             {
  38.                 k++;
  39.             }
  40.             // 将num[j]添加到分配数组allot的第digit行的末尾
  41.             allot[digit][k] = num[j];
  42.         }
  43.         // 将分配数组的数据收集到原数组中
  44.         l = 0;
  45.         for (j = 0; j < 10; j++)
  46.         {
  47.             k = 0;
  48.             // 获取数组allot的每一行的数据 到 原数组中
  49.             while (allot[j][k])
  50.             {
  51.                 num[l++] = allot[j][k++];
  52.             }
  53.         }
  54.         memset(allot, 0, sizeof(allot));
  55.     }
  56. }
  57.  
  58. int main()
  59. {
  60.     int i, num[size] = {52, 200, 4, 1034, 17, 3319, 8324, 33112, 603, 8};
  61.     RadixSort(num, size);
  62.  
  63.     for (i = 0; i < size; i++)
  64.     {
  65.         printf("%d ", num[i]);
  66.     }
  67.     printf("\n");
  68.     return 0;
  69. }

九.算法的稳定性和复杂度

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/511404
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号