1. #include <iostream>
    2. #include <vector>
    3. #include <ctime>
    5. #define THOUSAND 1000
    7. using namespace std;
    9. // 常规冒泡,逐步把最大的放在尾端
    10. void sortByBubbing1_0(vector<int> &arr)
    11. {
    12.     int size = arr.size();
    13.     // 1_0的优化，加入了isChange参数
    14.     bool isChange = false;
    15.     for (int j = 1; j < size; j++)
    16.     {
    17.         for(int i = 0; i < size-j; i++)
    18.         {
    19.             if (arr[i]>arr[i+1])
    20.             {
    21.                 swap(arr[i],arr[i+1]);
    22.                 isChange = true;
    23.             }
    24.         }
    25.         if (!isChange) break;
    26.     }
    27. }
    29. // 记录交换的位置，下一次就不用从头开始了
    30. void sortByBubbing1_1(vector<int> &arr)
    31. {
    32.     int size = arr.size();
    33.     //    int i, sum = 0;
    34.     int p = -1;
    35.     for (int j = 1; j < size; j++)
    36.     {
    37.         int first = 0;
    38.         int iStart = (p < 2) ? 0 : p-1;
    39.         p = -1;
    40.         for (int i = iStart; i < size-j; i++)
    41.         {
    42.             if (arr[i]>arr[i+1])
    43.             {
    44.                 if (first == 0)
    45.                 {
    46.                     p = i;
    47.                     ++first;
    48.                 }
    49.                 swap(arr[i],arr[i+1]);
    50.             }
    51.         }
    52.         if (p < 0) break;
    53.     }
    54. }
    56. // 双向冒泡排序(也称鸡尾酒冒泡)
    57. void sortByBubbing1_2(vector<int> &arr)
    58. {
    59.     int size = arr.size();
    60.     bool isChange = false;
    61.     for (int i = 1;i < size; ++i)
    62.     {
    63.         if (i & 1 == 1)
    64.         {
    65.             for (int j = i/2; j < size - i/2 - 1; ++j)
    66.             {
    67.                 if (arr[j] > arr[j+1])
    68.                 {
    69.                     swap(arr[j],arr[j+1]);
    70.                     isChange = true;
    71.                 }
    72.             }
    73.         } else {
    74.             for (int j = size - i/2 - 1; j > 0; --j)
    75.             {
    76.                 if (arr[j] < arr[j-1])
    77.                 {
    78.                     swap(arr[j],arr[j-1]);
    79.                     isChange = true;
    80.                 }
    81.             }
    82.         }
    83.         if (!isChange) break;
    84.     }
    85. }
    87. // 双向冒泡排序优化，用了1_2的方法进行优化
    88. void sortByBubbing1_3(vector<int> &arr)
    89. {
    90.     int size = arr.size();
    91.     int p = -1;
    92.     for (int i = 1;i < size; ++i)
    93.     {
    94.         if (i & 1 == 1)
    95.         {
    96.             // 因为p-2至少得大于初始值才有意义
    97.             int jStart = (p < 2 + i/2) ? i/2 : p - 2;
    98.             p = -1;
    99.             for (int j = jStart; j < size - i/2 -1; ++j)
    100.             {
    101.                 if (arr[j] > arr[j+1])
    102.                 {
    103.                     swap(arr[j],arr[j+1]);
    104.                     p = j;
    105.                 }
    106.             }
    107.         } else {
    108.             // 因为p+2至少得小于初始值才有意义
    109.             int jStart = (p < size - i/2 + 1) ? size - i/2 -1 : p + 2;
    110.             p = -1;
    111.             for (int j = jStart; j > 0; --j)
    112.             {
    113.                 if (arr[j] < arr[j-1])
    114.                 {
    115.                     swap(arr[j],arr[j-1]);
    116.                     p = j;
    117.                 }
    118.             }
    119.         }
    120.         if (p < 0) break;
    121.     }
    122. }
    124. int main()
    125. {
    126.     srand((unsigned)time(NULL));
    127.     vector<int> arr = {1,2,3,4,5,6,7,8,9,0,10,11,12,13,14,15,16,17,18,22,33,44,55,66,77,88,99,100,89};
    128.     clock_t start = clock();
    129.     for (int q=0;q<THOUSAND*THOUSAND*2;++q)
    130.     {
    131.         // 这个就是我们之前学到的洗牌算法了
    132.         for (int i=arr.size()-1; i > 0 ;--i)
    133.         {
    134.             swap(arr[i],arr[rand()%(i+1)]);
    135.         }
    136.         // 这里选择执行的函数
    137.         sortByBubbing1_0(arr);
    138.     }
    140.     clock_t end = clock();
    141.     double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    142.     cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    144.     // 查看排序的正确性
    145.         for (int i = 0; i < arr.size(); ++i)
    146.         {
    147.             cout << "a[" <<i<<"]="<< arr[i] << endl;
    148.         }
    149.     return 0;
    150. }

    每个函数执行若干遍后发现，鸡尾酒排序对比普通冒泡来说，不但代码多，而且执行效率也是一样的，可见其在随机输入的情况下是没有优势的。

    对比两种算法，冒泡将最大值不断向右侧堆叠。而鸡尾酒将依次将最大和最小往两边堆叠，所谓鸡尾酒的优点在2,3,4,5,6,1少执行几次遍历，但如5,6,1,2,3,4或4,5,6,1,2,3，鸡尾酒排序又得多排几次。

    既然宏观上两者效率差不多，而且两者本质一样，那么一方面的优点一定会被另一方面的缺点，也不存在鸡尾酒是冒泡的升级版的说法，希望学习时能有独立思想不要人云亦云。

    点击关注，持续推送质量好文；如有不当，欢迎指出；转载请注明出处。