微网站 好处,wordpress主题演示站,做网站 营业执照,深圳关键词优化报价高阶排序 1、快速排序
冒泡排序的升级算法
每次选择一个基准数#xff0c;把小于基准数的放到基准数的左边#xff0c;把大于基准数的放到基准数的右边#xff0c;采用 “ 分治算法 ”处理剩余元素#xff0c;直到整个序列变为有序序列。
最好和平均的复杂度#xff1a…高阶排序 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、重复上面的过程直到循环结束循环条件为 LR) 运行到循环结束 此时将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,pos1,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 - j1arr[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,pos1,end);}快排算法优化二选择基准数的优化采用“三数取中”法
采用“三数取中”法找合适的基准数。
mid (LR)/2;2、归并排序
也采用 “ 分治思想 ”先进行序列划分再进行元素的有序合并。 时间复杂度O(n logn) 空间复杂度O(logn)O(n) — 取大的 — O(n)
核心思想
类比于递归思想核心在于递和归。 递—将数据规模不断的减小减小到结果已知的规模。 归—通过已知的规模反推而上不断解决上一层规模的问题最终累计出原始数据 的结果。 所以归并排序的思想在归的过程中进行的数据合并达到排序的效果。
难点
上述思想衍生出的问题和难点
1递到什么程度才开始归
2在归的过程中如何进行数据合并对数数据规模需要一个前后指针一个起始下标一个末尾下标。进行二路归并需要中间值int mid (LR)/2;
递的过程 将数据分两半 归并的过程 数据合并也就是叶子节点网根节点回退。 重新开辟一个空间将两个有序的叶子节点合并递归到上一层不断重复直到归并到根节点此时数据处理完毕。
代码实现
//归并过程函数
void Merge(int arr[], int l, int m, int r)
{int* p new int[r-l1];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,mid1,end);//再归并 [begin,mid] [mid1,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 functionbool(int,int);//这里默认大根堆PriorityQueue(int cap 20, Comp comp greaterint()):size_(0), cap_(cap), comp_(comp){que_ new int[cap_];}//PriorityQueue(Comp comp greaterint())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_[child1],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~3276732768–3276832767 …。第二个区间随机数再加一些基数。
