- #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;
- }
- //select sort: simple select sort and heap sort
- //simple select sort
- template<typename EleType>
- void selectSort(vector<EleType> &arr)
- {
- vector<EleType>::size_type i, j, tmp;
- for(i = 0; i < arr.size(); ++i)
- {
- tmp = i;
- for (j = i+1; j < arr.size(); ++j)
- {
- if(arr[tmp] > arr[j])
- tmp = j;
- }
- if(tmp != i)
- Swap(arr[i], arr[tmp]);
- }
- }
- //heap sort
- template<typename EleType>
- void maxHeapPerDown(vector<EleType> &arr,typename vector<EleType>::size_type start,typename vector<EleType>::size_type end)
- {
- vector<EleType>::size_type i, child;
- EleType tmp;
- i = start;
- for (tmp = arr[i]; 2*i+1 < end; i = child)
- {
- child = 2*i+1;
- if (child +1 < end && arr[child] < arr[child +1])
- child++;
- if(tmp < arr[child])
- arr[i] = arr[child];
- else
- break;
- }
- arr[i] = tmp;
- }
- template<typename EleType>
- void heapSort(vector<EleType> &arr)
- {
- vector<EleType>::size_type i;
- for (i = arr.size()/2; i > 0 ; --i)
- {
- maxHeapPerDown(arr, i, arr.size());
- }
- maxHeapPerDown(arr, 0, arr.size());
- for (i = arr.size()-1; i > 0; --i)
- {
- Swap(arr[0],arr[i]);
- maxHeapPerDown(arr, 0, i);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/250420149356.html
来源: http://www.codesnippet.cn/detail/250420149356.html