鸡尾酒排序的C++程序-yiteyi-C++库

鸡尾酒类是气泡排序。气泡排序算法总是从左侧遍历元素，并在第一次迭代中将最大元素移动到其正确位置，在第二次迭代中将第二大元素移动到其正确位置，以此类推。鸡尾酒排序交替地在两个方向上遍历给定数组。

null

算法： 算法的每次迭代分为两个阶段：

第一阶段从左到右循环数组，就像气泡排序一样。在循环过程中，将比较相邻项，如果左侧的值大于右侧的值，则交换值。在第一次迭代结束时，最大数量将驻留在数组的末尾。
第二阶段以相反的方向在数组中循环——从最近排序的项之前的项开始，然后返回到数组的开头。在这里，还将比较相邻的项目，并在需要时进行交换。

CPP

                         // C++ implementation of Cocktail Sort                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Sorts array a[0..n-1] using Cocktail sort                       
                         void                                     CocktailSort(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 bool                                     swapped =                                     true                                     ;                       
                                                 int                                     start = 0;                       
                                                 int                                     end = n - 1;                       
           
                                                 while                                     (swapped) {                       
                                                 // reset the swapped flag on entering                       
                                                 // the loop, because it might be true from                       
                                                 // a previous iteration.                       
                                                 swapped =                                     false                                     ;                       
           
                                                 // loop from left to right same as                       
                                                 // the bubble sort                       
                                                 for                                     (                                     int                                     i = start; i < end; ++i) {                       
                                                 if                                     (a[i] > a[i + 1]) {                       
                                                 swap(a[i], a[i + 1]);                       
                                                 swapped =                                     true                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // if nothing moved, then array is sorted.                       
                                                 if                                     (!swapped)                       
                                                 break                                     ;                       
           
                                                 // otherwise, reset the swapped flag so that it                       
                                                 // can be used in the next stage                       
                                                 swapped =                                     false                                     ;                       
           
                                                 // move the end point back by one, because                       
                                                 // item at the end is in its rightful spot                       
                                                 --end;                       
           
                                                 // from right to left, doing the                       
                                                 // same comparison as in the previous stage                       
                                                 for                                     (                                     int                                     i = end - 1; i >= start; --i) {                       
                                                 if                                     (a[i] > a[i + 1]) {                       
                                                 swap(a[i], a[i + 1]);                       
                                                 swapped =                                     true                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // increase the starting point, because                       
                                                 // the last stage would have moved the next                       
                                                 // smallest number to its rightful spot.                       
                                                 ++start;                       
                                                 }                       
                         }                       
           
                         /* Prints the array */                       
                         void                                     printArray(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 printf                                     ("%d ", a[i]);                       
                                                 printf                                     ("");                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 5, 1, 4, 2, 8, 0, 2 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 CocktailSort(arr, n);                       
                                                 printf                                     ("Sorted array :");                       
                                                 printArray(arr, n);                       
                                                 return                                     0;                       
                         }                       

输出：

Sorted array :0 1 2 2 4 5 8

请参阅完整的文章鸡尾酒类更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章