常见基础排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了常见基础排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含7784字,纯文字阅读大概需要12分钟。
内容图文
选择排序:
第一次循环,找最小的数,记录下标,然后移到数组的首位, 第二次循环从第二个数开始,继续找剩余最小的数,然后继续移到数组的第二位 依次循环,排完所有的数1 #define _CRT_SECURE_NO_WARNINGS 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 #include <string.h> 6 #define MAXNUM 20 7 //选择排序 8 void election_table(int *table) 9 { 10 for (int i = 0; i < MAXNUM-1; i++) 11 { 12 int flag = i; //记录每次循环后找到的最小值的下标 13 int table_min = table[i]; 14 for (int j = i+1; j < MAXNUM; j++) 15 { 16 if (table_min > table[j]) 17 { 18 flag = j; 19 table_min = table[j]; 20 } 21 } 22 //此时已经找到了这一次循环最小值的下标了 23 int temp = 0; 24 temp = table[flag]; 25 table[flag] = table[i]; 26 table[i] = temp; 27 } 28 } 29 //生成随机数 30 void rand_num() 31 { 32 int table[MAXNUM]; 33 for (int i = 0; i < MAXNUM; i++) 34 { 35 table[i] = rand() % 100; 36 printf(" %d ", table[i]); 37 } 38 printf("\n"); 39 election_table(&table); //对生成的数进行排序 40 for (int i = 0; i < MAXNUM; i++) 41 { 42 printf(" %d ", table[i]); 43 } 44 printf("\n"); 45 } 46 int main(void) 47 { 48 rand_num(); 49 system("pause"); 50 return 0; 51 }
插入排序:
将无序序列插入有序序列中=====> 轮询取出数组的每一个数据,插入适合的位置
- 在基本有序的情况下,插入排序效率很高。
- 在插入序列较少的时候,效率也很高
1 void charu_table(int *table) 2 { 3 int number = 0; //缓存取出的那个数 4 int j = 0; 5 //第一个可以不用进行比较,因为前面没有比他大的 6 for (int i = 1; i < MAXNUM; i++) 7 { 8 number = table[i]; //每次取出数组中的一个数据,插入合适它的位置 9 if (number < table[i - 1]) //当取出的数据比前面的小时 10 { 11 for (j = i; j > 0; j--) //通过循环,找到自己要插入的位置 12 { 13 if (number < table[j - 1]) //当前面的数据比抽出来的数据大时 14 { 15 table[j] = table[j - 1]; //数据向后移动 16 } 17 else //当前面没有自己大时 18 { 19 break; 20 } 21 } 22 table[j] = number; 23 } 24 } 25 }
希尔排序:
例如:把一个大的序列有序分成若干组,之后在利用插入排序,最后按原有顺序合并, 总结:先分后合, ? ? ? ? 分:把数组的元素按下标区别对待 ? ? ? ? 合:慢慢的合并,从三个一组,到六个一组,到十八个一组。。。。。到最后所有元素一组1 void charu_table(int *table) 2 { 3 int increasement = MAXNUM; 4 do { 5 //分数据,也是合并数距,increasement只会越来越小,分组也会越来越少 6 increasement = increasement / 3 + 1; //确定分成几组,第一次分成三个一组,这样效率最高,第二次六个一组 7 //先分 8 for (int i = 0; i < increasement; i++) //在同一个数组上分成increasement组,但是元素还是在原来的数组上,通过循环来操作每一组数据 9 { 10 for (int j = i + increasement; j < MAXNUM; j += increasement) //100个元素,分34组,0 34 68 一组 11 { 12 int temp = table[j]; //保存取出的元素 13 int k = 0; 14 for (k = j - increasement; k >= 0 && temp < table[k]; k -= increasement) 15 { 16 table[k + increasement] = table[k]; //每个小组的元素相比较,向后移动 17 } 18 table[k + increasement] = temp; //把取出的数据插入适当的位置 19 } 20 }//这里出来后就是第一次合并数据了 21 } while (increasement > 1); 22 }
快速排序:
基本思想:快速排序 = 分治法 + 挖坑填数
1 void fast_table(int *table, int Start, int End) 2 { 3 int start = Start; 4 int end = End; 5 int temp = table[start]; //作为基准数 6 if (start < end) 7 { 8 while (start < end) 9 { 10 while (start < end && table[end] > temp) //从后往前 寻找比基准数小的那个数的下标 11 { 12 end--; 13 } 14 if (start < end) 15 { 16 table[start] = table[end]; //填坑,把后面小的数填到前面去 17 start++; 18 } 19 while (start < end && table[start] < temp) //从前往后 寻找比基准数大的那个数的下标 20 { 21 start++; 22 } 23 if (start < end) 24 { 25 table[end] = table[start]; //填坑,把前面大的数填到前面去 26 end--; 27 } 28 } 29 table[start] = temp; //把基准数放到 两个指针放到重合的位置。 30 //通过递归,对左半部分和右半部分排序 31 kuaipai_table(table, 0, start - 1); //梯归虽然方便,但是效率太低 32 kuaipai_table(table, start + 1, End); //梯归虽然方便,但是效率太低 33 } 34 }
归并排序
1 void MergeTable(int *table,int start,int end,int mid,int* temp) 2 { 3 //开始位置和中间位置的下标 4 int i_start = start; 5 int i_end = mid; 6 //中间位置和结束位置的下标 7 int j_start = mid + 1; 8 int j_end = end; 9 int length = 0; //用于表示辅助空间有多少个元素 10 //合并两个序列 11 while (i_start <= i_end&&j_start <= j_end) 12 { 13 if (table[i_start] < table[j_start]) 14 { 15 temp[length] = table[i_start]; 16 i_start++; 17 length++; 18 } 19 else 20 { 21 temp[length] = table[j_start]; 22 j_start++; 23 length++; 24 } 25 } 26 //遍历i这个序列 27 while (i_start <= i_end) //判断是否还有剩余的元素 28 { 29 temp[length] = table[i_start]; 30 i_start++; 31 length++; 32 } 33 //遍历j这个序列 34 while (j_start <= j_end) //判断是否还有剩余的元素 35 { 36 temp[length] = table[j_start]; 37 j_start++; 38 length++; 39 } 40 //辅助空间覆盖原空间 41 for (int i = 0; i < length; i++) 42 { 43 table[start + i] = temp[i]; 44 } 45 } 46 //拆分部分 47 void SplitTable(int *table, int start, int end,int *temp) //合并的结果放入temp中 48 { 49 if (start >= end) 50 { 51 return; 52 } 53 //拆分部分 54 int mid = (end + start) / 2; //取出数列的中间值 55 //左边拆分 56 guibin_table(table, start, mid,temp); 57 //右边拆分 58 guibin_table(table, mid + 1, end,temp); 59 //合并部分 60 heBinTable(table, start, end, mid, temp); 61 }
内容总结
以上是互联网集市为您收集整理的常见基础排序算法全部内容,希望文章能够帮你解决常见基础排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。