1、快速排序
创新互联公司专注为客户提供全方位的互联网综合服务,包含不限于成都网站制作、网站设计、外贸网站建设、潞城网络推广、微信小程序定制开发、潞城网络营销、潞城企业策划、潞城品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联公司为所有大学生创业者提供潞城建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。可以用递归和非递归的方法分别实现。
平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快。int _QuickSort(int* a,int left,int right,int key) { while (left < right) { while (left < right&&a[left] <=a[key]) { left++; //找出比a[key]大的下标 } while (left < right&&a[right] >=a[key]) { right--; //找出比a[key]小的下标 } swap(a[left], a[right]); //交换 } if (a[left] > a[key]) //如果需要排序的序列都小于a[key]值 swap(a[left],a[key]);//把 key-1 当边界,如图中当第二次a[key]为5时。 return left; } return key; }
int _QuickSort2(int* a, int left, int right, int key) { int cur = left; int prev = left - 1; while (cur <= right) { if (a[cur] <= a[key]) { prev++; if(prev!=cur) swap(a[prev], a[cur]); } cur++; } swap(a[prev+1],a[key]); return prev+1; }
void QuickSort(int* a, int left, int right) { assert(a); if (left < right) { int mid = FindMid(a,left,right);//3位取中,把左边右边和中间的数比较,找出中间的数作为key swap(a[mid],a[right]); int key = right; int boundary=_QuickSort2(a,left,right-1,key);//一趟排序后找出边界值 //int boundary=_QuickSort(a,left,right-1,key);//有两种方法找出边界值 QuickSort(a,left,boundary-1); QuickSort(a, boundary+1,right); } } //非递归借用栈来完成 void NORQucikSort(int* a,int left,int right) { stack<int> s1; s1.push(left); s1.push(right); while (!s1.empty()) { int key = s1.top(); int _right = s1.top(); s1.pop(); int _left = s1.top(); s1.pop(); if (_left >= _right) continue; int boundary = _QuickSort(a, _left, _right - 1, key); //int boundary = _QuickSort2(a, _left, _right - 1, key); s1.push(boundary + 1); //先压key右边的序列 s1.push(_right); s1.push(_left); s1.push(boundary-1); } } //优化快速排序 三数取中 int FindMid(int* a, int left, int right) { int mid = left + (right - left) / 2; if (a[left] > a[right]) { if (a[left] < a[mid]) return left; else if (a[mid]>a[right]) return mid; return right; } else { if (a[left] > a[mid]) return left; else if (a[mid] < a[right]) return mid; return right; } }
2、堆排序
堆排序的思想就是如果是升序排序,则建最大堆,反之,则建最小堆。
建堆之后,从第一个数开始和最后一个数交换,缩小堆的范围(去除最后一个数),然后第一个数向下调整,则最大的数已在最后。直到堆里只有一个数。
建堆过程就是从最后一个非叶子节点直到跟节点向下调整。假设我们现在要升序排序。即就是向下调整时,把小的交换到父节点。
堆排序的时间复杂度是O(N*lgN),空间复杂度是O(1)。
void AdjustDown(int *a,int size,int parent) //向下对齐 { int child = parent * 2 + 1; //把左孩子的下标给child while (child < size) //保证向下对齐直到child超出范围 { if (child + 1 < size&&a[child + 1] > a[child]) //当右孩子>左孩子时,child变为右孩子下标 { child++; } if (a[parent] < a[child]) { swap(a[parent],a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int *a, int size) { assert(a); for (int i = (size - 2) / 2; i >= 0; i--) { AdjustDown(a,size,i); //从图中下标为4的非叶子节点开始,进行向下对齐 } for (int i = size - 1; i > 0; i--) { swap(a[0],a[i]); //把最大堆中的第一个元素和最后一个元素交换,此时最后一个元素最大 AdjustDown(a,i,0);//把剩余的元素建成最大堆 } }
3、归并排序
归并排序时的时间复杂度为O(nlgn) 其主要思想是分治法(divide and conquer),分就是要将n个元素的序列划分为两个序列,再分为4个序列,直到每个序列只有一个数,然后合并两个有效序列为一个有效序列,直到整个序列为有序序列。
归并排序的时间复杂度O(N*lgN),空间复杂度是O(N)。
递归实现:
void MergeSort(int *a, int size) { assert(a); int *tmp = new int[size]; int left = 0, right = size - 1; _MergeSort(a,tmp,left,right); } void _MergeSort(int* a, int* tmp, int left, int right) { if (left < right) { int mid = left + (right - left) / 2;//取中间下标 _MergeSort(a,tmp,left,mid); //递归进行 _MergeSort(a, tmp, mid+1, right); //直到递归到左右序列只有一个元素 Combine(a,tmp,left,mid,mid+1,right);//2个有序序列合并成一个 memcpy(a+left,tmp,(right-left+1)*sizeof(int));//把有序序列拷给原数组 } } void Combine(int* a, int* tmp, int begin1, int end1,int begin2, int end2) { int index = 0; while (begin1 <= end1&&begin2 <= end2) { while (a[begin1] <= a[begin2]&&begin1<=end1) { tmp[index++] = a[begin1]; begin1++; } while (a[begin1] > a[begin2] && begin2 <= end2) { tmp[index++] = a[begin2]; begin2++; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } }
而递归排序的非递归实现,则采取相反的思路,先把整个数组分成n个序列,每次两个序列合并。每两个序列有序后,合4个序列,以此类推。
void MergeSort2(int *a, int size) { assert(a); int gap = 0; int *temp = new int[size]; int count = 0; //gap指begin1和end1每次的差值 所差次数依次为,0,1,3,7(2^n-1) while (gap < size) { int begin1 = 0, end1 = gap, begin2 = end1 + 1, end2 = begin2 + gap; for (; end2 < size; begin1=end2+1,end1=begin1+gap,begin2=end1+1,end2=begin2+gap) { Combine(a,temp,begin1,end1,begin2,end2); memcpy(a+begin1,temp,(end2-begin1+1)*sizeof(int)); } if (begin2 < size) { end2 = size - 1; Combine(a, temp, begin1, end1, begin2, size-1); memcpy(a + begin1, temp, (end2 - begin1 + 1)*sizeof(int)); } count++; gap=pow(2,count)-1; } }
分享题目:常用的较优排序之快速排序,堆排序,归并排序
文章转载:https://www.cdcxhl.com/article38/peiepp.html
成都网站建设公司_创新互联,为您提供响应式网站、定制开发、网站建设、小程序开发、外贸建站、网站收录
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联