排序算法总结

今天在复习了以前的笔记,发现我有很多遗忘又很重要的知识点。

排序算法,我自己明白的:1、冒泡排序算法。2、选择排序算法。其中选择排序算法又分为数组和链表的。3、STL函数中的sort()函数调用(最简便的。。。)

首先明白选择排序算法和冒泡排序算法的区别:(选自度娘

冒泡算法,每次比较如果zhi发现较小的元素在后面,就交换两个相邻的元素。

而选择排序算法的改进在于:先并不急于调换位置,先从A[1]开始逐个检查,看哪个数最小就记下该数所在的位置P,等一躺扫描完毕,再把A[P]和A[1]对调,这时A[1]到A[10]中最小的数据就换到了最前面的位置。

所以,选择排序每扫描一遍数组,只需要一次真正的交换,而冒泡可能需要很多次。比较的次数一样的。

 

数组的方法..

 1 //选择法排序(以数组实现)
 2 int main()
 3 {
 4     int arr[10] = { 0 };
 5     int n = sizeof(arr) / sizeof(arr[0]);
 6     int i = 0, j = 0, min = 0;
 7 
 8     printf("请输入%d个int数据\n", n);
 9     for (i = 0; i < n-1; i++)
10     {
11         for (min = i, j = min + 1; j < n; j++)
12         {
13             if (arr[min] > arr[j])
14                 min = j;
15         }
16 
17         if (min != i)
18         {
19             int tmp = 0;
20             tmp = arr[i];
21             arr[i] = arr[min];
22             arr[min] = tmp;
23         }
24     }
25 
26     for (i = 0; i < n; i++)
27     {
28         printf("%d", arr[i]);
29     }
30     printf("\n");
31 
32     return 0;
33 }

 

 

 链表的方法...

 

 

 

 

 

 1 void sort_link(STU *head)
 2 {
 3     //1、判断链表是否存在
 4     if(NULL == head)
 5     {
 6         printf("link not found\n");
 7         return;
 8     }
 9     else
10     {
11         STU *p_i = head;//i=0 
12         while(p_i->next != NULL)//i<n-1  外层循环
13         {
14             STU *p_min = p_i;//min = i;
15             STU *p_j = p_min->next;//j = min+1
16             while(p_j != NULL)//j<n  内层循环
17             {
18                 
19                 //寻找成员num最小值的 节点
20                 if(p_min->num > p_j->num)//if(arr[min] > arr[j])
21                     p_min = p_j;//min = j
22                 p_j = p_j->next;//j++
23             
24             }
25 
26             if(p_min != p_i)//min != i
27             {
28                 //只交换数据域(1、节点内容整体交换   2、只交换指针域)
29                 //1、节点内容整体交换(数据域交换第1次   指针域交换第1次)
30                 STU tmp;
31                 tmp = *p_i;
32                 *p_i = *p_min;
33                 *p_min = tmp;
34 
35                 //2、只交换指针域(指针域交换第2次)
36                 tmp.next = p_i->next;
37                 p_i->next = p_min->next;
38                 p_min->next = tmp.next;
39             }
40 
41 
42             p_i = p_i->next;//i++
43         }
44         
45     }
46     
47 }

最后还有一个STL库里的sort()函数。把数字存到容器里就可用...