C语言选择排序算法的实现 - 简书
<div class="fixed-btn note-fixed-download" data-toggle="popover" data-placement="left" data-html="true" data-trigger="hover" data-content=''>
写了1512字，被16人关注，获得了27个喜欢
C语言选择排序算法的实现
原理：假定当前值外层循环变量i对应的数组元素为最小值，通过两个变量min和index分别暂存假定的最小值和最小值下标，通过内层for循环让i往后的所有元素与min进行进行比较，比较的过程中继续将最小值暂存在min中，将当前最小值对应的下标暂存在index中。一趟比较结束后判断最终的最小值与之前假定的最小值下标是否相同，如果不相同则交换两个值。下一趟外层循环继续从下一个开始于后续所有元素进行比较。每比较一趟，就少一个被比较的元素。因为上一次比较已经将最小值放在数组前面
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
被以下专题收入，发现更多相似内容：
非常棒的专题！每天都会收录精华文章，欢迎投稿，一起分享学习的喜悦。
· 1923人关注
作为开发者，只有不断学习才能让自己，才能走得更远！！
· 912人关注
分享移动开发技术、专题、干货。
· 814人关注
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
选择支付方式：C语言排序！
[问题点数：40分，结帖人ruying1389279]
C语言排序！
[问题点数：40分，结帖人ruying1389279]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。C语言基本功-选择排序法 - 懒猫爱飞的日志 -
电子工程世界-论坛
C语言基本功-选择排序法
热度 1已有 1241 次阅读 10:31
|个人分类:|
再温习一下第二种排序法，也是一种基本的排序法，选择排序法：算法原理（来源于网络，息懒得码字了，原理这东西理解就好^_^）:顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完再简单点,对着一群数组说,你们谁最小出列,站到最后边然后继续对剩余的无序数组说,你们谁最小出列,站到最后边再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了,从小到大举例先说看每步的状态变化,后边介绍细节,现有无序数组[6 2 4 1 5 9]第一趟找到最小数1,放到最前边(与首位数字交换)交换前:| 6 | 2 | 4 | 1 | 5 | 9 |交换后:| 1 | 2 | 4 | 6 | 5 | 9 |第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位交换前:| 1 | 2 | 4 | 6 | 5 | 9 |交换后:| 1 | 2 | 4 | 6 | 5 | 9 |第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置交换前:| 1 | 2 | 4 | 6 | 5 | 9 |交换后:| 1 | 2 | 4 | 5 | 6 | 9 |第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换排序完毕输出正确结果[1 2 4 5 6 9]第一趟找到最小数1的细节当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |先把6取出来,让它扮演最小数当前最小数6与其它数一一进行比较,发现更小数就交换角色当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较当前最小数2与4比较,不动当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较当前最小数1与5比较,不动当前最小数1与9比较,不动,到达末尾当前最小数1与当前首位数字进行位置交换,如下所示交换前:| 6 | 2 | 4 | 1 | 5 | 9 |交换后:| 1 | 2 | 4 | 6 | 5 | 9 |完成一趟排序,其余步骤类似下面是用C完成的实验，编译环境：Dev C++ 4.9.9.2,&编程语言：C/*& 基本思想：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。&基于此思想的算法主要有简单选择排序、树型选择排序和堆排序&&就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,*/#include &stdio.h&#include &stdlib.h&&&&&&& int test_tab[] = {0,4,9,5,7,1,3,9,6,4,5,6,7,7,8,8,1,0,3,2};// 选择排序法 void Selection_Sort(int *dat, int len){&&&& int i=0,j=0,temp=0;&&&& int index = 0;&&&& int n = 0;&&&& &&&& for(i=0;i&i++)&&&& {&&&&&&&&&&&& &&&&&& index =&&&&&& for(j=0;j&j++)&&&&&& {&&&&&&&& if(dat[index]&dat[j])&&&&&&&&&& index =&&&&&&&&&& &&&&&&&& if(index != i)&&&&&&&& {&&&&&&&&&& temp&& = dat[i];&&&&&&&&&& dat[i] = dat[index];&&&&&&&&&& dat[index] =&&&&&&&& &&&&&&&& } &&&&&&&& n++; &&&&&&& } &&&&&&&&&&&&&&&&&&&&&&&& &&&& } &&&& &&&& printf("总的循环次数是： %d \r\n",n);}// 主程序入口 int main(int argc, char *argv[]){& int i = 0;& int len = sizeof(test_tab)/sizeof(test_tab[0]);& & Selection_Sort(test_tab,sizeof(test_tab)/sizeof(test_tab[0]));& for(i=0;i&i++)&&& printf("%d ",test_tab[i]);&&& & system("PAUSE");&& return 0;}/////////////////////////////////////////////////////////////////////////////////////////////////这个算法理解起来也不是太难，主要是要懂原理最后，吼一下俺的口号：每天进步一点点，开心多一点^_^
作者的其他最新日志
评论 ( 个评论)
Powered byC语言常见的几个排序
发布时间： 9:15:31
编辑：www.fx114.net
本篇文章主要介绍了"C语言常见的几个排序"，主要涉及到C语言常见的几个排序方面的内容，对于C语言常见的几个排序感兴趣的同学可以参考一下。
#include "stdio.h"
void insersoft(int ch[],int len)& //插入排序{&& int i,j,&& for(i = 1; i & i++)&& {&&&& temp = ch[i];&&&& j = i-1;& while(j&=0 && temp&ch[j])& {&&&& ch[j+1] = ch[j];&&&& ch[j] =&&j--;& } && }}
void half_soft(int ch[],int len)&&& //二分法排序{&int low=0;&&int mid,i,j,&for(i = 1; i & i++)&&&& //一个一个的插入&{&&&&&& low = 0;&&& high = i-1;&&& temp = ch[i];&&&&&&&& //找到要插入的位置low&&& while(low &= high)&&& {&&& mid = (low +high)/2;&&& if(temp & ch[mid])&&& low = mid +1;&&& else&&& high = mid -1;&&&& }&&&&&& for(j = i-1; j &= j--)&&& {&&&&&& ch[j+1] = ch[j];&& //往后挪一个位置&&&& }&&& ch[low] =&}}
void selectsoft(int ch[], int len)&& //选择排序{& int i,j,& for(i = 0; i & len-1; i++)&& for(j = i+1; j & j++)&& {&&&&&& if(ch[i] & ch[j])&& //选择小的数据往前放&&& {&&&&&& temp = ch[j];&&& ch[j] = ch[i];&&& ch[i] =&&& &&& }&&&& && }}
void maopaosoft(int ch[], int len)&& //冒泡排序{&& int i,j,&& for(i = 0; i & i++)&&&& for(j= 0; j & len-i-1; j++)& {&& if(ch[j] & ch[j+1])&& //选择大的数据往后放&& {&&&&& temp = ch[j];&&&ch[j] = ch[j+1];&&&ch[j+1] =&& && }& }}
//快速排序方法1void quicksoft(int ch[], int low, int high)&& //快速排序{&& &&& int i,j,&i =&j =&temp = ch[low];& //& 暂时作为基准点&while(i & j)&{&&& while((i & j) && (temp & ch[j])) //在右边的只要比基点的大仍在右边&&& { &&&& j--;&& //向前移一位&&& }&&& if(i & j)&& //出现比基准点小的数，替换基准点的数&&& {&&&&&& ch[i] = ch[j];&&& i++;&& //右移一位&&& }&&&&&& while((i & j) && (temp & ch[i]))& //在左边的只要比基点的小仍在左边&&& {&&&& i++;& //右移一位&&& }&&& if(i & j)&& //出现比基准点大的数，填入原先比基点小的数的位置即j&&& {&&& ch[j] = ch[i];&&& j--;&&&& &&& }&}&ch[i] =
&if(low & i-1)&{&&& quicksoft(ch,low,i-1);&&& //前半部分在做快速排序&}&&&if(j+1 & high)&{&&&& quicksoft(ch,i+1,high);&&& //后半部分在做快速排序&}}
//快速排序方法2void quick_soft(int ch[], int left, int right){& int pos,temp,& int i = 0;& pos =& temp = ch[pos];
& for(i = 1; i &= i++)& {&&&& if(ch[i] & temp)&{&&& pos++;&&&&&& swap = ch[pos];&&& ch[pos] = ch[i];&&& ch[i] =&}& }& swap = ch[pos];& ch[pos] = ch[0];& ch[0] =&
&&& if(left & pos-1)&&& {& && quick_soft(ch,left,pos-1);&&& //前半部分在做快速排序&&& }& &&&&& if(pos+1 & right)&&& {& && quick_soft(ch,pos+1,right);&&& //后半部分在做快速排序&&& }& }
void shell_soft(int ch[], int len)& //希尔排序{&& int h,j,k,&& for(h = len/2; h & 0; h = h/2)& //控制增量&& {&&&&& for(j = j &j++)&&&&& //相当于分组&& {&&&& temp = ch[j];&&for(k = j-h;(k&=0 && temp & ch[k]); k -= h)& //对分组的数据进行排序&&{&&&& ch[k+h] = ch[k];&&}&&&& ch[k+h] =&& //这里k=k-h& 就是交换&& }& && }}
void main(){&&& int ch[10];&int i,num,temp,l;&puts("输入多少个数字：");&scanf("%d",&num);&puts("请输入一组数字：");&for(i = 0; i & i++)&{&&scanf("%d",&ch[i]);&}&//insersoft(ch,num);&//half_soft(ch,num);&//selectsoft(ch,num);&//maopaosoft(ch,num);&//quicksoft(ch,0,num-1);&//shell_soft(ch,num);&quick_soft(ch,0,num-1);&puts("排序结果为：");&for(i = 0; i & i++)&{&&printf("%5d",ch[i]);&}&printf("\n");}
管理员在日编辑了该文章文章。 -->
阅读(280) | 评论(0) | 转发(0) |
上一篇：const注意的几个事项
下一篇：拷贝构造函数遇到指针的问题
相关热门文章
网店不信用的时辰若何去营销推...
教你多少招不花钱做网店推广的...
C++函数中那些不可以被声明为...
农残检测仪：食品安全问题都是...
编写安全代码——小心有符号数...
使用openssl api进行加密解密...
一段自己打印自己的c程序...
sql relay的c++接口
ChinaUnix & ITPUB社区12周年...
ssh连接出现以下提示，求解...
如何扩展MYSQL
准备做一个大型门户,用户什么...
gbk or utf8
给主人留下些什么吧！~~
本文标题：
本页链接：查看: 1873|回复: 1
C语言算法：各种排序算法的实现
在学习算法的过程中，排序算法是很基础的。下面我用C语言实现了5中基础的排序算法：插入排序、选择排序、冒泡排序、并归排序、快速排序。1.&插入排序
插入排序很简单，在《算法导论》中的解释是这样的。插入排序的工作机理与很多人打牌时，整理手上的牌的做法差不多。开始的时候我们的左手是空的。接着我们从桌面上一张一张的摸牌，并将它放到左手的一个正确的位置上。为了找到这个正确的位置，要将它与左手的牌从右到左地进行比较，无论在什么
时候左手的牌都是排好序的。很简单吧,不过当初为了理解这个算法也花了一点时间，下面是C语言对插入排序的一个简单实现：
//插入排序
int insert_sort(int a[],int size)
& & int i,j,
& & for(i = 1;i &i++){
& && &&&temp = a;
& && &&&for(j = i-1;j &=0 && temp & a[j];j--)
& && && && &a[j+1] = a[j];
& && &&&a[j+1] =
& & return 0;
}//end insert_sort
2&.选择排序
选择排序的工作原理是这样的，对数据进行遍历，找出最小的元素（升序）作为第一个元素，再在剩下的数中找出最小的作为第二个元素，一直循环下去，最后的你会发现这个数组中的数据已经排好序了。下面是C语言的选择排序的一个简单实现：
//选择排序
int select_sort(int a[],int size)
& & int i,j,
& & for(i = 0;i &i++){
& && &&&for(j = i+1;j &j++)
& && && && &if(a & a[j]){
& && && && && & //交换位置
& && && && && & temp = a;
& && && && && & a = a[j];
& && && && && & a[j] =
& && && && &}
& & return 0;
}//end select_sort
3&.冒泡排序
冒泡排序是重复交换相邻的两个反序元素。它的工作工作机理我觉得跟选择排序差不多。因为在第一个遍历整个数组交换反序元素之后，数组的第一个元素
就已经是整个数组中最小的元素了。下面是C语言实现的一个冒泡排序。
//冒泡排序
int bubble_sort(int data[],int size)
& & int i,j,
& & for(i = 0;i &i++)
& && &&&for(j = size - 1;j &j--)
& && && && &if(data[j] & data[j-1]){
& && && && && & temp = data[j];
& && && && && & data[j] = data[j-1];
& && && && && & data[j-1] =
& && && && &}
}//end bubble_sort
4&.并归排序
并归排序，你也可以叫它合并排序。它采用了递归的思想，将数据分成两个部分，将这两个部分排好序之后再进行合并，一直重复这个过程，得出最后的结
果。可能说的比较抽象，大家看下面的代码。
//合并两个已经排好的结果
int merg_result(int data[],int start,int middle,int end)
& & int s1,s2,
& && &&&i,i1,i2;
& & s1 = middle-start+1;
& & s2 = end -
& & i1 = i2 = 0;
& & //两个临时的数组
& & int temp1[s1],temp2[s2];
& & //复制数据前后两个段的数据进临时数组
& & for(i = 0;i & s1;i++)
& && &&&temp1 = data[start+i];
& & for(i = 0;i & s2;i++)
& && &&&temp2 = data[middle+1+i];
& & //开始合并
& & for(i =i & s1+s2+i++){
& && &&&if(temp1[i1] & temp2[i2]){
& && && && &if(i1 &= s1)
& && && && && &//无法将两个临时数组的最后一个
元素设为无穷大
& && && && &data = temp1[i1++];
& && &&&else{
& && && && &if(i2 &= s2)
& && && && && &
& && && && &data = temp2[i2++];
& & //添加两个循环，将最后的数据合并好
& & while(i1 & s1)
& && &&&data[i++] = temp1[i1++];
& & while(i2 & s2)
& && &&&data[i++] = temp2[i2++];& && && && && && && && && && &
}//end merg_result
//并归排序
int merg_sort(int data[],int start,int end)
& & if(start & end){
& && &&&middle = (start+end)/2;
& && &&&//分治
& && &&&merg_sort(data,start,middle);
& && &&&merg_sort(data,middle+1,end);
& && &&&//合并结果
& && &&&merg_result(data,start,middle,end);
& & return 0;
}//end merg_sort
有两个函数，主例程将数组分成2个部分，然后递归调用自身，最后再调用合并函数合并最后的结果。
5&.快速排序
这是我觉得最神奇的一个。前面3个排序时间代价都是O(n2)，虽然并归排序的时间O(nlgn）。但是由于合并过程中需要的临时数组，使得它占用的栈空间相当大，在我的机子上（2G内存）排序50万的整形数据程序就会崩溃，内存不够了。而快速排序虽然也是递归的，但是它完全在本地工作，不需要申请额外的空间，所以很方便。下面是我用C语言写的一个快速排序的例程，
//合并两个已经排好的结果
int partition(int data[],int start,int end)
& & int key,
& && &&&i,j,
& & //选取最后一个元素作为主元素
& & key = data[end];
& & for(j =j &j++){
& && &&&if(data[j] &= key){
& && && && &//交换data[j]与data
& && && && &temp = data;
& && && && &data[i++] = data[j];
& && && && &data[j] =
& & //将主元素换到i位置
& & temp = data;
& & data = data[end];
& & data[end] =
& & //返回主元素的位置
& & //printf(&%d &,i);
}//end partition
//并归排序
int quick_sort(int data[],int start,int end)
& & if(start & end){
& && &&&middle = partition(data,start,end);
& && &&&quick_sort(data,start,middle-1);
& && &&&quick_sort(data,middle+1,end);
& & return 0;
}//end quick_sort
这只是我理解的快速排序一个很简单的实现。
上面的代码都是我在理解算法之后写出来的，当然可能有一些bug，如果你发现
了请联系我。：）
关于算法性能的分析，我实在不在行。在书上说的这几个算法性能上，前3个是O(n2）,后两个是O(nlgn)。说实话我对这些的理解不是很够。于是我自己写了一个测试程序在我的笔记本上跑了下。我的方式是随机生成数据，然后使用不同的排序算法进行测试，当然几百个数据几乎一瞬间就可以解出，所以我在测试的时候是对1000次（或者更多）排序的总时间进行统计。
通过统计结果，我发现插入排序在对于小量的数据，效果很好。但是在数据太大的时候就不能和并归排序和快速排序进行比较了。这个数据的间值在200左右。而快速排序不管是大数据还是小数据的效果都非常好，有些时候比插入排序还好。当然，这是我没有遇到传说中的坏数据，因为坏数据是有可能让快速排序的时间达到O(n2)的。
是我测试的结果，有一些我连续测了几次，结果都差不多。你可以看看。当然，你可能会看的眼花。
寒假过了这么久，在家看游戏设计方面的是内容。参考书是《windows游戏编程大师技巧》。终于会读取bmp位图了，并且还按照书上做了一个小动画。哈哈，过几天再把整理的一个内容发到博客上。快过年了，提前祝大家新年快乐！：
可以到我的博客来看看:
多谢分享哦
Powered by