对冒泡算法的优化

haocheng996

本人参考网上对冒泡算法的优化，再一次进行的小小优化，欢迎各位指点

1. void bubble4(uint16_t *arr, uint16_t length)
   
2. {
   
3.         uint16_t borden_right = length -1; //右边界初始值
   
4.         uint16_t borden_left  = 0;         //左边界初始值为
   
5.         uint16_t lastPos      = 0;         //记录右边界的值
   
6.         uint16_t prePos       = 0;         //记录左边界的值
   
7.     uint16_t temp;                     //交换的中间变量
   
8.         uint8_t  flag, i, j;               //是否有交换的标志     
   
9.    
   
10.    
    
11.         for(i = 0; i < length-1; i++)
    
12.     {
    
13.                 flag = 1;
    
14. 
    
15.                 //正向找出最大值
    
16.                 for( j = borden_left; j < borden_right; j++)
    
17.         {
    
18.                         if(arr[j] > arr[j+1])
    
19.             {
    
20.                 temp     = arr[j];
    
21.                 arr[j]   = arr[j+1];
    
22.                 arr[j+1] = temp;
    
23.                                 flag = 0;
    
24.                                 lastPos = j;
    
25.                         }
    
26.                 }
    
27.         
    
28.         //正向没发生交换就证明数组已经排好了
    
29.         if(flag)
    
30.         {
    
31.             break;
    
32.         }
    
33.         
    
34.         borden_right = lastPos;
    
35.    
    
36.                 //逆向找出最小值
    
37.                 for( j = borden_right; j > borden_left; j--)
    
38.         {
    
39.                         if(arr[j] < arr[j-1])
    
40.             {
    
41.                 temp     = arr[j];
    
42.                 arr[j]   = arr[j-1];
    
43.                 arr[j-1] = temp;
    
44.                                 flag = 0;
    
45.                                 prePos = j;
    
46.                         }
    
47.                 }
    
48. 
    
49.                 if(flag)
    
50.         {
    
51.                         break;
    
52.                 }
    
53.        
    
54.                 borden_left  = prePos;
    
55.         
    
56.         //每排序一次都把数组打印出来
    
57. //        for(j = 0; j < length; j++)
    
58. //        {
    
59. //            USART_SendData(USART1, arr[j]);
    
60. //            while(USART_GetFlagStatus(USART1, USART_FLAG_TC) == RESET);
    
61. //        }
    
62.         }
    
63. 
    
64. }

复制代码

stm1024

从时间复杂度上，你比原始的冒泡法系数还大一些？

奏奏奏

我觉得所谓优化，应该是有明确的对比参数数据的，比如执行时间消耗短了，占用RAM变小了……等等
如果楼主能提供这些数据，我觉得更好

jyl518-283289

直接上选择法吧

haocheng996

时间上会节省，但栈空间就要付出多一点，个人兴趣，实验数据就不发出来了

天臆弄人

你这没看出哪有优化，在网上看到过相似的算法, 你这改过的程序，CPU执行的过程，比你不改更花时间，除非是运算的百W级别数组

天臆弄人

你有没有测试过具体时间呢，比较下常规的和你改过在 1000个数组排列，耗时大小