高阶排序
1、快速排序
冒泡排序的升级算法
每次选择一个基准数，把小于基准数的放到基准数的左边，把大于基准数的放到基准数的右边，采用 “ 分治算法 ”处理剩余元素，直到整个序列变为有序序列。
最好和平均的复杂度：
时间复杂度：O(n)*O(logn) = O(nlogn)
空间复杂度：O(logn) 递归的深度所占用的栈内存
最坏的情况（有序的元素）：元素有几个，其深度就有几个，此时时间复杂度为 O(n^2) , 空间复杂度为O(n)
思路
实例理解
对于数组arr[] = {46,8,76,10,38,7,68,32,65,53};进行快速排序。
循环的条件 L< R
1、选取基准数 val = arr[L]; // val = 46
2、从R开始往前找第一个 <val 的数字，放到L的地方。（这里不用担心数据被覆盖，因为val已经将值保存）， L++ 。
3、从L开始，往后找第一个 >val 的数字，放到R的地方， R-- 。
4、重复上面的过程，直到循环结束（循环条件为 L<R)
运行到循环结束
此时，将val的值写入 arr[L] 最终一趟下来的结果为
一趟下来，此时，arr[L] 左边的值全部小于val–46,左边全部大于val–46。
此时，继续对两边的数据继续快排。
最终结果为：
代码实现
//快排分割处理函数
int Partation(int arr[], int left, int right)
{
//记录基准数
int val = arr[left];
//进行一次快排分割处理 O(n)*O(logn) = O(nlogn) 空间复杂度：O(logn) 递归的深度所占用的栈内存
while (left < right)
{
while (left < right && arr[right] > val)
{
right--;
}
if (left < right)
{
arr[left] = arr[right];
left++;
}
while (left < right && arr[left] < val)
{
left++;
}
if (left < right)
{
arr[right] = arr[left];
right--;
}
}
//left == right 的位置，就是放基准数的位置
arr[left] = val;
return left;
}
//快排的递归接口
void QuickSort(int arr[], int begin, int end)
{
if (begin >= end)//快排递归结束的条件
{
return;
}
//在[begin,end]区间的元素进行一次快排分割处理
int pos = Partation(arr,begin,end);
//对基准数的左边和右边的序列，再分别进行快排
QuickSort(arr,begin,pos-1);
QuickSort(arr,pos+1,end);
}
//快速排序
void QuickSort(int arr[], int size)//为了区别自带的快速排序函数
{
return QuickSort(arr,0,size-1);
}
int main()
{
int arr[10];
srand(time(NULL));
for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
QuickSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
return 0;
}
测试
快速排序的算法优化、效率提升
1）对于小段趋于有序的序列采用插入排序
2）三数取中法。旨在挑选合适的基准数，防止快排退化成冒泡排序。
3）随机数法
特点
快速排序是个不稳定的排序算法
当数据趋于有序，或者已经有序了，快速排序的效率是很差的，但是快速排序的效率是最好的。
快排算法优化一：
1、随着快速排序算法执行，数据越来越趋于有序，在一定范围内，可以采用插入排序代替快速排序
相关代码：
//针对快排优化设计的插入排序
void InsertSort(int arr[], int begin,int end)
{
for (int i = begin; i <= end; i++)//O(n)
{
int val = arr[i];
int j = i - 1;
for (; j >= 0; j--) //O(n)
{
if (arr[j] <= val)
{
break;
}
arr[j + 1] = arr[j];
}
//val -> j+1
arr[j + 1] = val;
}
}
void QuickSort(int arr[], int begin, int end)
{
if (begin >= end)//快排递归结束的条件
{
return;
}
//优化一：当[begin,end] 序列的元素个数小到指定数量，采用插入排序
if (end - begin <= 50)//这里的范围视情况而定
{
InsertSort(arr,begin,end);
return;
}
//在[begin,end]区间的元素进行一次快排分割处理
int pos = Partation(arr,begin,end);
//对基准数的左边和右边的序列，再分别进行快排
QuickSort(arr,begin,pos-1);
QuickSort(arr,pos+1,end);
}
快排算法优化二：选择基准数的优化，采用“三数取中”法
采用“三数取中”法，找合适的基准数。
mid = (L+R)/2;
2、归并排序
也采用 “ 分治思想 ”，先进行序列划分，再进行元素的有序合并。
时间复杂度：O(n logn)
空间复杂度：O(logn)+O(n) — 取大的 — O(n)
核心思想
类比于递归思想，核心在于递和归。
递—将数据规模不断的减小，减小到结果已知的规模。
归—通过已知的规模反推而上，不断解决上一层规模的问题，最终累计出原始数据 的结果。
所以归并排序的思想：在归的过程中，进行的数据合并，达到排序的效果。
难点
上述思想衍生出的问题和难点：
1）递到什么程度，才开始归？
2）在归的过程中，如何进行数据合并？
对数数据规模需要一个前后指针，一个起始下标，一个末尾下标。进行二路归并，需要中间值，int mid = (L+R)/2;
递的过程：
将数据分两半，
归并的过程：
数据合并，也就是叶子节点网根节点回退。
重新开辟一个空间，将两个有序的叶子节点合并递归到上一层，不断重复，直到归并到根节点，此时数据处理完毕。
代码实现
//归并过程函数
void Merge(int arr[], int l, int m, int r)
{
int* p = new int[r-l+1];
int idx = 0;
int i = l;
int j = m + 1;
while (i <= m && j <= r)
{
if (arr[i] <= arr[j])
{
p[idx++] = arr[i++];
}
else
{
p[idx++] = arr[j++];
}
}
while (i <= m)
{
p[idx++] = arr[i++];
}
while (j <= r)
{
p[idx++] = arr[j++];
}
//再把合并好的大段有序的结果，拷贝到原始arr[数组[l,r]区间内
for (i = l, j = 0; i <= r; i++, j++)
{
arr[i] = p[j];
}
delete[]p;
}
//归并排序递归接口
void MergeSort(int arr[], int begin, int end)
{
//递归结束的条件
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
//先递
MergeSort(arr,begin,mid);
MergeSort(arr,mid+1,end);
//再归并 [begin,mid] [mid+1,end] -- 把两个小段有序的序列，合并成一个大段的有序序列
Merge(arr,begin,mid,end);
}
//归并排序
void MergeSort(int arr[], int size)
{
return MergeSort(arr, 0, size - 1);
}
测试
int main()
{
int arr[10];
srand(time(NULL));
for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
return 0;
}
3、堆排序
二叉堆
二叉堆就是一颗完全二叉树，范围两种典型的堆，分别是大根堆和小根堆
基于二叉堆的基础，规定了当前节点和两个孩子节点值的大小关系。
满足 0 <= i <= (n-1)/2 , n 代表最后一个元素的下标。
如果 arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2*i + 2] ,就是小根堆。
如果 arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2*i + 2] ,就是大根堆。
二叉堆，实际上（物理上）还是用数组存储的元素，只是逻辑上，将其看成有一个人口根节点，
每个节点都有两个孩子，没有孩子的最下一层，称之为叶子节点，这样的二叉树结构，称之为完全二叉树。
完全二叉树：
完全二叉树相比于二叉树，最后一层的叶子节点都是靠左排列，
优点是在存储二叉树节点的时候，比较省数组内存空间。
最后一层的叶子节点都是靠左排列的，每一层的节点都是满的。
最下层节点，必须从左往右都有，中间空一个都不算。
如何将数组存储的元素，逻辑上看成完全二叉树？当前节点和两个孩子节点有什么关系？
在数组中，满足下图关系的节点，在逻辑上看成二叉树当前节点和其左右节点。
如何获得第一个非叶子节点的下标？
(n-1)/2
堆的上浮和下层调整（添加删除元素）
入堆（大根堆入堆示例）
数组的元素添加，在数组末尾添加元素。
相对应的，逻辑上，在二叉树的最下层如图所示位置，添加新元素。
但此时，破坏了此时完全二叉树的逻辑，需要进行调整。、
因为是大根堆，所以要对数据进行上浮调整。
这里新的元素10大于父节点5，进行交换。
交换过后，发现还是比父节点大，继续交换。
如下图所示，元素上浮到根节点，上浮结束。
注意，人堆不是入到堆顶，是入到小于父节点的位置。
出堆（大根堆出堆示例）
大根堆出堆，出堆顶元素。
优先级队列实现的时候，假设值越大，优先级越大，这里为大根堆，出元素，就先出堆顶元素。
当然也可以规定，值越小，优先级越小。
出堆操作
将堆顶元素取出。
将最后的数据放到堆顶，该值相对是偏小的。
从零号元素开始，往下调整，继续下层调整操作
比较节点两个孩子节点，将孩子节点中较大值，覆盖，进行下层操作。
以此类推，直到元素无孩子节点，或者孩子节点都小于该元素。
将val覆盖该位置的值。
基于堆的优先级队列代码实现
类似于C++库中的priority_queue，其底层也是数组，只不过没有自己写数组。如果自己写数组，就成为容器了，而不是容器适配器，其只是对底层容器（vector）进行适配。
//优先级队列实现 priority_queue(vector) -- push pop top empty size
class PriorityQueue
{
public:
//模板定义一个函数对象
using Comp = function<bool(int,int)>;
//这里默认大根堆
PriorityQueue(int cap = 20, Comp comp = greater<int>())
:size_(0)
, cap_(cap)
, comp_(comp)
{
que_ = new int[cap_];
}
//PriorityQueue(Comp comp = greater<int>())
PriorityQueue(Comp comp)
:size_(0)
, cap_(20)
, comp_(comp)
{
que_ = new int[cap_];
}
~PriorityQueue()
{
delete[] que_;
que_ = nullptr;
}
public:
//入堆操作 O(log n) O(1)
void push(int val)
{
//判断扩容
if (size_ == cap_)
{
int* p = new int[2 * cap_];
memcpy(p,que_,cap_*sizeof(int));
delete[]que_;
que_ = p;
cap_ *= 2;
}
if (size_ == 0)
{
//只有一个元素，不用进行堆的上浮调整
que_[size_] = val;
}
else
{
//堆里面有多个元素，需要进行上浮调整
siftUp(size_,val);
}
size_++;
}
//出堆操作
void pop()
{
if (size_ == 0)
throw "container is empty!";
size_--;
if (size_ > 0)
{
// 删除堆顶元素，还有剩余的元素，要进行堆的下沉调整
siftDown(0,que_[size_]);
}
}
bool empty() const { return size_ == 0; }
int top()const
{
if (size_ == 0)
throw "container is empty!";
return que_[0];
}
int size() const { return size_; }
private:
//入堆上浮调整
void siftUp(int i, int val)
{
while (i > 0)//最多计算到根节点（0号位）
{
int father = (i - 1) / 2;
if (comp_(val, que_[father]))
{
que_[i] = que_[father];
i = father;
}
else
{
break;
}
}
//把val放到i的位置
que_[i] = val;
}
//出堆下沉调整
void siftDown(int i, int val)
{
//i下沉不能超过最后一个有孩子的节点
//while (i <= (size_ - 1 - 1) / 2)
while (i < size_ / 2)
{
int child = 2 * i + 1;//第i个节点的左孩子
if (child + 1 < size_ && comp_(que_[child+1],que_[child]))
{
//如果i节点右孩子的值大于左孩子，child记录右孩子的下标
child = child + 1;
}
if (comp_(que_[child], val))
{
que_[i] = que_[child];
i = child;
}
else
{
break;//已经满足堆的性质，提前结束
}
}
que_[i] = val;
}
private:
int* que_; // 指向动态扩容的数组
int size_; // 数组元素的个数
int cap_; // 数组的总内存空间大小
Comp comp_; //比较器对象
};
测试
int main()
{
PriorityQueue que;//基于大根堆实现的优先级队列
PriorityQueue que1([](int a, int b) {return a < b; });//基于小根堆实现的优先级队列
srand(time(NULL));
for (int i = 0; i < 10; i++)
{
que.push(rand()%100);
que1.push(rand() % 100);
}
while (!que.empty())
{
cout << que.top() << " ";
que.pop();
}
cout << endl;
while (!que1.empty())
{
cout << que1.top() << " ";
que1.pop();
}
cout << endl;
}
堆排序代码实现
堆排序的实现，需要借助于大根堆或者小根队的性质。如果需要从小到大排序，需要借助于大根堆。反之，借助小根堆。
思路
对于下图所示无序原始序列，将其这些在数组里存放的元素，逻辑上看作一个二叉堆。
1、从第一个非叶子节点开始，把二叉堆调整成一个大根堆
其中，第一个非叶子节点的小标为 ( n - 1 )/2,如图所示为数字8
从第 ( n - 1 )/2号位元素开始，到堆元素（0），进行下沉操作。
2、把堆顶元素和当前末尾元素进行交换，从零号位继续开始进行部分的堆的下沉
上一趟取得的剩余元素的最大值，将其置于末尾，该元素处理完毕。
下一趟就不管该值，对剩下的元素继续进行下沉操作
3、重复操作二，不断获取剩余元素最大值，并将其下沉
代码实现
//堆的下沉调整
void siftDown(int arr[], int i, int size)
{
int val = arr[i];//记录一下要调整的值
//while(i <= (size-1-1)/2)
while (i < size / 2)
{
int child = 2 * i + 1;
if (child + 1 < size && arr[child + 1] > arr[child])
{
child = child + 1;
}
if (arr[child] > val)
{
arr[i] = arr[child];
i = child; //i 继续指向其孩子，继续调整，直到最后一个有孩子节点的节点
}
else
{
break;
}
}
arr[i] = val;
}
//堆排序
void HeapSort(int arr[], int size)
{
int n = size - 1;
//从第一个非叶子节点
for (int i = (n - 1) / 2; i >= 0; i--)
{
siftDown(arr,i,size);
}
//将堆顶元素和当前末尾元素进行交换，从堆顶再一次进行下沉操作
for (int i = n; i > 0; i--)
{
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
siftDown(arr,0,i); //第三个参数，参与调整的元素的个数，没处理一次，减一
}
}
测试
int main()
{
int arr[10];
srand(time(NULL));
for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
return 0;
}
4、性能测试
注意，rand 函数所给的随机数 范围为 0~32767。
cout << RAND_MAX << endl; // 打印rand函数所给随机数的最大值
如果测试数据量规模过大，例如千万、亿。其中重复的元素将会非常多。
所以为了测试的准确性，在每个测试区间内，都随机一些数据。例如区间0~32767，32768–32768+32767 …。第二个区间，随机数再加一些基数。
