这几天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();
}
