本文最后更新于 390 天前，其中的信息可能已经有所发展或是发生改变。
排序算法
其实这些东西之前就写了，不过最近刚看了一点《++标准模板库编程实战》，里面写了一个通过迭代器实现排序的例子，就想着把我之前写的排序算法也都改为使用迭代器。不过修改的过程中也碰到了一些问题，比如怎么通过std::iterator_traits来提取变量类型（不过这应该是Cpp primer的内容，还是看得少了Orz）
测试用例
void unit_test()
{
auto restore = [&](int *x) {
x[0] = 12;
x[1] = 2;
x[2] = 16;
x[3] = 30;
x[4] = 8;
x[5] = 28;
x[6] = 4;
x[7] = 10;
x[8] = 20;
x[9] = 6;
x[10] = 18;
};
int array[11];
restore(array);
bubbleSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nBubble sort finished without error\n";
restore(array);
selectSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nSelect sort finished without error\n";
restore(array);
insertSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nInsertion sort finished without error\n";
restore(array);
shellSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nShell sort finished without error\n";
restore(array);
heapSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nHeap sort finished without error\n";
restore(array);
mergeSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nMerge sort finished without error\n";
restore(array);
quickSort(array, array + 11);
std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nQuick sort finished without error\n";
}
冒泡排序
template <typename RandomIter>
void bubbleSort(RandomIter start, RandomIter end)
{
bool sorted{false};
for (auto first = end; first > start; --first)
{
for (auto second = start + 1; second < first; ++second)
{
if (*second < *(second - 1))
{
std::swap(*(second - 1), *second);
sorted = true;
}
}
if (!sorted)
{
return;
}
}
}选择排序
template <typename RandomIter>
void selectSort(RandomIter start, RandomIter end)
{
for (auto first = start; first < end; ++first)
{
auto minPos = first;
for (auto second = first + 1; second < end; ++second)
{
if (*second < *minPos)
{
minPos = second;
}
}
std::swap(*first, *minPos);
}
}插入排序
template <typename RandomIter>
void insertSort(RandomIter start, RandomIter end)
{
typename std::iterator_traits<RandomIter>::value_type insertion;
for (auto first = start + 1; first < end; ++first)
{
insertion = *first;
auto second = first;
for (; second > start; --second)
{
if (*(second - 1) > insertion)
{
*second = *(second - 1);
}
// 没有交换就说明已经插入到了指定的位置
else
{
break;
}
}
*second = insertion;
}
}希尔排序
template <typename RandomIter>
void _ShellSort(RandomIter start, RandomIter end,
typename std::iterator_traits<RandomIter>::difference_type stride)
{
typename std::iterator_traits<RandomIter>::value_type insertion;
for (auto first = start + stride; first < end; first += stride)
{
insertion = *first;
auto second = first;
for (; second > start; second -= stride)
{
// 元素后移一位
if (*(second - stride) > insertion)
{
*second = *(second - stride);
}
// 没有交换就说明已经找到了指定的位置
else
{
break;
}
}
// 空出来的位置给插入的元素
*second = insertion;
}
}
template <typename RandomIter>
void shellSort(RandomIter start, RandomIter end)
{
typename std::iterator_traits<RandomIter>::difference_type stride = (end - start) / 2;
while (stride)
{
_ShellSort(start, end, stride);
stride /= 2;
}
}堆排序
template <typename RandomIter>
void _DownToMaxHeap(RandomIter start, RandomIter end, RandomIter pos)
{
auto parent = pos;
auto child = start + (parent - start) * 2 + 1;
/*调整begin位置的非叶子结点 --整个堆排序的核心代码块*/
while (child < end)
{
if (end - child > 1 && *child < *(child + 1))
{
++child;//右孩子节点
}
if (*child > *parent)
{
std::swap(*child, *parent);
}
else
{
break;
}
parent = child;
child = start + (parent - start) * 2 + 1;
}
}
template <typename RandomIter>
void _BuildMaxHeap(RandomIter start, RandomIter end)
{
if (end - start < 2)
{
return;
}
auto parent = start + (end - start) / 2 + 1;
while (parent >= start)
{
_DownToMaxHeap(start, end, parent);
--parent;
}
}
template <typename RandomIter>
void heapSort(RandomIter start, RandomIter end)
{
//构造最大堆
_BuildMaxHeap(start, end);
while (end > start)
{
std::swap(*start, *(--end));
_DownToMaxHeap(start, end, start);
}
}归并排序
template <typename RandomIter>
void _MergeSort(RandomIter start, RandomIter mid, RandomIter end)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
int length = static_cast<int>(end - start);
value_type *buffer = new value_type[length];
int ptr = 0;
auto lptr = start;
auto rptr = mid;
while (lptr < mid && rptr < end)
{
buffer[ptr++] = (*lptr < *rptr) ? *(lptr++): *(rptr++);
}
while (lptr < mid)
{
buffer[ptr++] = *(lptr++);
}
while (rptr < end)
{
buffer[ptr++] = *(rptr++);
}
for (int i = 0; i < length; ++i)
{
*(start++) = buffer[i];
}
delete buffer;
}
template <typename RandomIter>
void mergeSort(RandomIter start, RandomIter end)
{
//数组arr空or仅有一个元素则退出
if (end - start < 2)
{
return;
}
auto mid = start + (end - start) / 2;
mergeSort(start, mid);
mergeSort(mid, end);
_MergeSort(start, mid, end);
}快速排序
template <typename RandomIter>
RandomIter _getIndex(RandomIter start, RandomIter end)
{
auto pivotValue = *start;
while (start < end)
{
while (start < end && *(--end) > pivotValue);
*start = *end;
while (start < end && *(++start) < pivotValue);
*end = *start;
}
*start = pivotValue;
return start;
}
template <typename RandomIter>
void quickSort(RandomIter start, RandomIter end)
{
if (start < end)
{
auto pivot = _getIndex(start, end);
quickSort(start, pivot);
quickSort(pivot + 1, end);
}
}