快速排序法：（好土，感覺(jué)滿世界都會(huì)，不過(guò)還是寫一下，當(dāng)然了，標(biāo)準(zhǔn)庫(kù)里多的是排序算法），這里還是實(shí)現(xiàn)經(jīng)典版的快速排序了，時(shí)間復(fù)雜度O(nlogn)
Algorithms.h
#pragma once
#include <iostream>
class Algorithms
{
public:
Algorithms(void);
~Algorithms(void);
public:
template <typename T>
static void QuickSort(T* arr, size_t min, size_t max);
private:
template <typename T>
static size_t qsort_helper_partition(T* arr, size_t min, size_t max);
template <typename T>
static inline void swap(T* arr, size_t x, size_t y);
};
template <typename T>
void Algorithms::QuickSort(T* arr, size_t min, size_t max)
{
if(min >= max || max == 0 - 1) return;
size_t p = qsort_helper_partition(arr, min, max);
QuickSort(arr, min, p - 1);
QuickSort(arr, p + 1, max);
}
template <typename T>
size_t Algorithms::qsort_helper_partition(T* arr, size_t min, size_t max)
{
T cmp = arr[min];
int i = min + 1, j = max;
while(true)
{
while(cmp < arr[i])
++i;
while(arr[j] < cmp)
--j;
if(i >= j) break;
swap(arr, i, j);
}
swap(arr, min, j);
return j;
}
template <typename T>
void Algorithms::swap(T* arr, size_t x, size_t y)
{
T tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
用法：（順便有標(biāo)準(zhǔn)庫(kù)的排序法，當(dāng)然只是調(diào)一下，沒(méi)有什么可說(shuō)的了）
#include "Algorithms.h"
#include <iostream>
#include <vector>
#include <algorithm>
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {4, 8, 3, 7, 1, 5, 6, 2};
for(size_t i = 0; i != 8; ++i)
{
std::cout<<arr[i]<<" ";
}
std::cout<<std::endl;
Algorithms::QuickSort(arr,0, 7);
for(size_t i = 0; i != 8; ++i)
{
std::cout<<arr[i]<<" ";
}
std::cout<<std::endl;
std::vector<int> vec;
vec.push_back(3);
vec.push_back(1);
vec.push_back(4);
vec.push_back(1);
vec.push_back(7);
vec.push_back(6);
for(std::vector<int>::iterator iter = vec.begin();
iter != vec.end(); ++ iter)
{
std::cout<<*iter<<" ";
}
std::cout<<std::endl;
std::sort(vec.begin(), vec.end());
for(std::vector<int>::iterator iter = vec.begin();
iter != vec.end(); ++ iter)
{
std::cout<<*iter<<" ";
}
std::cout<<std::endl;
return 0;
}