主要参考：
交换
std::swap()可以直接使用，也可以自己实现：
template <class T>
void swap(const T& a, T const& b)
{
T temp = a;
a = b;
b = temp;
}
关于const，值得说明的是：
const T x;定义一个常量x，其值不可修改
const T* p;定义一个指针变量p，其指向对象*p不可修改，指针p可修改T const* p;与上等同T* const p = &var;定义一个指针变量p，其指向对象*p可修改，指针p不可修改const T* const p = &var;定义一个指针变量p，其指向对象*p和指针p都不可修改
const T& a = var定义一个引用变量a，其值不可修改T const& a = var与上等同T& const a = var无意义
bool empty() const;const修饰表明该成员函数不修改数据成员
冒泡排序
比较n-1趟，每趟比较n-i-1次，每次从头开始，大数逐次移到末尾. 下图是每次将小数移至最前端。
template<class T>
void BubbleSort(T* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
}
}
}
选择排序
减少交换次数，只操作下标
template<class T>
void selectSort(T* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (a[min] > a[j])
min = j;
}
if (min != i)
swap(a[i], a[min]);
}
}
插入排序
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
template<class T>
void insertSort(T* a, int n)
{
for (int right = 1; right < n; right++)
{
int left = right - 1;
T temp = a[right];
while (temp < a[left] and left >= 0)
{
a[left + 1] = a[left];
left--;
}
int middle = left + 1;
a[middle] = temp;
}
}
快速排序 ★★★
递归的排序算法，平均时间 O(nlogn) 性能是目前最好的，应用最广泛; 但需要工作栈存放递归调用的执行环境，平均栈深 O(logn)，是一种不稳定的排序算法.
快速排序 的思想----分治法非常实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
基本思想：（分治）
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
template<class T>
void quickSort(T* a, const int left, const int right)
{
if (left >= right) return; // 待排序数列只有一个元素时，结束递归
else
{
// 选枢轴
if (right - left == 1);
else
{ // 中值放在左侧
int middle = (left + right) / 2;
if (a[left] > a[middle])
swap(a[middle], a[left]);
if (a[middle] > a[right])
swap(a[middle], a[right]);
if (a[left] < a[middle])
swap(a[middle], a[left]);
}
int pivot = left;
// 一次划分
int i{ left }, j{ right + 1 };
while (i < j)
{
do i++; while (a[i] < a[pivot]); // 从左扫描
do j--; while (a[j] > a[pivot]); // 从右扫描
if (i < j) swap(a[i], a[j]);
}
swap(a[pivot], a[j]); // 最左侧为初始枢轴
pivot = j;
// 递归
quickSort(a, left, pivot - 1);
quickSort(a, pivot + 1, right);
}
}
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑引子：如何将2个有序数列合并？这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就比较下一个数，如果有数列为空，那直接将另一个数列的数据依次取出即可。
引子
以下是两个有序数组a[ ], b[ ]的归并排序（最简单）
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路是：将数组分成2组A，B，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了？可以将A，B组各自再分成2组。依次类推，当分出来的小组只有1个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了。这样通过先 递归 的分解数列，再合并数列就完成了归并排序。
- 递归式
// 一次归并排序, 输入为已排序数组 a[l,...,m] a[m+1,...,n]
template <class T>
void merge(T* a, const int l, const int m, const int n)
{
// 申请辅助空间
int length = n - l + 1;
assert(length > 1); // 消除C6386警告
T* temp = new T[length];
// 遍历等长元素
int i = l, j = m + 1, k = 0;
while (i <= m and j <= n)
{
if (a[i] <= a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
// 复制其余元素
copy(a + i, a + m + 1, temp + k);
copy(a + j, a + n + 1, temp + k);
// 释放辅助空间
copy(temp, temp + length, a + l);
delete[] temp;
}
template <class T>
void mergeSort(T* a, int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
- 迭代式
以下代码的缺点：频繁申请/释放内存
// 一次归并排序, 输入为已排序数组 a[l,...,m] a[m+1,...,n]
template <class T>
void merge(T* a, const int l, const int m, const int n)
{
// 申请辅助空间
int length = n - l + 1;
assert(length > 1); // 消除C6386警告
T* temp = new T[length];
// 遍历等长元素
int i = l, j = m + 1, k = 0;
while (i <= m and j <= n)
{
if (a[i] <= a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
// 复制其余元素
copy(a + i, a + m + 1, temp + k);
copy(a + j, a + n + 1, temp + k);
// 释放辅助空间
copy(temp, temp + length, a + l);
delete[] temp;
}
// 一趟归并排序
template <class T>
void mergePass(T* a, int n, int h)
{
int i= 1;
while (n - i + 1 >= 2 * h)
{
merge(a, i, i + h - 1, i + 2 * h - 1);
i += 2 * h;
}
if (n - i + 1 > h)
merge(a, i, i + h - 1, n);
else
;// do nothing
}
// 归并排序（迭代式）
template <class T>
void mergeSort(T* a, int n)
{
if (a == nullptr or n <= 0) return;
// 最初归并长度为1
for (int h = 1; h < n; h *= 2)
{
mergePass(a, n, h);
}
}
改进：只申请一次内存
// 一次归并排序, 输入为已排序数组 a[l,...,m] a[m+1,...,n]
template <class T>
void merge(T* a, T* result, const int l, const int m, const int n)
{
// 遍历等长元素
int i = l, j = m + 1, k = l;
while (i <= m and j <= n)
{
if (a[i] <= a[j])
{
result[k++] = a[i++];
}
else
{
result[k++] = a[j++];
}
}
// 复制其余元素
copy(a + i, a + m + 1, result + k);
copy(a + j, a + n + 1, result + k);
}
// 一趟归并排序
template <class T>
void mergePass(T* a, T* result, int n, int h)
{
int i = 1;
while (n - i + 1 >= 2 * h)
{
merge(a, result, i, i + h - 1, i + 2 * h - 1);
i += 2 * h;
}
if (n - i + 1 > h)
merge(a, result, i, i + h - 1, n);
else
copy(a + i, a + n + 1, result + i);
}
// 归并排序（迭代式）
template <class T>
void mergeSort(T* a, int n)
{
if (a == nullptr or n <= 0) return;
T* temp = new T[n + 1];
int h = 1; // 最初归并长度为1
while (h < n)
{
mergePass(a, temp, n, h);
h *= 2;
mergePass(temp, a, n, h);
h *= 2;
}
delete[] temp;
}
基数排序（桶、箱）
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶排序”（bucket sort）或“箱排序”（bin sort），顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序是建立在“箱排序”的基础上的。箱排序是创建数组
A[MaxValue]；然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。
.
存在的问题： 当序列中存在较大值时，BinSort 的排序方***浪费大量的空间开销。
基数排序是在BinSort的基础上，通过基数的限制来减少空间的开销。所谓基数，是指进制，十进制数列的基数为10，二进制为2，八进制为8.
可以用链表或者数组来构造“箱”，这里使用STL中的链表完成：
template<class T>
int maxdigit(const T a, int n)
{
int digits{ 1 }, ratio{ 10 };
for (int i = 0; i < n; ++i)
{
while (a[i] > ratio)
{
++digits;
ratio *= 10;
}
}
return digits;
}
template<class T>
void radixSort(T* a, int n)
{
std::list<T> bins[10]; // 十进制需要十个箱
int digits = maxdigit(a, n);
for (int d = 0, radix = 1; d < digits; ++d, radix *= 10)
{
// 将每个数放入对应箱中
for (int i = 0; i < n; ++i)
{
int index = (a[i] / radix) % 10;
bins[index].push_back(a[i]);
}
// 从10个箱中按顺序取出，每取一个就删除一个
for (int i = 0, j = 0; i < 10; ++i)
{
while (not bins[i].empty())
{
a[j++] = bins[i].front();
bins[i].pop_front();
}
}
}
}
京公网安备 11010502036488号