|
发表于 10-6-2015 08:18 AM
|
显示全部楼层
- class Solution {
- public:
- void merge(stack<int>& s, int stride) {
- int sz = s.size();
- stack<int> tmp, res;
- for(int start = 0; start < sz; start += stride) {
- int end = min(start + stride - 1, sz - 1);
- int mid = min(start + (stride >> 1) - 1, sz - 1);
- int t = 0, f = start, i = mid + 1;
- for(f = start; f <= mid; f++) {
- res.push(s.top());
- s.pop();
- }
- for(f = start; f <= mid; f++) {
- tmp.push(res.top());
- res.pop();
- }
- for(i = start, f = mid + 1; i <= mid && f <= end;) {
- if(s.top() >= tmp.top()) {
- res.push(s.top());
- s.pop();
- f++;
- }
- else {
- res.push(tmp.top());
- tmp.pop();
- i++;
- }
- }
- while(i <= mid) {
- res.push(tmp.top());
- tmp.pop();
- i++;
- }
- while(f <= end) {
- res.push(s.top());
- s.pop();
- f++;
- }
- }
- while(!res.empty()) {
- s.push(res.top());
- res.pop();
- }
- }
- stack<int> sortStack(stack<int>& s) {
- int sz = s.size();
- int stride = 2;
- for(stride = 2; stride < sz; stride <<= 1) {
- merge(s, stride);
- }
- merge(s, stride);
- return s;
- }
- };
复制代码 |
|