【数据结构与算法篇】八种排序 (C++实现)
多种排序算法的Cpp实现
- 一. 排序的概念及其运用
- 排序的概念
- 二. 一图速览常见排序
- 三. 排序的C++实现
- 1> 直接插入排序
- 2> 希尔排序
- 希尔排序代码实现(希尔所实现)
- 希尔排序代码实现(优化版)
- 3> 选择排序
- 选择排序的代码实现(同时选出最大和最小的元素)
- 4> 堆排序
- 堆排序的代码实现
- 5> 冒泡排序
- 6> 快速排序
- 快速排序(递归版)
- 快速排序(迭代版)
- 7> 归并排序
- 归并排序(递归版)
- 归并排序(迭代版)
- 8> 基数排序
一. 排序的概念及其运用
排序的概念
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，将其递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变的程度被称为排序的稳定性。
- 比如，在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。(内存中读取数据， 排序的结果依旧可以写入到内存中)
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。(内存中读取数据， 排序的结果最终写入到磁盘中)
二. 一图速览常见排序
三. 排序的C++实现
1> 直接插入排序
插入排序， 又叫直接插入排序， 简称插排。
基本思想 :
- 一组待排序的元素， 我们要使其变得有序,例如升序。 此时我们认为前 i 个元素是有序的 (i从1开始), 要将第i+1个元素插入到这前i个元素中。
- 具体的插入过程是， 将第 i+1个元素与前面的元素依次进行比较(从第i个元素开始), 直至找到某个元素小于 第i+1个元素(或者前i个元素均大于第i+1个元素),
- 此时 ， 我们找到该元素小于第i+1个元素， 那么我们将第i+1个元素插入到该元素的后面， 最终使得这共i+1个元素变得有序
- 重复上述过程对数组中的所有元素依次进行排序， 最终使得该数组中的元素全部变得有序
// 直接插入排序 (升序排列)
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++) // n-1 防止 temp = a[end+1] 越界 , 也可以在数组中只有一个元素或是空数组时不进入循环
{
int end = i;
int temp = a[end + 1];
while (end >= 0)
{
if (temp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = temp;
// 代码执行到该位置有两种情况， (1) 前i个元素均 > 待排序元素， 此时待排序元素插入到数组首元素位置， 其他元素后移
// (2) 待排序元素在前i个元素中找到了插入位置， 此位置不为 数组中首元素位置。 原位置的元素及其之后元素后移
}
}
时间复杂度: O(N^2) // 逆序下最坏为0(N^2) , 有序时为O(N)
空间复杂度: O(1) // 原数组中进行排序
2> 希尔排序
希尔排序是按其设计者希尔的名字命名的， 希尔排序又称为 缩小增量排序。
基本思想:
- 对待排序序列进行多次预排序， 通过这多次预排序最终使得待排序序列极为接近有序， 从而降低排序算法的时间消耗(也就是降低了其时间复杂度)
- 设置一个int类型的变量， 假设该变量名为 grep (一般grep=n/2)。
- 将待排序系列中间隔为 grep的元素划分为同组元素
- 如此一来， 待排序元素也就被分为了grep组, 对于这grep组中的元素， 在同组元素之间进行直接插入排序， 使得其在同组中变得有序
- 不断缩小grep的值， 循环往复进行上述过程(一般 grep = grep/2)
- grep不断缩小的过程被称为缩小增量
- 最终grep = 1时， 待排序序列中的元素变得接近有序， 此时在对其进行直接插入排序(相当于对新序列进行直接插入排序)， 最终使得整个序列变得有序
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
希尔排序的时间复杂度都不固定
希尔排序代码实现(希尔所实现)
void ShellSort(int* a, int n)
{
int gap = n;
// 设置变量 gap
while(gap>1)
{
gap = gap / 2;
// 每次循环缩小增量
for (int j = 0; j < gap; j++)
// 同组元素依次进行插排
{
for (int i = j; i < n - gap; i += gap)
// 某个元素进行一次完整的插入排序
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
// while循环遍历 前 i个元素， 直至某个元素 小于 temp
{
if (temp < a[end])
{
a[end + gap] = a[end];
// 比 待排序元素大的元素向后移动gap位
end -= grep;
}
else
{
break;
}
}
a[end + gap] = temp;
// 待排序元素插入到正确的位置
}
}
}
}
时间复杂度: O(N^1.3) //（这是平均时间复杂度）
空间复杂度: O(1)
希尔排序代码实现(优化版)
// 希尔排序代码优化
void ShellSort(int* a, int n)
{
int gap = n;
// 是同组元素与元素之间的间隔
while (gap > 1)
// 这个while循环是控制预排序的次数
// 如果while循环可以运行， 那么当grep = 1时， 一定会运行一次插入排序。 因为是先更新grep的值， 在进行希尔排序。
{
gap = gap / 2;
// 将n个元素分成了grep组, 分组依据是所有间隔为 grep 的元素位于同一组
//gap = gap / 3 + 1;
// 也可以改变gap每次缩小的规模，从而减少排序次数， +1是为了最终使得gap =1 ; 因为
for (int i = 0; i < n - gap; i++)
// 这个for循环是控制同组中的元素依次进行插入排序， 不过是多组并排
// 采取多组并排的方式进行排序, 一共grep个组, 每次将靠前组中的一个元素排完后， 去排后面的组; 后面的组都排完后， 再次循环排
// 前一个组中的下一个元素(按顺序排列) (按组序， 按组中元素序列)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (temp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}
时间复杂度: O(N^1.3) //（这是平均时间复杂度）
空间复杂度: O(1)
3> 选择排序
选择排序顾名思义， 从待排序序列中选出指定元素， 最后将其放到指定位置
基本思路:
- 遍历待排序序列， 从其中选出最大(或最小)的元素， 将其放置在数组中的最前面(降序)或者最后面(升序),
- 第二次遍历待排序序列， 从其中选出次大(或次小)的元素， 将其放置在数组中的最前面 – 降序(升序)或者最后面 – 升序(降序),
- 如此循环往复， 直至数组中的元素全部有序。
- 也可以同时从数组中选出最大和最小的元素， 放在数组的两侧。
选择排序的代码实现(同时选出最大和最小的元素)
// 选择排序
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin <= end)
{
int min = begin, max = end;
// a[min]默认为数组中第一个元素， a[max]默认为数组中最后一个元素
for (int i = begin; i <= end; i++)
// 因此 a[min] 需要和 [begin+1, end] 中的元素比较
{
// a[max] 需要和 [begin, end-1] 中的元素比较
if (a[i] < a[min])
// 取两者并集， 因此 区间为[begin, end]
{
min = i;
}
if (a[i] > a[max])
{
max = i;
}
}
Swap(&a[begin], &a[min]);
if (max == begin)
// 如果 最大值a[max]恰好在索引为begin的位置，那么会将最大值交换至 索引为min的位置
{
max = min;
}
Swap(&a[end], &a[max]);
++begin;
--end;
}
}
时间复杂度: O(N^2) // 最坏和最好下均为O(N^2)
空间复杂度: O(1) // 原数组中进行排序
4> 堆排序
数据结构 - 堆， 通过堆进行的排序被称为堆排序
基本思路:
- 将待排序序列通过多次向下调整， 最终建立一个堆的结构
- 按升序排序 :
- 建大堆，
- 堆中的父节点 >= 子节点
- 每次排序， 将堆顶的元素(最大的元素)与堆末尾的元素交换位置，
- (末尾所得末尾元素不计入)然后向下调整， 得到新堆
- 如此循环往复最终使得待排序序列变为升序序列
- 按降序排列:
- 建小堆
- 堆中的父节点 <= 子节点
- 每次排序， 将堆顶的元素(最小的元素)与堆末尾的元素交换位置，
- (末尾所得末尾元素不计入)然后向下调整， 得到新堆
- 如此循环往复最终使得待排序序列变为降序序列
堆排序的代码实现
// 堆的向下调整
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 建堆且排序
void HeapSort(int* a, int n)
{
for (int i = (n - 1) / 2; i >= 0; i--)
// for循环建堆
// 建堆时间复杂度为 O(N)
{
AdjustDown(a, n, i);
// 向下调整时间复杂度为O(logN)
}
int end = n - 1;
while (end > 0)
// while循环进行堆排序， 时间复杂度为 O（NlogN）
{ // O(logN)
Swap(&a[0], &a[end]);
// 将堆顶元素换至堆末尾 , 在这里end代表堆中最后一个元素的索引
--end;
// 每次交换完， 进行--end， 原堆中最后一个元素不计入新堆
AdjustDown(a, end + 1, 0);
// 向下调整排序 , 在这里end+1代表新堆中元素的个数
// 向下调整 时间复杂度为O(logN)
}
}
时间复杂度: O(NlogN)
// 使用该种方法 从最后一个父节点开始向下调整建堆的时间复杂度为O(3n) ,也就是O(N)
// 从根节点开始 向下调整建堆的时间复杂度为 O(NlogN)
空间复杂度: O(1)
5> 冒泡排序
冒泡排序的命名十分形象， 该种排序方式就像是 将待排序序列中的元素挑选出来， 使其像一个气泡从水中冒出水面一样冒到数组的最后面
基本思路:
- 定义两个指针， 一前一后，使其指向相邻元素。 从数组首元素开始，对相邻元素进行比较
- 每次比较依据的原则是 使得后指针始终指向较大的那个元素 – 升序(或较小)且不改变两个指针的相对位置
- 做法便是， 对两个指针指向的元素进行比较， 如若前指针指向的元素小于后指针指向的元素， 那么同时使两个指针移动一个位置， 然后再次进行比较
- 如果前指针指向的元素大于后指针指向的元素， 那么交换两个元素的位置， 使得后指针指向的位置存储的是较大的那个元素。
- 当后指针指向空时循环结束，此时就将最大的那个元素冒到了数组的最后面
- 如此循环往复， 最终使得待排序序列变为升序
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);
count = 1;
}
}
if (count == 0)
// 对于本就按照升序排列的序列， 冒泡排序外循环运行一次， 没有发生交换， 那么代表该序列有序， 直接结束冒泡排序 此时时间复杂度为最好: O(N)
break;
}
}
时间复杂度: O(N^2) // 最坏: O(N^2) 数组有序时可为O(N)
空间复杂度: O(1)
6> 快速排序
快速排序在大多数情况下，其排序速度远快于其他排序算法， 因此叫做快速排序
基本思路:
- 在待排序序列中， 选定一个元素作为 key值， (一般key值为数组中第一个元素)
- 然后定义两个变量begin , end 分别指向数组的开头和结尾
- 然后通过whille循环遍历整个数组， begin指针在指向小于等于key值的元素时就向后移动, end指针在指向大于等于key值的元素时就向前移动
- 当begin指向的元素大于key值时， begin停止移动； 当end指向的元素小于key值时， end也停止移动， 当两个指针均停止移动时， 我们交换这两个元素的位置
- 当 begin与end指针指向同一位置时， 循环结束
- 当循环结束时， 我们将开始选定作为key值的那个元素与 begin指向的元素进行交换位置
- 上述步骤的思想是 : 使得所有小于key值的元素都在 key值之前， 所有大于key值的元素都在key值之后 (其他等于key值的元素不改变其位置)
- 经过上述步骤， 最终使得被选定为key值的这个元素放置在了未来有序序列的正确位置
- 然后， 我们将这个待排序序列分为 排在key值前面的和排在key值后面的这两组
- 我们在对这两组元素分别进行上述步骤
- 最终待排序序列变为升序序列
快速排序(递归版)
// 快速排序的第一步优化 (三数取中)
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
return midi;
else if (a[left] < a[right])
return right;
else
return left;
}
else
{
if (a[midi] > a[right])
return midi;
else if (a[left] > a[right])
return right;
else
return left;
}
}
// 快速排序之单趟排序的实现(Hoare版 -- 霍尔所编写)
int PartSort1(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
// 调用函数 GetMidi(), 返回三个索引所指向的元素中位于中间的那个元素的索引
Swap(&a[midi], &a[left]);
// 将这个元素交换至数组首位置。
int keyi = left;
// keyi = left ,记录Left的初值，用于一趟排序完成后， 将数组首元素交换至正确位置
while (left < right)
{
while (a[right] >= a[keyi] && left<right)
// "<=" 避免 a[left] = a[right] = a[key] 带来的死循环
// && left < right, 避免极端情况， left(或right)不动， right(或left)动而出现的数组越界情况
{
--right;
}
while (a[left] <= a[keyi] && left < right)
// 先 ++right, 最终保证 a[left] < a[keyi]
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
// 快速排序之单趟排序的实现(挖坑法)
int PartSort2(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[midi], &a[left]);
int key = a[left];
while (left < right)
{
while (a[right] >= key && left < right)
{
--right;
}
a[left] = a[right];
while (a[left] <= key && left < right)
{
++left;
}
a[right] = a[left];
}
a[left] = key;
return left;
}
// 快速排序之单趟排序的实现(前后指针法)
int PartSort3(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
int prev = left, cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != right)
// 在这里不会出现死循环， 因此不需要等号
// 前置 ++ ， 先++ 再使用prev的新值
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
// 完整的快速排序(升序 递归版)
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
if(end-begin+1 > 10)
{
//int keyi = PartSort1(a, begin, end); // 快排 最初霍尔所写
//int keyi = PartSort2(a, begin, end); // 快排 挖坑法
int keyi = PartSort3(a, begin, end); // 前后指针法
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
else
// 快速排序第二步优化 ， 小区间元素进行直接采取插入排序
{
InsertSort(a + begin, end - begin + 1);
}
}
时间复杂度: O(NlogN) // 极端情况下, 快排为线性划分区间时为 时间复杂度为O(N^2)
空间复杂度: O(logN) // 极端情况下, 快排为线性划分区间时为 空间复杂度为O(N)
快速排序(迭代版)
通过利用数据结构 - 栈, 控制快速排序的区间
迭代版待优化 :
- 三数取中
- 小区间直接插排的优化
void QuickSortNonR(int* a, int begin, int end)
// 一般begin = 0， end = n-1 , 这是为了使得begin， end分别指向数组的首尾元素
{
std::stack<int> stk;
// STL的stack容器， 声明一个stack对象stk
stk.push(end);
stk.push(begin);
// 将用于控制快排第一趟的首元素位置和尾元素位置存入栈中
while (!stk.empty())
{
int left = stk.top();
stk.pop();
int right = stk.top();
stk.pop();
int keyi = PartSort3(a, left, right);
// 调用快排单趟排序的实现， 对区间[left, right]中的元素进行排序
if (keyi + 1 < right)
{
stk.push(right);
stk.push(keyi + 1);
// 将右区间元素的首尾存入栈中
}
if (left < keyi - 1)
{
stk.push(keyi - 1);
stk.push(begin);
// 将左区间元素的首尾存入栈中
}
}
}
7> 归并排序
归并排序是对分治思想的一个典型运用 。 分治法 – 分而治之
基本思路:
- 将待排序序列不断拆一分为二 (理想上是均等拆分)
- 通过多次递归拆分， 最后所得序列中为 只含有一个元素的序列， 此时该序列一定为有序序列 (也就是 N 个有序序列),
- 然后我们对已有序的序列进行两两归并(每相邻两个序列进行归并),
- 归并之后得到新的有序序列(也就是 n/2个有序序列， 每个序列中含有两个元素)
- 最后我们多次重复上述步骤，
- 最后一次归并使得两个最大的有序子序列归并为完整有序序列
- 此时 待排序序列变为有序
归并排序(递归版)
// 归并排序 -- 内层实现
void _MergeSort(int* a, int* temp, int begin, int end)
{
if (begin >= end)
// 递归至 空数组或是数组中只存在一个元素
{
return;
// 函数返回
}
int midi = (begin + end) / 2;
// 将数组分隔
_MergeSort(a, temp, begin, midi);
// 递归调用函数_MergeSort() , 传入左区间的序列
_MergeSort(a, temp, midi + 1, end);
// 递归调用函数_MergeSort() , 传入右区间的序列
int begin1 = begin, end1 = midi;
// 当递归函数开始返回时， 此时左右区间均为有序序列， 进行归并 (第一次归并是将 单个元素数组与单个元素数组(或空数组)进行归并)
int begin2 = midi + 1, end2 = end;
int index = begin;
// 定义变量 分别确定左右区间 begin1， end1 确定左区间首尾元素的索引 变量index用于将元素归并插入动态数组 temp 时，可以有序的连续插入
while (begin1 <= end1 && begin2 <= end2 )
{ // 循环结束的条件是 其中一个数组遍历完， 也就是将其中一个区间数组中的元素完全插入temp指向的动态数组中
if (a[begin1] < a[begin2])
// 判断左右区间数组中首元素那个较小， 将较小的元素尾插入temp数组
{
temp[index++] = a[begin1++];
}
else
{
temp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
// 判断两个区间数组中， 谁未被遍历完， 然后继续遍历元素并插入temp指向的数组中
{
temp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[index++] = a[begin2++];
}
for (int i = begin; i <= end; i++)
// 将temp数组中存储的元素拷贝至a数组中指定位置中。
// 将变量 index 定义的值为 begin时， 在最后一步的拷贝时， 可以起到巧妙的作用(无需定义多个变量)
{
a[i] = temp[i];
}
}
// 完整的归并排序(递归版)
void MergeSort(int* a, int n)
{
int* temp = new int[n];
// 在堆区new一个int类型的数组， 大小为 4n个字节， 可存储n个元素, 用于后续元素归并
if (!temp)
{
perror("new is failed");
exit(-1);
}
_MergeSort(a, temp, 0, n - 1);
// 调用实际归并排序函数
}
时间复杂度: O(NlogN)
空间复杂度: O(N)
归并排序(迭代版)
// 归并排序非递归
void MergeSortNonR(int* a, int n)
{
int grep = 1;
int* temp = new int[n];
while (grep < n)
{
for (int i = 0; i < n; i += 2 * grep)
{
int begin1 = i, end1 = i + grep - 1;
int begin2 = i + grep, end2 = i + 2 * grep - 1;
int index = i;
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
// 循环结束的条件是 其中一个数组遍历完， 也就是将其中一个区间数组中的元素完全插入temp指向的动态数组中
{
if (a[begin1] <= a[begin2])
// 判断左右区间数组中首元素那个较小， 将较小的元素尾插入temp数组
{
temp[index++] = a[begin1++];
}
else
{
temp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
// 判断两个区间数组中， 谁未被遍历完， 然后继续遍历元素并插入temp指向的数组中
{
temp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[index++] = a[begin2++];
}
for (int j = i; j <= end2; j++)
// 将temp数组中存储的元素拷贝至a数组中指定位置中。
{
a[j] = temp[j];
}
}
grep*=2;
}
delete[]temp;
}
时间复杂度: O(NlogN)
空间复杂度: O(N)
8> 基数排序
基数排序，又叫非比较排序。 是通过不同的关键字对待排序序列中的元素进行计数并排序
基本思路:
- 通过哈希映射的方式将待排序序列的各个元素映射到数组的下标中
- 然后计算每个元素出现的次数， 出现一次就对其所映射的指定位置进行+1
- 不断地遍历整个数组， 最终映射所得数组记录了待排序序列中的不同元素的位置与相同元素的个数
- 最后遍历映射数组， 在通过映射的方式将映射数组中的记录写回到原数组中
- 最终， 待排序序列变为有序
// 计数排序
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* temp = new int[range] {0};
for (int i = 0; i < n; i++)
{
int num = a[i] - min;
temp[num]++;
}
int index = 0;
for (int i = 0; i < range; i++)
{
while (temp[i])
{
a[index++] = i + min;
temp[i]--;
}
}
delete[] temp;
}
时间复杂度: O(N+range)
空间复杂度: O(range)