`

经典算法——鸡尾酒排序(冒泡算法改良)

阅读更多

        搞开发的人都需要积累一些经典算法,以备不时之须。

        搞开发也有好几年了,积累的一些算法一直没做过整理,这段时间无聊就把这些算法整理以下,以备以后之用。  算法——————鸡尾酒排序

        问题

  有一数组,长度为n,把数组中的元素从小到大重新排列。

  说明

  鸡尾酒(cocktail)排序,又叫搅拌(shaker)排序。是改良的冒泡排序,冒泡排

  序可见另一篇文章经典算法之冒泡排序。

  思路

  鸡尾酒排序的过程为:(1)先对数组从左到右进行冒泡排序(升序),则最大的元

  素去到最右端;(2)再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左

  端。以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围。

  例如对45 ,19, 77, 81, 13, 28, 18, 19, 77进行排序

  从左到右:19,45,77,13,28,18,19,77,81

  从右到左:13,19,45,77,18,28,19,77,81

  从左到右:13,19,45,18,28,18,77,77,81

  从右到左:13,18,19,45,18,28,77,77,81

  从左到右:13,18,19,18,28,45,77,77,81

  从右到左:13,18,18,19,28,45,77,77,81

  这时不再发生交换,排序结束。

  具体实现:

package com.jack.arithmetic;

/**
 * 鸡尾酒排序
 * @author jack
 *
 */
public class CocktailSort {
 public static void main(String[] args) {
  int[] array = { 10, 3, 5, 31, 37, 5, 0, 9 }; 
  // 对数据排序 
  sort(array);
  for (int el : array) {
   System.out.print(el + " ");
  }
 }

 /**
  * 排序处理部分
  * @param array
  */
 static void sort(int[] array) {
  int top = array.length - 1;
  int bottom = 0;
  boolean flag = true;
  int i, j;
  while (flag) {
   flag = false;
   // 从小到大,升序
   for (i = bottom; i < top; i++) {
    if (array[i] > array[i + 1]) {
     swap(array, i, i + 1);
     flag = true;
    }
   }
   top--;
   // 从大到小,降序
   for (j = top; j > bottom; j--) {
    if (array[j] < array[j - 1]) {
     swap(array, j, j - 1);
     flag = true;
    }
   }
   bottom++;
  }
 }

 /**
  * 数据替换部分
  * @param array 给定的数组
  * @param i 代替换下标
  * @param j 替换部分下标
  */
 private static void swap(int[] array, int i, int j) {
  int tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
 }
}
排序结果:0 3 5 5 9 10 31 37

分享到:
评论

相关推荐

    冒泡排序改进算法 /鸡尾酒算法

    为了提高冒泡排序的效率,人们提出了多种改进算法,其中鸡尾酒排序(Cocktail Sort,又称双向冒泡排序)是一种常见的优化策略。 鸡尾酒排序的基本思想是在排序过程中,不仅从左向右进行比较和交换,还会从右向左...

    易语言鸡尾酒排序

    鸡尾酒排序,又称 bidirectional bubble sort 或 cocktail sort,是一种基于冒泡排序的优化算法。在冒泡排序中,元素是按照从最小到最大的顺序逐渐“浮”到数组的前端,而鸡尾酒排序则通过从一端到另一端来回遍历...

    java数据结构算法 冒泡 选择 鸡尾酒 插入 快速 排序算法

    本资源包涵盖了五种常见的排序算法:冒泡排序、选择排序、鸡尾酒排序(又称双向冒泡排序)、插入排序以及快速排序。这些排序算法在实际编程中有着广泛的应用,尤其是在处理大量数据时,了解并熟练掌握它们的原理和...

    算法-理论基础- 排序- 鸡尾酒排序(包含源程序).rar

    鸡尾酒排序,又称 bidirectional bubble sort 或者 cocktail sort,是一种变形的冒泡排序算法,因其在排序过程中,数据在数组两端来回扫动,如同调制鸡尾酒时酒液在杯中摇晃,故得此名。在这个压缩包文件中,你将...

    c++鸡尾酒排序算法yu

    鸡尾酒排序,也称为双向冒泡排序,是一种基于冒泡排序的优化算法。冒泡排序的基本思想是通过相邻元素之间的比较和交换,将较大的元素逐渐“冒”到数组的末尾。而鸡尾酒排序则在此基础上进行了改进,它不仅从左向右...

    经典算法的C#源码实现

    经典排序算法 - 鸡尾酒排序Cocktail sort 经典排序算法 - 希尔排序Shell sort 经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳...

    c#冒泡,选择,鸡尾酒,插入,希尔等排序方法

    本资源集成了五种经典的排序算法:冒泡排序、选择排序、鸡尾酒排序(也称作双向冒泡排序)、插入排序以及希尔排序。以下是对这些排序方法的详细说明: 1. **冒泡排序**: 冒泡排序是一种简单的排序算法,通过重复...

    十大基本排序,堆排序,归并排序,鸡尾酒排序,计数排序,基数排序等

    鸡尾酒排序是冒泡排序的一个变种,它不仅从左向右比较和交换相邻元素,还从右向左进行一次遍历。这种双向遍历的方式有助于减少数据的移动次数。 #### C++ 实现 `Cocktail`函数实现了鸡尾酒排序的基本逻辑。 ```...

    java交换排序之鸡尾酒排序实现方法

    鸡尾酒排序,又称定向冒泡排序、搅拌排序或涟漪排序,是冒泡排序的一种改进版。它的基本思想是从序列的一端开始,按照升序排列元素,然后从另一端开始,按照降序排列,如此反复,直到整个序列有序。这种排序方式类似...

    易语言鸡尾酒排序源码-易语言

    鸡尾酒排序,又称“震波排序”或“摇摆排序”,是一种变种的冒泡排序算法。在易语言中实现鸡尾酒排序,可以帮助初学者深入理解排序算法的原理和易语言编程技巧。易语言作为一款中国自主研发的编程语言,以其独特的...

    基于Python的冒泡排序算法详解与优化

    内容概要:本文详细介绍了冒泡排序算法的基本概念及其Python代码实现,重点解释了算法的基本步骤,以及常见的优化手段,如设置标志位和鸡尾酒排序。冒泡排序的时间复杂度为O(n²),适用于小规模的数据排序。 适用...

    C++经典排序算法,比较全的排序算法思想和实现

    还有一些不那么常见但有趣的排序算法,如鸡尾酒排序(Shaker Sort,又称双向冒泡排序)和二路归并排序(Two-Way Merge Sort),它们在特定场景下可能更有效或更具启发性。 5. **通用快速排序(Generic Quick Sort)...

    排序算法 各种算法的综合

    比如鸡尾酒排序(双向冒泡排序)或者插入排序的变体等,虽然效率可能低于O(N²),但它们的思路可能启发新的优化方法。 4. **通用快速排序**:这部分介绍了一个基于模板的快速排序实现,它可以对任何数据类型进行...

    c++冒泡排序,从小到大排序或者从大到小

    2. **双向冒泡排序**:即鸡尾酒排序,它结合了正向和反向冒泡,能够在一定程度上减少比较和交换的次数,提高效率。 3. **嵌入其他高效排序算法**:当数据规模超过一定阈值时,可以考虑使用快速排序、归并排序等更...

    算法,Python.zip

    O(n+k)来源维基百科鸡尾酒调酒器鸡尾酒摇床排序,也称为双向冒泡排序、鸡尾酒排序、摇床排序(也可以指选择排序的一种变体)、波纹排序、洗牌排序或穿梭排序,是冒泡排序的一种变体,既是一种稳定排序算法,也是一种...

    排序算法总结

    - 冒泡排序是最基础的交换排序算法,通过不断比较相邻元素并交换,使得每一轮遍历后最大的元素"冒"到数组末尾。 - 代码实现中的`bubbleSort`函数利用两个嵌套循环,如果发现相邻元素顺序错误则交换,如果一轮遍历...

    算法-理论基础- 排序- 原始冒泡排序(包含源程序).rar

    此外,也可以考虑采用变种算法如鸡尾酒排序,该算法不仅将元素向上冒泡,还会在数组的另一端进行下沉操作,从而稍微提高排序效率。 ### 结语 虽然冒泡排序在排序算法中并不高效,但它作为排序理论的基石,为我们...

    算法之排序专题 二分法排序等等

    例如,鸡尾酒排序(也叫双向冒泡排序)或选择排序等。 文章还预告了一个基于模板的通用快速排序实现,这个模板函数可以对任何数据类型进行排序,体现了C++模板的强大之处。 总的来说,排序算法的选择应根据实际...

Global site tag (gtag.js) - Google Analytics