这几天RIO喝多了，所以看这个排序算法超级亲切。它的原理也十分简单，还记得上一篇的冒泡排序吗，它的算法是单方向的冒泡，要是可以将算法设计成双向冒泡，那就是鸡尾酒排序啦。
具体做法是先从i【左边】开始把所有list[i]>list[i+1]的数交换，然后从j【右边】开始把所有list[j-1]<list[j]的数交换，这样双向冒泡，感觉舒服多了。
在代码实现上有一个可以优化的地方：要是没有发生交换，则说明这个元素之后【或之前】的数是排好序的，这时候只需要用一个shift值记录最近一次交换的位置，即可以确定left和right的位置。具体请君看代码吧^_

include<iostream>

include<vector>

using namespace std;

class ShakerSort{

private:
    int len;
    vector<int> list;
public:
    ShakerSort(vector<int> _list, int _len);
    void shaker_sort();
    void swap(int, int);
    void out();

};

ShakerSort::ShakerSort(vector<int> _list, int _len){

for(int i=0; i<_len; i++) list.push_back(_list[i]);
this->len = _len;

}

void ShakerSort::shaker_sort(){

int left  = 0;
int right = len-1;
int i;
int shift;

while(left<right){
    
    for(int i=left; i<right; i++){
        
        if(list[i]>list[i+1]) {
            swap(i, i+1);
            shift = i;
        }
    }       
    right = shift;
    
    for(int i=right; i>left; i--){
        
        if(list[i]<list[i-1]) {             
            swap(i, i-1);
            shift = i;
        };
    }
    left =shift;
}

}

void ShakerSort::swap(int a, int b){

int temp = list[a];
list[a]  = list[b];
list[b]  = temp;

}

void ShakerSort::out(){

for(int i=0; i<len; i++) cout<<list[i];

}

int main(){

int array[9] = {9,8,7,6,5,4,3,2,1};
vector<int> list;
for(int i=0; i<9; i++) list.push_back(array[i]);
ShakerSort mazhe(list, 9);
mazhe.shaker_sort();
mazhe.out(); 

}