- #include<iostream>
- #include<vector>
- using namespace std;
- template<typename EleType>
- inline void Swap(EleType &x, EleType &y)
- {
- EleType tmp;
- tmp = x;
- x = y;
- y = tmp;
- }
- //quick sort
- template<typename EleType>
- const EleType midOfThree(vector<EleType> &arr ,int left, int right)
- {
- int mid = left + (right - left)/2;
- if(arr[left] > arr[mid])
- Swap(arr[left], arr[mid]);
- if(arr[left] > arr [right])
- Swap(arr[left], arr[right]);
- if(arr[mid] > arr[right])
- swap(arr[mid], arr[right]);
- Swap(arr[mid], arr[right - 1]);
- return arr[right - 1];
- }
- template<typename EleType>
- void subQuickSort(vector<EleType> &arr, int left, int right)
- {
- int i, j;
- if (right - left > 5)
- {
- EleType pivot = midOfThree(arr, left, right);
- i = left; j = right - 1;
- for(;;)
- {
- while(arr[++i] < pivot) ;
- while(arr[--j] > pivot) ;
- if (i < j)
- Swap(arr[i],arr[j]);
- else
- break;
- }
- Swap(arr[i], arr[right - 1]);
- subQuickSort(arr, left, i - 1);
- subQuickSort(arr, i + 1, right);
- }
- else
- {
- for (i = left+1; i <= right; ++i)
- {
- EleType tmp = arr[i];
- for (j = i; j > left && arr[j-1] > tmp; --j)
- arr[j] = arr[j-1];
- arr[j] = tmp;
- }
- }
- }
- template<typename EleType>
- void quickSort(vector<EleType> &arr)
- {
- subQuickSort(arr, 0, arr.size()-1);
- }
- //select the first element as pivot.
- //programming is simple, but this algorithm may be O(n^2) complexity when input data is presort.
- template<typename EleType>
- void subFstPivQuickSort(vector<EleType> &arr, int left, int right)
- {
- if (left < right)
- {
- EleType pivot = arr[left];
- Swap(arr[left], arr[right]);
- int j = left;
- for (int i = left; i < right; ++i)
- {
- if(arr[i] < pivot)
- Swap(arr[i],arr[j++]);
- }
- Swap(arr[j], arr[right]);
- subFstPivQuickSort(arr, left, j-1);
- subFstPivQuickSort(arr, j+1, right);
- }
- }
- template<typename EleType>
- void fstPivQuickSort(vector<EleType> &arr)
- {
- subFstPivQuickSort(arr, 0, arr.size()-1);
- }
- int main()
- {
- int a[10] = {8,4,6,2,0,1,3,9,5,7};
- vector<int> x,y;
- vector<int>::size_type i;
- for (int idx = 0; idx < 10; idx++)
- x.push_back(a[idx]);
- y = x;
- for (i = 0; i< y.size(); ++i)
- cout<<y[i]<<' ';
- cout<<endl;
- quickSort(y);
- for (i = 0; i< y.size(); ++i)
- cout<<y[i]<<' ';
- cout<<'\\n';
- y = x;
- fstPivQuickSort(y);
- for (i = 0; i< y.size(); ++i)
- cout<<y[i]<<' ';
- cout<<endl;
- y = x;
- }
- //该片段来自于http://www.codesnippet.cn/detail/250420149387.html
来源: http://www.codesnippet.cn/detail/250420149387.html