我是靠谱客的博主 悦耳含羞草，最近开发中收集的这篇文章主要介绍数据结构与算法（二）排序算法详解及实现：选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
目录
- 一、测试模板类
- 二、选择排序
- 三、插入排序
- 四、希尔排序
- 五、归并排序
- 5.1 自顶向下的归并排序
- 5.2 自下向上的归并排序
- 六、快速排序
- 七、堆排序
一、测试模板类
在学习排序算法的过程中，初步写了一个测试用的模板类，类的方法中包括排序的算法（待实现），类中目前只实现了小于比较和交换等基础的功能，源代码如下，后续会根据排序算法的不同，实现在模板类的排序方法里。
//sort1.h
#pragma once
#include <iostream>
template<class T>
class arrSort
{
public:
arrSort(T* arr1, int length, bool isSorted = false);
~arrSort() {};
bool less(int i, int j);
void exch(int i, int j);
void show() const;
void sort();
bool isSorted();
private:
T* arr;
int len;
bool isSort;
};
template<class T>
inline arrSort<T>::arrSort(T* arr1, int length, bool isSorted) :arr(arr1), len(length),isSort(isSorted) {};
template<class T>
bool arrSort<T>::less(int i, int j)
{
return arr[i] < arr[j] ? true : false;
}
template<class T>
void arrSort<T>::exch( int i, int j)
{
T temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
template<class T>
void arrSort<T>::show() const
{
using namespace std;
for (int i = 0; i < len; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
template<class T>
void arrSort<T>::sort()
{
//待实现
isSort = true;
}
template<class T>
bool arrSort <T>::isSorted()
{
return isSort;
}
//@author: px
//@time: 2021/01/30
//@description: 排序算法测试用模板类
#include "sort1.h"
int main()
{
using namespace std;
int num[] = { 1,3,4,2,8,5,2,1 };
arrSort<int> arr1(num, 8);
arr1.show();
arr1.exch(1, 2);
arr1.show();
cout << arr1.less(0, 5) << endl;
return 0;
}
二、选择排序
选择排序是初级排序算法中的一种， 其核心思想是首先找到数组中最小的那一个元素，然后将它和数组第一位元素交换位置，其次，找到数组倒数第二小的那个元素，再与数组第二位元素交换位置，如此进行下去，直到数组最后一位元素也完成操作，根据这个思想，代码实现如下：
template<class T>
void arrSort<T>::sort()
{
//选择排序实现
for (int i = 0; i < len; i++)
{
int minIndex = i;
//j从i+1往后开始查找即可。
for (int j = i + 1; j < len; j++)
{
//假如当前元素小于最小元素就将minIndex更新为当前元素的索引
if (less(j, minIndex))
{
minIndex = j;
}
exch(minIndex, i);
}
}
//将排序标志置1
isSort = true;
}
测试程序:
#include "sort1.h"
//获取长度
#define length(arr) sizeof(arr)/sizeof(arr[0])
int main()
{
using namespace std;
int num[] = { 1,3,4,2,8,5,2,1 };
arrSort<int> arr1(num, length(num));
arr1.show();
arr1.sort();
arr1.show();
return 0;
}
测试结果：
选择排序的特点是：
- 与输入无关，即使输入的是已经排好序的数组，执行的时间也不会缩短；
- 数据移动少，每次交换改变两个元素的值，因此选择排序用了len次交换，交换次数与数组大小是线性关系。
- 选择排序的时间复杂度是 O ( n 2 ) O(n^2 ) O(n2)级别的。
三、插入排序
插入排序的原理是，将数组中的元素插入到适当位置。这种方式像是人打扑克牌时候发牌阶段的处理方法，找出数组中较小的元素，逐步将其移动到合适的位置。
template<class T>
void arrSort<T>::sort()
{
//插入排序算法实现
for (int i = 0; i < len; i++)
{
//less(j, j - 1)判断是否较小的元素在较大元素的右边，
//有就交换至左边，然后通过内层的一次循环将这个较小的
//元素移动到合适的位置。
for (int j = i; j > 0 && less(j, j - 1); j--)
{
exch(j, j - 1);
}
}
//将排序标志置1
isSort = true;
}
测试结果
插入排序的特点：
- 运行时间和输入是有关的，适用于具有部分有序特点的数组，在这种情况下，只需要移动个别不在适当位置的元素即可获得有序数组，相较于选择排序，插入排序在这种情况下更快；
- 插入排序的时间复杂度也是 O ( n 2 ) O(n^2 ) O(n2)级别的。
四、希尔排序
插入排序每次交换相邻的元素来调整顺序，因此速度很慢，为了克服这一缺点，希尔排序交换不相邻的元素来对数组进行局部排序，最终用插入排序将局部有序的数组排序，源代码如下:
template<class T>
void arrSort<T>::sort()
{
//希尔排序算法实现
//确定合适的部分有序数组长度h
int h = 1;
while (h < len / 3)
{
//h递增序列的选择不唯一，且对结果有影响
h = h * 3 + 1;
}
//通过改变h来确定交换的距离
while (h >= 1)
{
for(int i = h;i<len;i++)
for (int j = i; j >= h && less(j,j-h); j--)
{
exch(j, j - h);
}
h = h / 3;
}
//将排序标志置1
isSort = true;
}
希尔排序特点：
- 权衡了数组的规模和有序性。
可以看出，希尔排序相较于插入排序，只是在插入排序外层多了一层调整 h 的while循环，这样就可以通过调整 h 的大小，使每次交换元素的距离变化，首先将 h 预设为一个较大的值，然后使用改变比较和交换距离为 h 后的插入排序来进行首次排序，使数组具有局部有序的特点，然后按照递增数列依次减小 h , 再进行插入排序，加强这一特点，直到完成排序，这样就可以利用插入排序针对局部有序数组效率高的优点。 - 希尔排序的时间复杂度为 O ( n 2 / 3 ) O(n^{2/3}) O(n2/3);
- 相较于选择排序和插入排序，希尔排序的实现难度并不高，且不需要额外的内存空间，当编程环境与硬件有关时，可以先考虑采用希尔排序。
五、归并排序
5.1 自顶向下的归并排序
自顶向下的归并排序使用了分治思想，将大的问题划分为小的问题，然后用小问题的答案来解决大问题，本小节中将自顶向下的归并排序简称为归并排序。
在归并排序里，最重要的步骤是归并，归并的意思是将两个有序的数组，合并成为一个有序的数组，在程序里，我们使用两个指针指向两个有序数组的首个元素，然后取两者中较小的元素作为下一个要放入合并后数组中的元素，然后将这个指针指向下一个元素，如此进行下去，直到两个数组中的元素都放入到合并数组中，就可以得到一个合起来的有序数组。当然, 除了这种情况之外,还存在两边某数组元素被取完的情况,总结起来有四种情况:
- 左边元素被取完, 此时应该取右边元素;
- 右边元素被取完, 此时应该取右边元素;
- 左边指针指向元素较小, 此时应该取左边元素;
- 右边指针指向元素较小或者两边指针指向元素相等,此时应该取右边元素。
为了更好地实现归并排序，在类中重写了show()函数，并将归并和排序两个步骤封装成了私有函数。归并排序源代码如下：
#pragma once
#include <iostream>
template<class T>
class arrSort
{
public:
arrSort(T* arr1, int length, bool isSorted = false);
~arrSort() {};
bool less(int i, int j);
void exch(int i, int j);
void show() const;
void show(int i, int j) const;
void sort();
bool isSorted();
private:
void merge(T* a, int low, int mid, int high); //归并，merge作为内部调用函数，不应该将接口暴露给用户。
void sort(T* a, int low, int high); //排序
private:
T* arr;
int len;
bool isSort;
};
template<class T>
inline arrSort<T>::arrSort(T* arr1, int length, bool isSorted) :arr(arr1), len(length),isSort(isSorted) {};
template<class T>
bool arrSort<T>::less(int i, int j)
{
return arr[i] < arr[j] ? true : false;
}
template<class T>
void arrSort<T>::exch( int i, int j)
{
T temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
template<class T>
void arrSort<T>::show() const
{
show(0, len-1);
}
template<class T>
void arrSort<T>::show(int low, int high) const
{
using namespace std;
for (int i = low; i <= high; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
//归并步骤实现
template<class T>
void arrSort<T>::merge(T* a,int low, int mid, int high)
{
std::cout << "merge:" << low << "-" << high <<'t';
int i = low;
int j = mid + 1;
//辅助数组复制原来数组的值，每一次归并时先将上一次归并的结果即arr的值复制到辅助数组a中
for (int k = low; k <= high; k++)
{
a[k] = arr[k];
std::cout << "a[" << k << "]:" << a[k];
std::cout << 't';
}
for (int k = low; k <= high; k++)
{
if (i > mid) //左边数组元素取完
arr[k] = a[j++];
else if (j > high) //右边数组元素取完
arr[k] = a[i++];
else if (a[i] < a[j]) //左边数组的元素较小，这里不能用less函数，因为比较的是在辅助数组中的元素！
arr[k] = a[i++];
else //右边数组的元素较小或两边元素相等
arr[k] = a[j++];
}
std::cout << "merge result: ";
show(low, high);
}
template<class T>
void arrSort<T>::sort(T* a, int low, int high)
{
std::cout << "sort:" << low << "-" << high << std::endl;
if (high <= low) //只有一个元素时
return;
int mid = low + (high - low) / 2;
sort(a, low, mid); //递归调用自身对左边继续归并排序
sort(a, mid + 1, high); //递归调用自身对右边继续归并排序
merge(a, low, mid, high);
}
template<class T>
void arrSort<T>::sort()
{
//归并排序算法实现
T* aux = new T[len]; //一次申请内存
sort(aux, 0, len - 1);
delete[] aux;
//将排序标志置1
isSort = true;
}
template<class T>
bool arrSort <T>::isSorted()
{
return isSort;
}
//sort1.cpp
#include "sort1.h"
//获取长度
#define length(arr) sizeof(arr)/sizeof(arr[0])
int main()
{
using namespace std;
int num[] = { 1,3,4,2,8,5,2,1 };
arrSort<int> arr1(num, length(num));
arr1.show();
arr1.sort();
arr1.show();
return 0;
}
结果如下图：
5.2 自下向上的归并排序
5.1节叙述的自顶向下的归并排序是将大的数组递归拆解成很小的数组（最后只有一个元素），然后进行归并，完成排序。而自下向上的归并排序的做法是先归并微型数组，然后将这些微型数组进行归并，直到将整个数组归并到一起。
源代码如下：
void arrSort<T>::merge(T* a,int low, int mid, int high)
{
std::cout << "merge:" << low << "-" << high <<'t';
int i = low;
int j = mid + 1;
//辅助数组复制原来数组的值，每一次归并时先将上一次归并的结果即arr的值复制到辅助数组a中
for (int k = low; k <= high; k++)
{
a[k] = arr[k];
std::cout << "a[" << k << "]:" << a[k];
std::cout << 't';
}
for (int k = low; k <= high; k++)
{
if (i > mid) //左边数组元素取完
arr[k] = a[j++];
else if (j > high) //右边数组元素取完
arr[k] = a[i++];
else if (a[i] < a[j]) //左边数组的元素较小，这里不能用less函数，因为比较的是在辅助数组中的元素！
arr[k] = a[i++];
else //右边数组的元素较小或两边元素相等
arr[k] = a[j++];
}
std::cout << "merge result: ";
show(low, high);
}
template<class T>
void arrSort<T>::sort()
{
//归并排序算法实现
T* aux = new T[len]; //一次申请内存
for (int sz = 1; sz < len; sz = 2 * sz) //sz为子数组的大小，外层循环调整每次归并子数组的长度
for (int low = 0; low < len - sz; low = low + 2 * sz) //low为子数组的索引,内层循环每次归并所有的子数组
{
merge(aux, low, low + sz - 1, (low + 2 * sz - 1) < (len - 1) ? (low + 2 * sz - 1) : (len - 1));
}
delete[] aux;
//将排序标志置1
isSort = true;
}
测试结果如下:
归并排序的特点：
- 时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)；
- 需要使用额外的空间，且与n成正比；
- 自下向上的归并排序适用于链表，对于链表只需要重新组织链表的链接就能原地排序了，不需要额外的空间。
六、快速排序
快速排序也体现了分治的思想，与归并排序不同的是，归并排序将数组分别分成两个子数组进行排序，并将有序的子数组归并来获得有序的整体数组，而快速排序认为当两个子数组有序时整个数组就是有序的。
归并排序和快速排序都体现了分治的思想，不过归并排序的递归调用发生在对数组处理(归并)之前，而快速排序的递归调用发生在对数组处理之后。
快速排序每次选择切分元素时应该是随机的，这里的实现中选择将原来的数组重新随机排列，然后选择数组的第一个元素为切分元素，另一种实现为不将原来的数组重新排列，而是在选择切分元素时随机选择。
源代码如下：
template<class T>
int arrSort<T>::partition(int low, int high)
{
int i = low + 1; //因为选取首元素作为切分元素，所以从第二个元素开始比较
int j = high;
T comp = arr[low]; //选取首元素作为切分元素
while (true)
{
while (arr[i] < comp) //i持续增长，直到找到比切分元素大的元素。
{
i++;
if (i == high)
break;
}
while (comp < arr[j]) //j持续减小，直到找到比切分元素小的元素。
{
j--;
if (j == low)
break;
}
if (i >= j) //两边指针相遇，说明比较完成
break;
exch(i, j); //找到了左边大于切分元素的索引与右边小于切分元素的索引，交换。
}
exch(low, j); //最后将切分元素放到左右两个数组中间。
return j;
}
template<class T>
void arrSort<T>::sort(int low, int high)
{
if (high <= low)
return;
int j = partition(low, high);
sort(low, j - 1);
sort(j+1, high);
}
template<class T>
void arrSort<T>::sort()
{
//快速排序算法实现
//首先打乱原来的数组，随机排序的数组可防止快速排序表现很差
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(arr, arr + len, std::default_random_engine(seed));
std::cout << "After shuffle: n";
show();
sort(0, len - 1);
//将排序标志置1
isSort = true;
}
快速排序结果：
快速排序的特点：
- 时间复杂度为 O ( n l g n ) O(nlgn) O(nlgn)，快速排序的时间复杂度最差为 O ( n 2 ) O(n^2) O(n2)，但是随机打乱数组可以避免这种情况；
- 原地排序；
七、堆排序
堆是一种数据结构，通常是一个可以被看做一棵完全二叉树的数组对象。当一个二叉树的每个结点都大于等于他的两个子结点时，被称为堆有序（注意：只要求父结点大于两个子结点，并不要求左子结点大于右子结点）。
堆是一种定义比较简单的数据结构，由于是完全二叉树，所以只用数组不用指针就可以表示了。
堆的性质如下：
- 对于不使用数组第一个位置的堆，一个结点k的父节点是k/2，它的两个子结点分别是2k和2k+1。
如何让一个无序的堆有序呢？考虑两个办法：
- 从左到右遍历数组，让每个结点与自己的父节点比较，如果子结点比较大就“上浮”，与父结点交换位置，一直比较下去，直到根节点；
- 从右至左遍历数组，让每个结点与自己的子结点比较，如果父节点较小就“下沉”，与子结点交换位置，直到叶结点。
“下沉”操作由于是针对各个子堆的父结点操作，因此只需要扫描数组的一半元素。
堆排序就建立在有序的堆之上，对于一个有序的堆，我们取出根结点（即最大的值），将根节点与数组的最后一个元素交换，即，将最大的值放到最后面，然后再对已经被换成数组尾元素的根节点执行“下沉”操作，将堆有序化。 依次执行下去，就能得到一个有序的数组。 源代码如下：
template<class T>
void arrSort<T>::sink(int k, int N) //将节点k下沉至堆中适当的节点
{
while (2 * k <= N)
{
int j = 2 * k; //左子节点
if (j < N && less(j, j + 1)) j++; //取左子节点和右子节点中的较大者
if (!less(k, j)) break; //判断父节点与自己的两个子节点的较大者哪个更小，如果父节点大于子节点就退出循环，否则执行交换
exch(k, j);
k = j;
}
}
template<class T>
void arrSort<T>::sort()
{
//堆排序算法实现
//第一步，创建最大堆，对于堆，前len/2个元素是每个子堆的根节点，因此这一步对每个子堆的根节点都下沉至合适的位置。
for (int k = len / 2; k >= 1; k--)
{
sink(k, len);
}
//第二步，将首节点（最大元素）与数组尾部元素交换，然后重新将堆有序化。
while (len > 1)
{
exch(1, len--);
sink(1, len);
}
//将排序标志置1
isSort = true;
}
最后
以上就是悦耳含羞草为你收集整理的数据结构与算法（二）排序算法详解及实现：选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序的全部内容，希望文章能够帮你解决数据结构与算法（二）排序算法详解及实现：选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复