這幾天RIO喝多了，所以看這個排序算法超級親切。它的原理也十分簡單，還記得上一篇的冒泡排序嗎，它的算法是單方向的冒泡，要是可以將算法設(shè)計成雙向冒泡，那就是雞尾酒排序啦。
具體做法是先從i【左邊】開始把所有l(wèi)ist[i]>list[i+1]的數(shù)交換，然后從j【右邊】開始把所有l(wèi)ist[j-1]<list[j]的數(shù)交換，這樣雙向冒泡，感覺舒服多了。
在代碼實現(xiàn)上有一個可以優(yōu)化的地方：要是沒有發(fā)生交換，則說明這個元素之后【或之前】的數(shù)是排好序的，這時候只需要用一個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(); 

}