实现了算法导论第七章中的快速排序
quick_sort.h
#pragma once
/*************************************************
Author:董小歪
Date:2016-06-05
Description:算法导论第七章-快速排序-Cpp代码实现
**************************************************/
#ifndef QUICK_SORT_H
#define QUICK_SORT_H
#include <iostream>
#include <vector>
#include <random>
using namespace std;
template <typename T>
class MyQuickSort
{
public:
MyQuickSort(); //构造函数
MyQuickSort(const vector<T> _data); //构造函数
void QuickSort(int l, int r); //快排
void Randomized_QuickSort(int l, int r);//随机化版本快排
void Hoare_QuickSort(int l, int r); //Hoare版本快排·思考题7-1
void Hoare_QuickSort2(int l, int r); //Hoare版本快排·思考题7-1
void Tail_Recursive_QuickSort(int l, int r); //尾递归版本·思考题7-4
void print_data(); //打印数据
private:
vector<T> data; //数据
int partition(int l, int r); //数组的划分
int randomized_partition(int l, int r); //随机化版本
int Hoare_partition(int l, int r); //Hoare版本。7-1和书上有点不同。
int Hoare_partition2(int l, int r); //Hoare版本。7-1和书上有点不同。
};
template <typename T>
MyQuickSort<T>::MyQuickSort()
{
data = vector<T>();
}
template <typename T>
MyQuickSort<T>::MyQuickSort(const vector<T> _data)
{
data = _data;
}
template <typename T>
int MyQuickSort<T>::partition(int l, int r)
{
int x = data[r];
int i = l - 1;
for (int j = l; j < r; ++j)
{
if (data[j] <= x) //注意要等号加上去
{
++i;
swap(data[i], data[j]);
}
}
swap(data[r], data[i + 1]);
return i + 1;
}
template <typename T>
void MyQuickSort<T>::QuickSort(int l, int r)
{
if (l < r) //有两个元素以上
{
int m = partition(l, r);
QuickSort(l, m - 1);
QuickSort(m + 1, r);
}
}
template <typename T>
void MyQuickSort<T>::print_data()
{
for (auto var : data)
cout << var << " ";
cout << endl;
}
template <typename T>
int MyQuickSort<T>::randomized_partition(int l, int r)
{
uniform_int_distribution<unsigned> u(l, r);
default_random_engine e;
int i = u(e); //产生一个随机数的位置
swap(data[i], data[r]);
return partition(l, r);
}
template <typename T>
void MyQuickSort<T>::Randomized_QuickSort(int l, int r)
{
if (l < r)
{
int m = randomized_partition(l, r);
Randomized_QuickSort(l, m - 1);
Randomized_QuickSort(m + 1, r);
}
}
template <typename T>
int MyQuickSort<T>::Hoare_partition(int l, int r)
{
int x = data[l];
int i = l, j = r;
while (i < j)
{
while (i < j && data[j] > x)
--j;
data[i] = data[j];
while (i < j && data[i] < x)
++i;
data[j] = data[i];
}
data[i] = x;
return i; //最后i和j是相等的，所以返回i和j都一样
}
template <typename T>
int MyQuickSort<T>::Hoare_partition2(int l, int r)
{
int x = data[l];
int i = l, j = r + 1;
while (true)
{
do
{
--j;
} while (data[j] > x);
do
{
++i;
} while (data[i] < x);
if (i < j)
swap(data[i], data[j]);
else
break;
}
data[l] = data[j];
data[j] = x;
return j;
}
template <typename T>
void MyQuickSort<T>::Hoare_QuickSort(int l, int r)
{
if (l < r)
{
int m = Hoare_partition(l, r);
Hoare_QuickSort(l, m - 1);
Hoare_QuickSort(m + 1, r);
}
}
template <typename T>
void MyQuickSort<T>::Hoare_QuickSort2(int l, int r)
{
if (l < r)
{
int m = Hoare_partition2(l, r);
Hoare_QuickSort2(l, m - 1);
Hoare_QuickSort2(m + 1, r);
}
}
template <typename T>
void MyQuickSort<T>::Tail_Recursive_QuickSort(int l, int r)
{
while (l < r)
{
int m = partition(l, r);
Tail_Recursive_QuickSort(l, m - 1);
l = m + 1;
}
}
#endif // !QUICK_SORT_H
#pragma
