21ic电子技术开发论坛 › 单片机与嵌入式系统 › 侃单片机论坛 › 8种排序
返回列表 发新帖我要提问

[C语言] 8种排序

[复制链接]
 楼主| 一路向北lm 发表于 2018-8-8 10:14 | 显示全部楼层 |阅读模式
TI, ST, os, ge, POS

转过来的8种排序
复制
  1. #include<stdio.h>
    

  2. #include<stdlib.h>
    

  3. //冒泡排序
    

  4. void bubleSort(int data[], int n);
    

  5. //快速排序
    

  6. void quickSort(int data[], int low, int high);
    

  7. int findPos(int data[], int low, int high);
    

  8. //插入排序
    

  9. void bInsertSort(int data[], int n);
    

  10. //希尔排序
    

  11. void shellSort(int data[], int n);
    

  12. //选择排序
    

  13. void selectSort(int data[], int n);
    

  14. //堆排序
    

  15. void heapSort(int data[], int n);
    

  16. void swap(int data[], int i, int j);
    

  17. void heapAdjust(int data[], int i, int n);
    

  18. //归并排序
    

  19. void mergeSort(int data[], int first, int last);
    

  20. void merge(int data[], int low, int mid, int high);
    

  21. //基数排序
    

  22. void radixSort(int data[], int n);
    

  23. int getNumPos(int num, int pos);
    


  24. 

  25. int main() {
    

  26.     int data[10] = {43, 65, 4, 23, 6, 98, 2, 65, 7, 79};
    

  27.     int i;
    

  28.     printf("原先数组:");
    

  29.     for(i=0;i<10;i++) {
    

  30.         printf("%d    ", data[i]);
    

  31.     }
    

  32.     printf("\n");
    

  33.     printf("冒泡排序:");
    

  34.     bubleSort(data, 10);
    

  35.     for(i=0;i<10;i++) {
    

  36.         printf("%d    ", data[i]);
    

  37.     }
    

  38.     printf("\n");
    

  39.     printf("快速排序:");
    

  40.     quickSort(data, 0, 9);
    

  41.     for(i=0;i<10;i++) {
    

  42.         printf("%d    ", data[i]);
    

  43.     }
    

  44.     printf("\n");
    

  45.     printf("插入排序:");
    

  46.     bInsertSort(data,10);
    

  47.     for(i=0;i<10;i++) {
    

  48.         printf("%d    ", data[i]);
    

  49.     }
    

  50.     printf("\n");
    

  51.     printf("希尔排序:");
    

  52.     shellSort(data, 10);
    

  53.     for(i=0;i<10;i++) {
    

  54.         printf("%d    ", data[i]);
    

  55.     }
    

  56.     printf("\n");
    

  57.     printf("选择排序:");
    

  58.     selectSort(data, 10);
    

  59.     for(i=0;i<10;i++) {
    

  60.         printf("%d    ", data[i]);
    

  61.     }
    

  62.     printf("\n");
    

  63.     /*int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79};
    

  64.     int i;
    

  65.     printf("原先数组:");
    

  66.     int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79};
    

  67.     for(i=1;i<11;i++) {
    

  68.         printf("%d    ", data[i]);
    

  69.     }
    

  70.     printf("\n");
    

  71.     printf(" 堆排序:");
    

  72.     heapSort(data, 10);
    

  73.     for(i=1;i<11;i++) {
    

  74.         printf("%d    ", data[i]);
    

  75.     }
    

  76.     printf("\n");
    

  77.     printf("归并排序:");
    

  78.     mergeSort(data, 0, 9);
    

  79.     for(i=0;i<10;i++) {
    

  80.         printf("%d    ", data[i]);
    

  81.     }
    

  82.     printf("\n");*/
    

  83.     printf("基数排序:");
    

  84.     radixSort(data, 10);
    

  85.     for(i=0;i<10;i++) {
    

  86.         printf("%d    ", data[i]);
    

  87.     }
    

  88.     printf("\n");
    

  89.     return 0;
    

  90. }
    


  91. 

  92. /*--------------------冒泡排序---------------------*/
    

  93. void bubleSort(int data[], int n) {
    

  94.     int i,j,temp;
    

  95.     //两个for循环，每次取出一个元素跟数组的其他元素比较
    

  96.     //将最大的元素排到最后。
    

  97.     for(j=0;j<n-1;j++) {
    

  98.         //外循环一次，就排好一个数，并放在后面，
    

  99.         //所以比较前面n-j-1个元素即可
    

  100.         for(i=0;i<n-j-1;i++) {
    

  101.             if(data[i]>data[i+1]) {
    

  102.                 temp = data[i];
    

  103.                 data[i] = data[i+1];
    

  104.                 data[i+1] = temp;
    

  105.             }
    

  106.         }
    

  107.     }  
    

  108. }
    


  109. 

  110. /*--------------------快速排序---------------------*/
    

  111. int findPos(int data[], int low, int high) {
    

  112.     //将大于t的元素赶到t的左边，大于t的元素赶到t的右边
    

  113.     int t = data[low];
    

  114.     while(low < high) {
    

  115.         while(low < high && data[high] >= t) {
    

  116.             high--;
    

  117.         }
    

  118.         data[low] = data[high];
    

  119.         while(low < high && data[low] <=t) {
    

  120.             low++;
    

  121.         }
    

  122.         data[high] = data[low];
    

  123.     }
    

  124.     data[low] = t;
    

  125.     //返回此时t在数组中的位置
    

  126.     return low;
    

  127. }
    

  128. //在数组中找一个元素，对大于该元素和小于该元素的两个数组进行再排序
    

  129. //再对两个数组分为4个数组，再排序，直到最后每组只剩下一个元素为止
    

  130. void quickSort(int data[], int low, int high) {
    

  131.     if(low > high) {
    

  132.         return;
    

  133.     }
    

  134.     int pos = findPos(data, low, high);
    

  135.     quickSort(data, low, pos-1);
    

  136.     quickSort(data, pos+1, high); 
    

  137. }
    


  138. 

  139. /*--------------------插入排序---------------------*/
    

  140. void bInsertSort(int data[], int n) {
    

  141.     int low,high,mid;
    

  142.     int temp,i,j;
    

  143.     for(i=1;i<n;i++) {
    

  144.         low = 0;
    

  145.         //把data[i]元素插入到它的前面data[0-(i-1)]中
    

  146.         temp =data[i];
    

  147.         high = i-1;
    

  148.         //该while是折半，缩小data[i]的范围(优化手段)
    

  149.         while(low <= high) {
    

  150.             mid = (low+high)/2;
    

  151.             if(data[mid] > temp) {
    

  152.                 high = mid-1;
    

  153.             }
    

  154.             else {
    

  155.                 low = mid+1;
    

  156.             }
    

  157.         }
    

  158.         int j = i;
    

  159.         //让data与已经排序好的数组的各个元素比较，小的放前面
    

  160.         while((j > low) && data[j-1] > temp) {
    

  161.             data[j] = data[j-1];
    

  162.             --j;
    

  163.         }
    

  164.         data[low] = temp;
    

  165.     }
    

  166. }
    


  167. 

  168. /*--------------------希尔排序---------------------*/
    

  169. void shellSort(int * data, int n) {
    

  170.     int step,i,j,key;
    

  171.     //将数组按照step分组，不断二分到每组只剩下一个元素
    

  172.     for(step=n/2;step>0;step/=2) {
    

  173.         //将每组中的元素排序，小的在前
    

  174.         for(i=step;i<n;i++) {
    

  175.             key = data[i];
    

  176.             for(j=i-step;j>=0 && key<data[j];j-=step) {
    

  177.                 data[j+step] = data[j];
    

  178.             }
    

  179.             //和上面的for循环一起，将组中小的元素换到数组的前面
    

  180.             data[j+step] = key;
    

  181.         }
    

  182.     }
    

  183. }
    


  184. 

  185. /*--------------------选择排序---------------------*/
    

  186. void selectSort(int data[], int n) {
    

  187.     int i,j,mix,temp;
    

  188.     //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的
    

  189.     for(i=0;i<n-1;i++) {
    

  190.         //假设最小元素的下标
    

  191.         int mix = i;
    

  192.         //将上面假设的最小元素与数组比较，交换出最小的元素的下标
    

  193.         for(j=i+1;j<n;j++) {
    

  194.             if(data[j] < data[mix]) {
    

  195.                 mix = j;
    

  196.             }
    

  197.         }
    

  198.         //若数组中真的有比假设的元素还小，就交换
    

  199.         if(i != mix) {
    

  200.             temp = data[i];
    

  201.             data[i] = data[mix];
    

  202.             data[mix] = temp;
    

  203.         }
    

  204.     }
    

  205. }
    


  206. 

  207. /*--------------------堆排序---------------------*/
    

  208. //堆排序将数组先组成二叉树，默认从数组的data[1]开始排，data[0]是
    

  209. //无效数据
    

  210. void heapSort(int data[], int n) {
    

  211.     int i;
    

  212.     //先将数组组成一棵完全二叉树
    

  213.     //从2/n开始，就是从倒数第二排结点往前开始
    

  214.     for(i=n/2;i>0;i--) {
    

  215.         heapAdjust(data, i, n);
    

  216.     }
    

  217.     //循环每个结点，将大的结点交换到堆顶
    

  218.     for(i=n;i>1;i--) {
    

  219.         swap(data, 1, i);
    

  220.         //每次交换完都要调整二叉树，将剩下的最大的结点交换到堆顶
    

  221.         heapAdjust(data, 1, i-1);
    

  222.     }
    

  223. }
    

  224. //交换函数
    

  225. void swap(int data[], int i, int j) {
    

  226.     int temp;
    

  227.     temp = data[i];
    

  228.     data[i] = data[j];
    

  229.     data[j] = temp;
    

  230. }
    

  231. void heapAdjust(int data[], int i, int n) {
    

  232.     int j, temp;
    

  233.     //假设第一个结点的元素是最大的
    

  234.     temp = data[i];
    

  235.     //i结点：2*i是i结点的左结点，2*i+1是i结点的右结点
    

  236.     //把结点元素大的交换到前面
    

  237.     for(j=2*i;j<=n;j*=2) {
    

  238.         if(j < n && data[j] < data[j+1]) {
    

  239.             j++;
    

  240.         }
    

  241.         if(temp >= data[j]) {
    

  242.             break;
    

  243.         }
    

  244.         data[i] = data[j];
    

  245.         i = j;
    

  246.     }
    

  247.     data[i] = temp;
    

  248. }
    


  249. 

  250. /*--------------------归并排序---------------------*/
    

  251. void mergeSort(int data[], int first, int last) {
    

  252.     int mid = 0;
    

  253.     //将数组不停的二分分组再组合，直到每组只剩一个元素
    

  254.     if(first < last) {
    

  255.         mid = (first+last)/2;
    

  256.         mergeSort(data, first, mid);
    

  257.         mergeSort(data, mid+1, last);
    

  258.         merge(data, first, mid, last);
    

  259.     }
    

  260.     return;
    

  261. }
    

  262. void merge(int data[], int low, int mid, int high) {
    

  263.     int i, k;
    

  264.     //定义一个临时数组存放传进来的无序数组排好序之后的数组
    

  265.     int *temp = (int *)malloc((high-low+1)*sizeof(int));
    

  266.     //将无序数组分成两个序列
    

  267.     int left_low = low;
    

  268.     int left_high = mid;
    

  269.     int right_low = mid+1;
    

  270.     int right_high = high;
    

  271.     //将两个序列比较排序，小的排前
    

  272.     for(k=0;left_low<=left_high && right_low<=right_high;k++) {
    

  273.         if(data[left_low]<=data[right_low]) {
    

  274.             temp[k] = data[left_low++];
    

  275.         }
    

  276.         else{
    

  277.             temp[k] = data[right_low++];
    

  278.         }
    

  279.     }
    

  280.     //左序列如果有剩下元素未排序，加到临时数组的末尾
    

  281.     if(left_low <= left_high) {
    

  282.         for(i=left_low;i<=left_high;i++) {
    

  283.             temp[k++] = data[i];
    

  284.         }
    

  285.     }
    

  286.     //右序列如果有剩下元素未排序，加到临时数组的末尾
    

  287.     if(right_low <= right_high) {
    

  288.         for(i=right_low;i<=right_high;i++) {
    

  289.             temp[k++] = data[i];
    

  290.         }
    

  291.     }
    

  292.     //将排好序的小分组转移到原数组中
    

  293.     for(i=0;i<high-low+1;i++) {
    

  294.         data[low+i] = temp[i];
    

  295.     }
    

  296.     free(temp);
    

  297.     return;
    

  298. }
    

  299. /*--------------------基数排序---------------------*/
    

  300. //该函数的作用是找出num的pos位数的数字(比如：23的个位数数字是3)
    

  301. int getNumPos(int num, int pos) {
    

  302.     int i;
    

  303.     int temp = 1;
    

  304.     for(i=0;i<pos-1;i++) {
    

  305.         temp *= 10;
    

  306.     }
    

  307.     return (num / temp) % 10;
    

  308. }
    

  309. void radixSort(int data[], int n) {
    

  310.     int i,j,k,pos,num,index;
    

  311.     //这几句话是创建一个从0-9(行)× (n+1)(列)的网格，第一列从上往下是0-9,
    

  312.     //第二列是该行包含的元素个数，默认为0个
    

  313.     int *radixArrays[10];
    

  314.     for(i=0;i<10;i++) {
    

  315.         radixArrays[i] = (int *)malloc(sizeof(int) * (n+1));
    

  316.         radixArrays[i][0] = 0;
    

  317.     }
    

  318.     //pos最大为31为数，计算机能承受的最大范围了
    

  319.     for(pos=1;pos<=31;pos++) {
    

  320.         //该for循环是将数组的元素按照位数(pos)的值放进网格内
    

  321.         for(i=0;i<n;i++) {
    

  322.             num = getNumPos(data[i], pos);
    

  323.             index = ++radixArrays[num][0];
    

  324.             radixArrays[num][index] = data[i];
    

  325.         }
    

  326.         //该for循环是将上面的for循环已经按照某个位数(pos)排列好的元素存入数组
    

  327.         for(i=0,j=0;i<10;i++) {
    

  328.             for(k=1;k<=radixArrays[i][0];k++) {
    

  329.                 data[j++] = radixArrays[i][k];
    

  330.             }
    

  331.             //清空网格，以便给下个位数排列
    

  332.             radixArrays[i][0] = 0;
    

  333.         }
    

  334.     }
    

  335. }


回复 赏

举报

相关帖子
yediezeus 发表于 2018-8-8 11:34 | 显示全部楼层
回复 赏

举报

airwill 发表于 2018-8-8 19:47 | 显示全部楼层
好东西, 需要顶一下.
初步看了一下, 好象没有发现哪个的效率特别高一点
回复 赏

举报

评论

一路向北lm
研究一下  发表于 2018-8-9 08:31
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

一路向北lm Image

293

主题

3837

帖子

81

粉丝
快速回复 在线客服 返回列表 返回顶部