最近在写一些数据结构以及算法相关的代码，比如常用排序算法以及具有启发能力的智能算法。为了能够让写下的代码下次还能够被复用，直接将代码编写成类模板成员函数的方式，之所以没有将这种方式改成更方便的函数模板纯属于偷懒，更方便于测试代码的有效性，等代码写完也懒得去改了。下面开始介绍这段代码，有什么不对的地方欢迎前来指正。
一共写了七种排序，插入排序InsertSort、堆排序HeapSort、快速排序QuickSort、合并排序MergeSort，计数排序CountingSort，基数排序RadixSort，桶排序BucketSort。排序思想都是根据<<Introduction to Algorithms>>而来的，所以对于这本书里面的时间复杂度都是严格遵从的，本文就不详细介绍这些算法的思想和实现机制了。针对于这七种排序，先写一个非特化的模板类Sort空着，是为了能够让模板的特化正确通过编译，接着写三个特化版本的Sort类，三个特化的版本分别接受T* vector<T>以及list<T>作为模板形参，而其中的各个成员函数接受的参数也是这些类型。函数体没有写的情况大致如下：
template<typename T>
class Sort
{ }; template<typename T>
class Sort<T*>
{
public:
void InsertSort(T* t, int length = )
{
} //the hardest part is to judge the correctness
void MergeSort(T* t, int length = )
{
} void HeapSort(T* t, int length = )
{
} void QuickSort(T* t, int length = )
{
} void CountingSort(T* t, int length = )
{
} void RadixSort(T* t, int length = )
{
} void BucketSort(T* t, int length = )
{
} template<typename T>
class Sort<std::vector<T>>
{
public:
void InsertSort(std::vector<T>& t)
{
} void HeapSort(std::vector<T>& t)
{
} void QuickSort(std::vector<T>& t)
{
} void CountingSort(std::vector<T>&t)
{
} void RadixSort(std::vector<T>& t)
{
} void BucketSort(std::vector<T>& t)
{
}
}; template<typename T>
class Sort<std::list<T>>
{
public:
void InsertSort(std::list<T>& t)
{
} void MergeSort(std::list<T>& t)
{
} void HeapSort(std::list<T>& t)
{
} void QuickSort(std::list<T>& t)
{
} void CountingSort(std::list<T>& t)
{
} void RadixSort(std::list<T>& t)
{
} void BucketSort(std::list<T>& t)
{
} };
对于编译期决定的类型T，基本数据类型之外，用户提供的自定义类只要重载了operator> operator< operator==...就能够直接使用这些函数。这是c++语言的特性，因为实现过程中使用了>和<来比较T，因此这个是需要的。对于T*版本的特化，因为数组本身就是通过下标运算来取得每个元素的，所以template<> Sort<T*>{}中的函数接受一个T类型指针和这个T类型数组的长度作为参数。
由于vector这个容器的是一段连续分配的地址（如果想了解的童鞋可以去看看STL源码剖析），因此vector重载了operator[]以及operator+, operator- 这些可以直接根据index索引到目标地址的对象。这样一来template<> Sort<std::vector<T>>{}中七种排序函数都可以跟template<> Sort<T*>{}中的函数几乎一模一样，可以直接通过operator[]来获取元素。但是从最开始我是希望编写可复用的程序的，因此效率问题在我的首要考虑范围之内。因为vector的operator[]一样也是通过iterator来获取元素的，所以在Sort类中首先尝试了直接使用iterator来取得元素,在Sort<vector<T>>中的InsertSort就是这样来实现的，从代码的可读性方面来说要差点。
而对于list容器来说，本身就是链式动态分配的内存，没有提供operator[]和operator+，operator-也是正常的，因此在Sort<list<T>>的函数实现中，没有办法使用t[i]这样的语法，因此针对list<T>的函数，一点也没有偷懒，都是使用iterator来实现的，与使用operator[]不同之处主要在于该iterator不能直接加上一个值，另一个就是iterator的边界条件比较麻烦，在iterator等于list的bigin()或者end()的时候，是不能够使用iterator--或者iterator++的，否则会触发list的断言。InsertSort算法的三种如下所示：
#include <vector>
#include <iostream>
#include <list>
#include <exception>
#include <iterator>
#include <math.h> template<typename T>
class Sort
{ }; template<typename T>
class Sort<T*>
{
public:
void InsertSort(T* t, int length = )
{
if (t == NULL)
{
std::cout << "are you fucking kidding me?";
}
else
{
//<<introduction to algorithm>> the array is from 1, we are from 0
for (int i = ; i<length; i++)
{
T temp = t[i];
int j = i - ;
while (j >= && t[j]>temp)
{
t[j + ] = t[j];
--j;
}
t[j + ] = temp;
}
}
}
}; #pragma region std::vector<T>
template<typename T>
class Sort<std::vector<T>>
{
public:
typedef typename std::vector<T>::iterator iterator;
public:
//actually vector use the operator[] should be faster
//the operator[] also used iterator
void InsertSort(std::vector<T>& t)
{
if (t.size()>)
{
for (std::vector<T>::iterator it = t.begin() + ; it != t.end(); it++)
{
std::vector<T>::iterator itFront = it - ;
T temp = *(it); while (*itFront > temp)
{
std::vector<T>::iterator itTemp = itFront;
itTemp++;
*itTemp = *itFront;
if (itFront != t.begin())
{
itFront--;
if (itFront == t.begin() && *itFront < temp)
{
itFront++;
break;
}
}
else
{
break;
}
}
*(itFront) = temp;
}
}
}
};
#pragma endregion #pragma region std::list<T>
template<typename T>
class Sort<std::list<T>>
{
//for the list, we can't directly use the operator+/-,because it is the list
//actually we can use the operator[] to change it, does list solved the problem?
//not effective at all
//we should support a method to increase or decrease the pointer(iterator)!
typedef typename std::list<T>::iterator iterator; public:
void InsertSort(std::list<T>& t)
{
for (std::list<T>::iterator it = t.begin(); it != t.end(); it++)
{
std::list<T>::iterator itFront = it;
if (++it == t.end())
{
break;
}
T temp = *it;
it--; while (*itFront > temp)
{
std::list<T>::iterator itTemp = itFront;
itTemp++;
*itTemp = *itFront;
if (itFront != t.begin())
{
itFront--;
if (itFront == t.begin() && *itFront < temp)
{
itFront++;
break;
}
}
else
{
break;
}
}
*itFront = temp;
}
} }; #pragma endregion
除了InsertSort之外的所有排序Sort<vector<T>>基本上都与T*相类似，而Sort<list<T>>则必须使用iteraotr来搞定。由于InsertSort是比较简单的插入排序，其效率也不是很高。除了这一种比较排序之外，还写了MergeSort，HeapSort以及QuickSort这三种比较算法。其中MergeSort和QuickSort都使用了分治的策略。而HeapSort则充分利用了数据结构来改善排序过程。这些思想在<<Introduction to Algrithms>>都十分详细。
除了上面的比较排序除外，还写了三种线性时间排序算法：CountingSort，RadixSort和BucketSort。这三种算法都是有其局限性的，因为CountingSort是通过输入数组的值来建立对应的计数数组，然后算出每个数对应的位置，因此输入数组的值必须是int类型才行，甚至还必须要是正数。同样的问题在RadixSort算法中也是存在的，而本模板稍微做了两点优化：一是使用c++的RTTI机制中的typeid方法来判断类型，只有是int类型才有下一步。二是解决CountingSort和RadixSort的负数和值过大过小问题，采用的方法是分割开正数和负数，针对不同类型的数再取其最大最小值，将最小值映射到0，而将最大值映射到max-min。就搞定了这个问题，稍微优化了一点空间。
对于BucketSort算法来说，完全利用的是数据结构的技巧来取得优势，三种特化的模板都是使用vector数组来实现的，本来是想要用双端链表来搞定的，这样效率高点，但是由于没有写针对于双端链表的sort算法，所以偷了回懒，直接用vector来搞定。这个算法也是最短的算法，思想也是最简单的。对于BucketSort算法的短板，就是搞不定除了基本数据类型之外的数据，因为还需要客户重载operator/，这个就比较麻烦了，估计很少有这个需求的用户类。
下面则是全部的代码：
#include <vector>
#include <iostream>
#include <list>
#include <exception>
#include <iterator>
#include <math.h> template<typename T>
class Sort
{ }; template<typename T>
class Sort<T*>
{
public:
void InsertSort(T* t, int length = )
{
if (t == NULL)
{
std::cout << "are you fucking kidding me?";
}
else
{
//<<introduction to algorithm>> the array is from 1, we are from 0
for (int i = ; i<length; i++)
{
T temp = t[i];
int j = i - ;
while (j >= && t[j]>temp)
{
t[j + ] = t[j];
--j;
}
t[j + ] = temp;
}
}
} //the hardest part is to judge the correctness
void MergeSort(T* t, int length = )
{
_MergeSort(t, , length - );
} void HeapSort(T* t, int length = )
{
try
{
if (length>)
{
length = length - ;
BuildHeap(t, length);
for (int i = length; i >= ; i--)
{
T temp = t[];
t[] = t[i];
t[i] = temp;
Max_Heapify(t, , i - );
}
}
}
catch (std::out_of_range e)
{
std::cout << "out_of_range error" << std::endl;
}
} void QuickSort(T* t, int length = )
{
_QuickSort(t, , length-);
} //this one can only work in integer, negetive value is also included
void CountingSort(T* t, int length = )
{
if (typeid(T) == typeid(int))
{
//one iterator to check the min, max, the number of negetive value
int count = ;
T* negetiveArray;
T* positiveArray;
//前一版本将比较的次数缩减到了3(n-2)/2次,但是行数太多
for (int i = ; i < length; i++)
{
if (t[i] < )
{
count++;
}
}
negetiveArray = new T[count];
positiveArray = new T[length - count];
//split the array into the postive and negetive value arrays
for (int i = , m = , n = ; i < length; i++)
{
if (t[i] < )
{
negetiveArray[m] = t[i];
m++;
}
else
{
positiveArray[n] = t[i];
n++;
}
}
T poMin = positiveArray[], poMax = positiveArray[];
T neMin = negetiveArray[], neMax = negetiveArray[];
for (int i = ; i < count; i++)
{
if (negetiveArray[i] < neMin)
{
neMin = negetiveArray[i];
}
if (negetiveArray[i] > neMax)
{
neMax = negetiveArray[i];
}
}
for (int i = ; i < length - count; i++)
{
if (positiveArray[i] < poMin)
{
poMin = positiveArray[i];
}
if (positiveArray[i] > poMax)
{
poMax = positiveArray[i];
}
}
//得到正负两个数组各自的最小最大差 并将两个数组映射到0-poMin;
T poMinux = poMax - poMin;
T neMinux = neMax - neMin; T* positiveArrayed = new T[length - count];
int* countArray = new int[poMinux + ];
memset(countArray, , (poMinux + )*sizeof(T)); for (int i = ; i < length - count; i++)
{
countArray[positiveArray[i] - poMin] ++;
//std::cout << countArray[i] << " ";
}
//此处与算法描述中不同的地方在于，countArray用于保存每个数存在的位置，但是该位置应该是从0开始的
for (int i = ; i <= poMinux; i++)
{
//std::cout << countArray[i - 1] << " ";
countArray[i] = countArray[i] + countArray[i - ];
countArray[i - ]--;
}
countArray[poMinux]--;
//将正数数组从后往前每一个数放到应该放的地方，之所以是从后往前是为了保持算法的稳定性
for (int i = length - count - ; i >= ; i--)
{
positiveArrayed[countArray[positiveArray[i] - poMin]] = positiveArray[i];
countArray[positiveArray[i] - poMin]--;
} //负值数组开始的地方
T* negetiveArrayed = new T[count];
int* countArrayNe = new int[neMinux + ];
memset(countArrayNe, , (neMinux + )*sizeof(T)); for (int i = ; i < count; i++)
{
countArrayNe[negetiveArray[i] - neMin]++;
}
for (int i = ; i <= neMinux; i++)
{
countArrayNe[i] += countArrayNe[i - ];
countArrayNe[i - ]--;
}
countArrayNe[neMinux]--; for (int i = count - ; i >= ; i--)
{
negetiveArrayed[countArrayNe[negetiveArray[i] - neMin]] = negetiveArray[i];
countArrayNe[negetiveArray[i] - neMin]--;
} //正负两个数组合并
for (int i = , j = ; i < length; i++)
{
if (i < count)
{
t[i] = negetiveArrayed[i];
}
else
{
t[i] = positiveArrayed[j];
j++;
}
} delete[] negetiveArray;
delete[] positiveArray;
delete[] countArray;
delete[] countArrayNe;
delete[] negetiveArrayed;
delete[] positiveArrayed;
}
else
{
std::cout << "you are using non-int type array for Counting Sort" << std::endl;
}
} void RadixSort(T* t, int length = )
{
int count = ;
for (int i = ; i < length; i++)
{
if (t[i] < )
{
count++;
}
}
T* positiveArray = new T[length - count];
T* negetiveArray = new T[count]; for (int i = , m=, n=; i < length; i++)
{
if (t[i] < )
{
negetiveArray[m] = -t[i];
m++;
}
else
{
positiveArray[n] = t[i];
n++;
}
}
_RadixSort(positiveArray, length - count);
_RadixSort(negetiveArray, count);
for (int i = , m=count-, n =; i < length; i++)
{
if (i < count)
{
t[i] = -negetiveArray[m];
m--;
}
else
{
t[i] = positiveArray[n];
n++;
}
}
} void BucketSort(T* t, int length = )
{
/*
this one does't like other linear time sorting, the basic type are all received for the parameter
and the class which supports operator[], operator - and operator > (< == ...).
*/
//if we achieve the algrithm with T*, it will need more time and space to judge the length of array's array
//struct, vector, list are all useful. this one is using the data structrue to decrease time; /*
The first version is using struct to construct the bucket, then i found that i did't finish the sort for the
linked list (sort by the pointer of a linked list)
*/ T max = t[], min = t[];
for (int i = ; i < length; i++)
{
if (t[i]>max)
{
max = t[i];
}
if (t[i] < min)
{
min = t[i];
}
}
int minux = max - min +;
//std::vector<std::vector<T>> colArray;
std::vector<T>* colArray = new std::vector<T>[length];
//std::vector<T> rawArray;
for (int i = ; i < length; i++)
{
int index = (t[i] - min)*length / minux;
std::vector<T> & rawArray = colArray[index];
rawArray.push_back(t[i]);
}
for (int i = ; i < length; i++)
{
std::vector<T>& rawArray = colArray[i];
Sort<std::vector<T>>::InsertSort(rawArray);
}
for (int i = , index=; i < length; i++)
{
std::vector<T> & rawArray = colArray[i];
//int j = 0;
for (std::vector<T>::iterator it = rawArray.begin(); it != rawArray.end(); it++)
{
t[index] = *it;
index++;
}
}
delete[] colArray;
} private:
void _MergeSort(T* t, int a, int b)
{
if (a<b)
{
int c = (a + b) / ;
_MergeSort(t, a, c);
_MergeSort(t, c + , b);
Merge(t, a, c, b);
}
} void Merge(T* t, int a, int c, int b)
{
int n1 = c - a + ;
int n2 = b - c;
//here to create the array dynamicly, remember to delete it;
T* temp1 = new T[n1 + ];
T* temp2 = new T[n2 + ]; for (int i = ; i<n1; i++)
{
temp1[i] = t[a + i];
}
//the biggest value of positive int
temp1[n1] = ;
for (int i = ; i<n2; i++)
{
temp2[i] = t[c + + i];
}
temp2[n2] = ; int m = , n = ;
for (int i = a; i <= b; i++)
{
if (temp1[m] <= temp2[n])
{
t[i] = temp1[m];
m++;
}
else if (temp1[m]>temp2[n])
{
t[i] = temp2[n];
n++;
}
}
//remember to clean it
delete[] temp1;
delete[] temp2;
} //i-root re-heap;
//abstract from the tree, but did not used tree;
void Max_Heapify(T* t, int i, int length)
{
int largest = ;
int l = GetLeftChild(i);
int r = GetRightChild(i); if (l <= length && t[i] <t[l])
{
largest = l;
}
else
{
largest = i;
} if (r <= length && t[largest] < t[r])
{
largest = r;
} if (largest != i)
{
T temp = t[i];
t[i] = t[largest];
t[largest] = temp;
Max_Heapify(t, largest, length);
}
} inline int GetLeftChild(int i)
{
return ((i + ) << ) - ;
} inline int GetRightChild(int i)
{
return (i + ) << ;
} void BuildHeap(T* t, int length)
{
//after the length/2, then it should not be the tree node
for (int i = length / ; i >= ; i--)
{
Max_Heapify(t, i, length);
}
} void _QuickSort(T* t, int a, int b)
{
if (a<b)
{
int s = Partition(t, a, b);
_QuickSort(t, a, s-);
_QuickSort(t, s + , b);
}
} int Partition(T* t, int a, int b)
{
T split = t[a];
//when the a equals b, a should be the split!
while (a < b)
{
while (t[b] >= split && a < b)
{
b--;
}
T temp = t[a];
t[a] = t[b];
t[b] = temp; while (t[a] <= split && a < b)
{
a++;
}
temp = t[a];
t[a] = t[b];
t[b] = temp;
}
return a;
} //get the index's number of t
inline int GetNIndex(int t, int i)
{
return (t%(int)pow(, i + ) - t%(int)pow(, i))/pow(,i);
} int* GetAllIndex(int t, int count)
{
int* array = new int[count];
memset(array, , count*sizeof(int));
int i = , sum = ;
while (t / pow(, i) > )
{
int temp = t%pow(, i + ) - sum;
sum += array[i];
array[i] = temp / pow(, i);
i++;
}
return array;
} void _RadixSort(T* t, int length = )
{
//对于多位数来说是count位数， 而对于扑克牌问题来说就是面值和花色了
T max = t[];
for (int i = ; i < length; i++)
{
if (max < t[i])
{
max = t[i];
}
}
int count = ;
//get the radix of max value;
int k = max / pow(, count);
while (k != )
{
count++;
k = max / pow(, count);
}
//int* array = new int[length*(count-1)];
//memset(array, 0, length*(count - 1)*sizeof(int)); int* positionArray = new int[length];
T* tempArray = new T[length];
//*************************************************
//change the codes more general for the problem of multi-decision sort
//using counting sort to solve every single problem;
for (int i = ; i < count; i++)
{
int* countArray = new int[];
memset(countArray, , * sizeof()); for (int j = ; j < length; j++)
{
positionArray[j] = GetNIndex(t[j], i);
}
//the t is changing with positionArray;
for (int m = ; m < length; m++)
{
countArray[positionArray[m]]++;
}
for (int m = ; m < ; m++)
{
countArray[m] += countArray[m - ];
countArray[m - ]--;
}
countArray[]--; for (int m = length - ; m >= ; m--)
{
//无论其他怎么改变 位置都是相对的 positionArray[m]就是t[m]
tempArray[countArray[positionArray[m]]] = t[m];
countArray[positionArray[m]]--;
}
for (int m = ; m < length; m++)
{
t[m] = tempArray[m];
}
delete[] countArray;
} delete[] positionArray;
delete[] tempArray;
}
}; #pragma region std::vector<T>
template<typename T>
class Sort<std::vector<T>>
{
public:
typedef typename std::vector<T>::iterator iterator;
public:
//actually vector use the operator[] should be faster
//the operator[] also used iterator
void InsertSort(std::vector<T>& t)
{
if (t.size()>)
{
for (std::vector<T>::iterator it = t.begin() + ; it != t.end(); it++)
{
std::vector<T>::iterator itFront = it - ;
T temp = *(it); while (*itFront > temp)
{
std::vector<T>::iterator itTemp = itFront;
itTemp++;
*itTemp = *itFront;
if (itFront != t.begin())
{
itFront--;
if (itFront == t.begin() && *itFront < temp)
{
itFront++;
break;
}
}
else
{
break;
}
}
*(itFront) = temp;
}
}
} void MergeSort(std::vector<T>& t)
{
int length = t.size();
if (length <= )
{
return;
}
else
{
_MergeSort(t, , length - );
}
} void HeapSort(std::vector<T>& t)
{
int length = t.size();
try
{
if (length>)
{
length = length - ;
BuildHeap(t, length);
for (int i = length; i >= ; i--)
{
T temp = t[];
t[] = t[i];
t[i] = temp;
Max_Heapify(t, , i - );
}
}
}
catch (std::out_of_range e)
{
std::cout << "out_of_range error" << std::endl;
}
} void QuickSort(std::vector<T>& t)
{
_QuickSort(t, , t.size() - );
} void CountingSort(std::vector<T>&t)
{
if (typeid(T) == typeid(int))
{
int length = t.size();
int count = ;
T* negetiveArray;
T* positiveArray;
//前一版本将比较的次数缩减到了3(n-2)/2次,但是行数太多
for (int i = ; i < length; i++)
{
if (t[i] < )
{
count++;
}
}
negetiveArray = new T[count];
positiveArray = new T[length - count];
//split the array into the postive and negetive value arraies
for (int i = , m = , n = ; i < length; i++)
{
if (t[i] < )
{
negetiveArray[m] = t[i];
m++;
}
else
{
positiveArray[n] = t[i];
n++;
}
}
T poMin = positiveArray[], poMax = positiveArray[];
T neMin = negetiveArray[], neMax = negetiveArray[];
for (int i = ; i < count; i++)
{
if (negetiveArray[i] < neMin)
{
neMin = negetiveArray[i];
}
if (negetiveArray[i] > neMax)
{
neMax = negetiveArray[i];
}
}
for (int i = ; i < length - count; i++)
{
if (positiveArray[i] < poMin)
{
poMin = positiveArray[i];
}
if (positiveArray[i] > poMax)
{
poMax = positiveArray[i];
}
}
//得到正负两个数组各自的最小最大差 并将两个数组映射到0-poMin;
T poMinux = poMax - poMin;
T neMinux = neMax - neMin; T* positiveArrayed = new T[length - count];
int* countArray = new int[poMinux + ];
memset(countArray, , (poMinux + )*sizeof(T)); for (int i = ; i < length - count; i++)
{
countArray[positiveArray[i] - poMin] ++;
//std::cout << countArray[i] << " ";
}
//此处与算法描述中不同的地方在于，countArray用于保存每个数存在的位置，但是该位置应该是从0开始的
for (int i = ; i <= poMinux; i++)
{
//std::cout << countArray[i - 1] << " ";
countArray[i] = countArray[i] + countArray[i - ];
countArray[i - ]--;
}
countArray[poMinux]--;
//将正数数组从后往前每一个数放到应该放的地方，之所以是从后往前是为了保持算法的稳定性
for (int i = length - count - ; i >= ; i--)
{
positiveArrayed[countArray[positiveArray[i] - poMin]] = positiveArray[i];
countArray[positiveArray[i] - poMin]--;
} //负值数组开始的地方
T* negetiveArrayed = new T[count];
int* countArrayNe = new int[neMinux + ];
memset(countArrayNe, , (neMinux + )*sizeof(T)); for (int i = ; i < count; i++)
{
countArrayNe[negetiveArray[i] - neMin]++;
}
for (int i = ; i <= neMinux; i++)
{
countArrayNe[i] += countArrayNe[i - ];
countArrayNe[i - ]--;
}
countArrayNe[neMinux]--; for (int i = count - ; i >= ; i--)
{
negetiveArrayed[countArrayNe[negetiveArray[i] - neMin]] = negetiveArray[i];
countArrayNe[negetiveArray[i] - neMin]--;
} //正负两个数组合并
for (int i = , j = ; i < length; i++)
{
if (i < count)
{
t[i] = negetiveArrayed[i];
}
else
{
t[i] = positiveArrayed[j];
j++;
}
} delete[] negetiveArray;
delete[] positiveArray;
delete[] countArray;
delete[] countArrayNe;
delete[] negetiveArrayed;
delete[] positiveArrayed;
}
else
{
std::cout << "you are using non-vector<int> type";
}
} void RadixSort(std::vector<T>& t)
{
std::vector<T> positiveArray;
std::vector<T> negetiveArray; for (iterator it = t.begin(); it != t.end(); it++)
{
if (*it < )
{
negetiveArray.push_back(-*it);
}
else
{
positiveArray.push_back(*it);
}
}
_RadixSort(positiveArray);
_RadixSort(negetiveArray);
int i = ;
iterator itNe;
if (negetiveArray.size() == )
{
itNe = negetiveArray.end();
}
else
{
itNe = --negetiveArray.end();
}
for (iterator it = t.begin(), itPo = positiveArray.begin(); it != t.end(); it++)
{
if (i < negetiveArray.size())
{
*it = -*itNe;
i++;
if (itNe != negetiveArray.begin())
{
itNe--;
}
}
else
{
*it = *itPo;
itPo++;
}
}
} void BucketSort(std::vector<T>& t)
{
int length = t.size();
T max = t[], min = t[];
for (int i = ; i < length; i++)
{
if (t[i]>max)
{
max = t[i];
}
if (t[i] < min)
{
min = t[i];
}
}
int minux = max - min + ;
std::vector<T>* colArray = new std::vector<T>[length];
for (iterator it = t.begin(); it != t.end(); it++)
{
int index = (*it - min)*length / minux;
colArray[index].push_back(*it);
}
for (int i = ; i < length; i++)
{
Sort<std::vector<T>>::InsertSort(colArray[i]);
}
for (int i = ; i < length; i++)
{
for (iterator it = colArray[i].begin(); it != colArray[i].end(); it++)
{
t[i] = *it;
}
}
delete[] colArray;
} private:
void _MergeSort(std::vector<T>& t, int a, int b)
{
if (a<b)
{
int c = (a + b) / ;
_MergeSort(t, a, c);
_MergeSort(t, c + , b);
Merge(t, a, c, b);
}
} void Merge(std::vector<T>& t, int a, int c, int b)
{
//actually the operator[] is also using the iterator! which one is more effective?
int n1 = c - a + ;
int n2 = b - c;
//here to create the array dynamicly, remember to delete it;
T* temp1 = new T[n1 + ];
T* temp2 = new T[n2 + ]; for (int i = ; i<n1; i++)
{
temp1[i] = t[a + i];
}
//the biggest value of positive int
temp1[n1] = ;
for (int i = ; i<n2; i++)
{
temp2[i] = t[c + + i];
}
temp2[n2] = ; int m = , n = ;
for (int i = a; i <= b; i++)
{
if (temp1[m] <= temp2[n])
{
t[i] = temp1[m];
m++;
}
else if (temp1[m]>temp2[n])
{
t[i] = temp2[n];
n++;
}
else
{ }
}
//remember to clean it
delete[] temp1;
delete[] temp2;
} int GetLeftChild(int i)
{
return (i + ) << - ;
} int GetRightChild(int i)
{
return (i + ) << ;
} void Max_Heapify(std::vector<T>& t, int i, int length)
{
int largest = ;
int l = GetLeftChild(i);
int r = GetRightChild(i); if (l<=length && t[l]>t[i])
{
largest = l;
}
else
{
largest = i;
} if (r<=length && t[r]>t[largest])
{
largest = r;
} if (largest != i)
{
T temp = t[i];
t[i] = t[largest];
t[largest] = temp;
Max_Heapify(t, largest, length);
}
} void BuildHeap(std::vector<T>& t, int length)
{
for (int i = length; i >= ; i--)
{
Max_Heapify(t, i, length);
}
} void _QuickSort(std::vector<T>& t, int a, int b)
{
if (a < b)
{
int s = Partition(t, a, b);
_QuickSort(t, a, s-);
_QuickSort(t, s + , b);
}
} int Partition(std::vector<T>& t, int a, int b)
{
T split = t[a];
while (a < b)
{
while (t[b] >= split && a < b)
{
b--;
}
T temp = t[a];
t[a] = t[b];
t[b] = temp; while (t[a] <= split && a < b)
{
a++;
}
temp = t[a];
t[a] = t[b];
t[b] = temp;
}
return a;
} inline int GetNIndex(int t, int i)
{
return (t % (int)pow(, i + ) - t % (int)pow(, i)) / pow(, i);
} void _RadixSort(std::vector<T>& t)
{
//对于多位数来说是count位数， 而对于扑克牌问题来说就是面值和花色了
T max = t[];
int length = t.size();
for (int i = ; i < length; i++)
{
if (max < t[i])
{
max = t[i];
}
}
int count = ;
//get the radix of max value;
int k = max / pow(, count);
while (k != )
{
count++;
k = max / pow(, count);
}
//int* array = new int[length*(count-1)];
//memset(array, 0, length*(count - 1)*sizeof(int)); int* positionArray = new int[length];
T* tempArray = new T[length];
//*************************************************
//change the codes more general for the problem of multi-decision sort
for (int i = ; i < count; i++)
{
int* countArray = new int[];
memset(countArray, , * sizeof()); for (int j = ; j < length; j++)
{
positionArray[j] = GetNIndex(t[j], i);
}
//the t is changing with positionArray;
for (int m = ; m < length; m++)
{
countArray[positionArray[m]]++;
}
for (int m = ; m < ; m++)
{
countArray[m] += countArray[m - ];
countArray[m - ]--;
}
countArray[]--; for (int m = length - ; m >= ; m--)
{
//无论其他怎么改变 位置都是相对的 positionArray[m]就是t[m]
tempArray[countArray[positionArray[m]]] = t[m];
countArray[positionArray[m]]--;
}
for (int m = ; m < length; m++)
{
t[m] = tempArray[m];
}
delete[] countArray;
} delete[] positionArray;
delete[] tempArray;
} };
#pragma endregion #pragma region std::list<T>
template<typename T>
class Sort<std::list<T>>
{
//for the list, we can't directly use the operator+/-,because it is the list
//actually we can use the operator[] to change it, does list solved the problem?
//not effective at all
//we should support a method to increase or decrease the pointer(iterator)!
typedef typename std::list<T>::iterator iterator; public:
void InsertSort(std::list<T>& t)
{
for (std::list<T>::iterator it = t.begin(); it != t.end(); it++)
{
std::list<T>::iterator itFront = it;
if (++it == t.end())
{
break;
}
T temp = *it;
it--; while (*itFront > temp)
{
std::list<T>::iterator itTemp = itFront;
itTemp++;
*itTemp = *itFront;
if (itFront != t.begin())
{
itFront--;
if (itFront == t.begin() && *itFront < temp)
{
itFront++;
break;
}
}
else
{
break;
}
}
*itFront = temp;
}
} void MergeSort(std::list<T>& t)
{
int length = t.size();
_MergeSort(t, , length - );
} void HeapSort(std::list<T>& t)
{
//the worst palce is to find the son of iterator, it will cost too much;
int length = t.size() - ;
BuildHeap(t);
iterator begin = t.begin();
iterator end = t.end();
end--;
for (int i = length; i >= ; i--)
{
T temp = *end;
*end = *begin;
*begin = temp;
MaxHeapify(t, begin, i - );
end--;
} } void QuickSort(std::list<T>& t)
{
_QuickSort(t, , t.size() - );
} void CountingSort(std::list<T>& t)
{
//偷天换日一回，将iterator操作变换成数组操作
if (typeid(T) == typeid(int))
{
int length = t.size();
int count = ;
T* positiveArray;
T* negetiveArray; iterator it;
for (it = t.begin(); it != t.end(); it++)
{
if (*it < )
{
count++;
}
}
positiveArray = new T[length-count];
negetiveArray = new T[count];
int m = , n = ;
for (it = t.begin(); it != t.end(); it++)
{
if (*it < )
{
negetiveArray[m] = *it;
m++;
}
else
{
positiveArray[n] = *it;
n++;
}
} T poMin = positiveArray[], poMax = positiveArray[];
T neMin = negetiveArray[], neMax = negetiveArray[]; for (int i = ; i < length - count; i++)
{
if (positiveArray[i]>poMax)
{
poMax = positiveArray[i];
}
if (positiveArray[i] < poMin)
{
poMin = positiveArray[i];
}
}
for (int i = ; i <count; i++)
{
if (negetiveArray[i]>neMax)
{
neMax = negetiveArray[i];
}
if (negetiveArray[i] < neMin)
{
neMin = negetiveArray[i];
}
}
T poMinux = poMax - poMin;
T neMinux = neMax - neMin; //positive array
T* positiveArrayed = new T[length - count];
T* countArrayPo = new T[poMinux + ];
memset(countArrayPo, , (poMinux + )*sizeof(T)); for (int i = ; i < length - count; i++)
{
countArrayPo[positiveArray[i]-poMin]++;
}
for (int i = ; i <= poMinux; i++)
{
countArrayPo[i] += countArrayPo[i - ];
countArrayPo[i - ]--;
}
countArrayPo[poMinux]--;
for (int i = length - count - ; i >= ; i--)
{
positiveArrayed[countArrayPo[positiveArray[i] - poMin]] = positiveArray[i];
countArrayPo[positiveArray[i] - poMin]--;
}
//negetive value
T* negetiveArrayed = new T[count];
T* countArrayNe = new T[neMinux + ];
memset(countArrayNe, , (neMinux + )*sizeof(T));
for (int i = ; i < count; i++)
{
countArrayNe[negetiveArray[i] - neMin]++;
}
for (int i = ; i <= neMinux; i++)
{
countArrayNe[i] += countArrayNe[i - ];
countArrayNe[i]--;
}
countArrayNe[neMinux]--;
for (int i = count - ; i >= ; i--)
{
negetiveArrayed[countArrayNe[negetiveArray[i] - neMin]] = negetiveArray[i];
countArrayNe[negetiveArray[i] - neMin]--;
}
//gather two arraies
m = , n = ;
for (it = t.begin(); it != t.end(); it++)
{
if (m < count)
{
*it = negetiveArrayed[m];
m++;
}
else
{
*it = positiveArrayed[n];
n++;
} } delete[] positiveArray;
delete[] negetiveArray;
delete[] countArrayPo;
delete[] countArrayNe;
delete[] positiveArrayed;
delete[] negetiveArrayed;
}
else
{
std::cout << "you are using non-list<int> type\n";
}
} void RadixSort(std::list<T>& t)
{
std::list<T> positiveArray;
std::list<T> negetiveArray; for (iterator it = t.begin(); it != t.end(); it++)
{
if (*it < )
{
negetiveArray.push_back(-*it);
}
else
{
positiveArray.push_back(*it);
}
}
_RadixSort(positiveArray);
_RadixSort(negetiveArray);
int i = ;
iterator itNe;
if (negetiveArray.size() == )
{
itNe = negetiveArray.end();
}
else
{
itNe = --negetiveArray.end();
}
for (iterator it = t.begin(), itPo = positiveArray.begin(); it != t.end(); it++)
{
if (i < negetiveArray.size())
{
*it = -*itNe;
i++;
if (itNe != negetiveArray.begin())
{
itNe--;
}
}
else
{
*it = *itPo;
itPo++;
}
}
} void BucketSort(std::list<T>& t)
{
int length = t.size();
T max = *(t.begin()), min = *(t.begin());
for (iterator it = t.begin(); it != t.end(); it++)
{
if (*it > max)
{
max = *it;
}
if (*it < min)
{
min = *it;
}
}
int minux = max - min+;
std::vector<T>* colArray = new std::vector<T>[length];
for (iterator it = t.begin(); it != t.end(); it++)
{
int index = (*it - min)*length / minux;
colArray[index].push_back(*it);
}
for (int i = ; i < length; i++)
{
Sort<std::vector<T>> s;
s.InsertSort(colArray[i]);
}
int m = ;
//the border condition annoys me a lot!
for (iterator it = t.begin(); it != t.end(); m++)
{
for (std::vector<T>::iterator itCol = colArray[m].begin(); itCol != colArray[m].end(); itCol++)
{
*it = *itCol;
it++;
}
}
} private:
void _MergeSort(std::list<T>& t, int a, int b)
{
if (a<b)
{
int c = (a + b) / ;
_MergeSort(t, a, c);
_MergeSort(t, c + , b); std::list<T>::iterator ita = t.begin();
std::list<T>::iterator itc = t.begin();
std::list<T>::iterator itb = t.begin();
for (int i = ; i <= b; i++)
{
if (i<a)
{
ita++;
}
if (i<c)
{
itc++;
}
if (i<b)
{
itb++;
}
}
Merge(t, ita, itc, itb);
} } //Here we can't directly use the std::list<T>::iterator, use the typedef to replace it
//compiler of ms
void Merge(std::list<T>& t, iterator a, iterator c, iterator b)
{
std::list<T> temp1;
std::list<T>::iterator nothing = ++c;
c--;
for (std::list<T>::iterator it = a; it != nothing; it++)
{
temp1.push_back(*it);
}
temp1.push_back();
std::list<T> temp2;
std::list<T>::iterator something = ++b;
b--;
for (std::list<T>::iterator it = nothing; it != something; it++)
{
temp2.push_back(*it);
}
temp2.push_back(); std::list<T>::iterator itTemp1 = temp1.begin();
std::list<T>::iterator itTemp2 = temp2.begin();
for (std::list<T>::iterator it = a; it != something; it++)
{
if (*itTemp1 > *itTemp2)
{
*it = *itTemp2;
itTemp2++;
}
else
{
*it = *itTemp1;
itTemp1++;
}
}
} iterator IteratorIncrease(std::list<T>& t, iterator it,int i)
{
iterator tempIt = it;
for (int index = ; index < i; index++)
{
if (tempIt == t.end()--)
{
return t.end();
}
tempIt++;
}
return tempIt;
} iterator IteratorDecrese(std::list<T>& t, iterator it, int i)
{
iterator tempIt = it;
for (int index = ; index < i; i++)
{
if (tempIt == t.begin())
{
std::cout << "out of range with iterator in decrese";
return t.end();
}
else
{
tempIt--;
}
}
return tempIt;
} int GetIteratorPosition(std::list<T>& t, iterator it)
{
int position = -;
iterator tempIt = t.begin();
for (tempIt; tempIt != t.end(); tempIt++)
{
position++;
if (tempIt == it)
{
break;
}
}
if (position >= t.size())
{
return -;
}
return position;
} int GetLeftChild(std::list<T>& t, iterator it)
{
int number = -;
iterator tempIt;
for (tempIt = t.begin(); tempIt != t.end(); tempIt++)
{
number++;
if (tempIt == it)
{
break;
}
}
if (number >= t.size())
{
//the it is not one of the t'iterator;
return NULL;
} int leftChild = ((number + ) << ) - ;
return leftChild;
} int GetRightChild(std::list<T>& t, iterator it)
{
int number = -;
iterator tempIt;
for (tempIt = t.begin(); tempIt != t.end(); tempIt++)
{
number++;
if (tempIt == it)
{
break;
}
}
if (number >= t.size())
{
//the it is not one of the t'iterator;
return NULL;
} int RightChild = (number + ) << ;
return RightChild;
} void MaxHeapify(std::list<T>& t, iterator it, int length)
{
//iterator tempIt = IteratorIncrease(t, t.begin(), length);
int leftChild = GetLeftChild(t, it);
int rightChild = GetRightChild(t, it);
int i = GetIteratorPosition(t, it); iterator itLeft = IteratorIncrease(t, t.begin(), leftChild);
iterator itRight = IteratorIncrease(t, t.begin(), rightChild); int largest = ;
T tLargest;
if (leftChild <= length && *itLeft > *it)
{
largest = leftChild;
tLargest = *itLeft;
}
else
{
largest = i;
tLargest = *it;
} if (rightChild <= length && *itRight > tLargest)
{
largest = rightChild;
tLargest = *itRight;
} if (largest != i)
{
T temp = *it;
*it = tLargest; if (largest == leftChild)
{
*itLeft = temp;
MaxHeapify(t, itLeft, length);
}
else
{
*itRight = temp;
MaxHeapify(t, itRight, length);
}
}
} void BuildHeap(std::list<T>& t)
{
for (int i = (t.size() - ) / ; i >= ; i--)
{
iterator temp = IteratorIncrease(t, t.begin(), i);
MaxHeapify(t, temp, t.size()-);
}
} void _QuickSort(std::list<T>& t, int a, int b)
{
if (a < b)
{
int s = Partition(t, a, b);
_QuickSort(t, a, s - );
_QuickSort(t, s + , b);
}
} int Partition(std::list<T>& t, int a, int b)
{
iterator l = IteratorIncrease(t, t.begin(), a);
iterator r = IteratorIncrease(t, t.begin(), b); T split = *l;
while (a < b && l != t.end() && r != t.end())
{
while (a<b && *r>split)
{
b--;
r--;
}
T temp = *r;
*r = *l;
*l = temp; while (a<b && *l < split)
{
a++;
l++;
}
temp = *l;
*l = *r;
*r = temp;
}
return a;
} inline int GetNIndex(int t, int i)
{
return (t % (int)pow(, i + ) - t % (int)pow(, i)) / pow(, i);
} void _RadixSort(std::list<T>& t)
{
int length = t.size();
if (length == )
{
return;
}
T max = *t.begin();
int count = ;
for (iterator it = t.begin(); it != t.end(); it++)
{
if (*it > max)
{
max = *it;
}
}
int k = max / pow(, count);
while (k != )
{
count++;
k = max / pow(, count);
} T* tempArray = new int[length];
for (int i = ; i < count; i++)
{
int* positionArray = new int[length];
int* countArray = new int[];
memset(countArray, , * sizeof(int)); iterator it = t.begin();
for (int j = ; j < length; j++)
{
positionArray[j] = GetNIndex(*it, i);
it++;
} for (int m = ; m < length; m++)
{
countArray[positionArray[m]]++;
}
for (int m = ; m < ; m++)
{
countArray[m] += countArray[m - ];
countArray[m - ]--;
}
countArray[]--;
//
it = --t.end();
for (int m = length - ; m >= ; m--)
{
tempArray[countArray[positionArray[m]]] = *it;
countArray[positionArray[m]]--;
if (it != t.begin())
{
it--;
}
}
int m = ;
for (it = t.begin(); it != t.end(); it++)
{
*it = tempArray[m];
m++;
}
delete[] positionArray;
delete[] countArray;
}
delete[] tempArray;
}
}; #pragma endregion
过段时间再贴上树这种树(非二叉树)结构的模板，其格式也会向标准模板靠齐，基本功能已经具有，但是还不够强大，远没有达到通用的标准。其存储结构是孩子兄弟存储法，针对树的前序遍历已经写好。