简谈算法之选择排序

michael_llh

简谈算法之选择排序 [复制链接]

        我们在面试互联网企业的软件开发岗位的时候，必不可少的会考到算法和数据结构的知识，而且这部分的内容也是我们在大学课程里面会学习到的内容，当然是指相关专业。那么我们在这里很大家一起分享相关的软件算法类的知识，因为自己也是边学习边总结，如果有什么不对或者需要大家补充的希望我们可以多多讨论，完善内容，能够帮助都后面有需要学习这一块内容的同学。

       今天我们来聊一聊排序算法当中的一个例子，选择排序，选择排序是比较好理解的一个排序方法，属于简单类型的，我们具体看下算法的实现内容。

我们先通过语言描述一下整个过程：

       首先呢，从一个数组中找到最小的元素然后将其和第一个元素交换，这样实现第一个元素是最小的，然后第二次就是找出次小的元素和第二个元素交换，依次进行，直到交换到最后一个元素，整个排序过程完成。

       这个应该是比较好理解的，我们就不画图了，我们可以直接通过代码当中进行解释如何实现的。

       相信注释已经非常清楚了，所以这里就不在进行文字说明了哈。

1. <font size="3">#include <stdio.h>
   
2. 
   
3. // 类型重定义
   
4. typedef int Item;
   
5. // 宏定义了一个key
   
6. #define key(A) (A)
   
7. // 宏定义一个大小判断的宏
   
8. #define less(A, B) (key(A) < key(B))
   
9. // 交换两个数值大小的宏
   
10. #define exch(A, B) {Item t = A; A = B; B = t;}
    
11. // 判断大小，并进行交换的宏，
    
12. // 如果A大于B，两者进行交换
    
13. #define compexch(A, B) if(less(B, A)) exch(A, B)
    
14.         
    
15. // 选择排序实现，输入一个数组和数组长度
    
16. void choice_selection(Item a[], int length){
    
17.         int i , j;   // 定义两个临时变量
    
18.         for(i = 0; i < length; i++ ){
    
19.                 int min = i;  // 首先把数组的第一个数值认为是最小的
    
20.                 // 遍历剩下的所有元素，找到最小的那个，交换下标
    
21.                 for(j = i+1; j < length; j++){
    
22.                         // 如果a[j]小于a[min],则下标赋值为j
    
23.                         if(less(a[j],a[min])) min = j;
    
24.                 }               
    
25.                 // 最后是交换两个数值，我们找到的那个最小的数值和第i个数值交换
    
26.                 exch(a[i], a[min]);
    
27.         }        
    
28. }
    
29. 
    
30. // 这里重新写一个非宏定义版本的
    
31. void Choice_selection(Item a[], int length){
    
32.         int i, j;
    
33.         int temp = 0;
    
34.         for(i = 0; i < length; i++ ){
    
35.                 int min = i;  // 首先把数组的第一个数值认为是最小的
    
36.                 // 遍历剩下的所有元素，找到最小的那个，交换下标
    
37.                 for(j = i+1; j < length; j++){
    
38.                         // 如果a[j]小于a[min],则下标赋值为j
    
39.                         if(a[j] < a[min]) min = j;
    
40.                 }               
    
41.                 // 最后是交换两个数值，我们找到的那个最小的数值和第i个数值交换
    
42.                 temp = a[i];
    
43.                 a[i] = a[min];
    
44.                 a[min] = temp;
    
45.         }        
    
46. }
    
47. 
    
48. int main(void){
    
49.         // 测试数组
    
50.         Item array[] = {12 ,475 ,78 ,56 ,798 ,45 ,212 ,24, 65, 98};
    
51.         // 得到数组的长度
    
52.         int length = sizeof(array)/sizeof(Item);
    
53.         // 定义一个临时变量
    
54.         int i;
    
55.         // 打印输出前的数组
    
56.         for(i = 0;i < length; i ++){
    
57.                 printf("%d ",array[i]);
    
58.         }
    
59.         printf(".\n");
    
60.         // 选择排序
    
61.         Choice_selection(array ,length);
    
62.         // 打印输出后的数组
    
63.         for(i = 0;i < length; i ++){
    
64.                 printf("%d ",array[i]);
    
65.         }
    
66.         printf(".\n");
    
67.         return 0;
    
68. }</font>

复制代码

soso

谢谢分享，有你的一贯风格，脉络清晰哈

哼哼哈嘿丨墨染

感谢分享，讲的挺好如果把分享的脉络和链接贴出来就更好啦！！！~

RCSN

感谢分享，MAKE下。希望楼主多多分享

michael_llh

soso 发表于 2016-12-6 12:01
谢谢分享，有你的一贯风格，脉络清晰哈

恩呢！经历校招，总结一下这些内容！

michael_llh

哼哼哈嘿丨墨染 发表于 2016-12-6 14:49
感谢分享，讲的挺好如果把分享的脉络和链接贴出来就更好啦！！！~

链接是指汇总吗？

michael_llh

RCSN 发表于 2016-12-6 14:50
感谢分享，MAKE下。希望楼主多多分享

恩呢，也希望能够多多关注哈！

eric_wang

感谢分享