做淘宝站外推广网站,dw个人网站设计模板免费,杭州网站建设zj net,免费下载模板的网站有哪些个人主页点这里~ 快速排序的简介: 快速排序是Hoare于1962年提出的一种 二叉树结构 的 交换 排序方法#xff0c;其基本思想为#xff1a;任取待排序元素序列中 的某元素作为 基准值 #xff0c;按照该排序码将待排序集合分割成 两子序列 #xff0c; 左子序列中所有元素均 …
个人主页点这里~ 快速排序的简介: 快速排序是Hoare于1962年提出的一种 二叉树结构 的 交换 排序方法其基本思想为任取待排序元素序列中 的某元素作为 基准值 按照该排序码将待排序集合分割成 两子序列 左子序列中所有元素均 小于 基准值 右 子序列中所有元素均 大于 基准值 然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 快速排序的关键: 设置一个key作为基准值,一般将最左边的元素作为key 详细过程: 定义一个left和一个right指针作为下标分别指向无序数组的左右边界, right从右向左走,当找到比key小的值就停下,left从左往右走,当找到比key大的值就停下, (左边找大,右边找小) (注意:key在左边就先走right 为什么?:我们会发现key的值一定比相遇的值要大 为什么?:因为我们先走right再走left那么循环终止只有那么情况:right找到了比key要小的值停下,然后left走到了与right相遇停止,此时相遇的值肯定是比key小的值,因为是right走到的值,相反就不行) 当两都停下时,交换两个位置的值.之后继续此过程 当两人走到相遇时停下来,交换key的值和两人相遇的值,同时更新key的位置,将key重新放到两人相遇的位置,此时会发现在key左边存放的都是比key的值小的值,右边都是大的,但并不一定时有序的 最后,以新的key为基准值,两边的区域分别递归上述过程 上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,写递归框架时可想想二叉树前序遍历规则即可快速写出来 void quicksort(int* a, int left, int right)
{if (left right)//递归终止条件{return;}int begin left;int end right;int key left;while (begin end){while (a[end] a[key] begin end){end--;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]);key begin;quicksort(a, left, key - 1);//左区间quicksort(a, key 1, right);//右区间
} 可以优化的两点(两个问题): 1.解决问题:避免了循环直接到相遇的情况 在快速排序中选择基准元素key的方式会影响算法的性能。 如果选择的基准元素总是接近待排序序列的中位数那么算法的性能会接近最优即时间复杂度为O(n log n)。然而如果选择的基准元素总是接近待排序序列的边界值即最大或最小值那么算法的性能会退化到接近冒泡排序即时间复杂度为O(n^2)。 当基准元素接近待排序序列的中位数时 左边和右边的子序列长度大致相等。这意味着递归调用的深度较小同时每次递归处理的数据量也大致相等这使得算法能够保持较为均匀的分割从而充分利用分治策略的优势。递归树较为平衡每个子问题的规模都大致相等。这有助于减少算法中的比较次数和交换次数从而提高算法的效率。 当基准元素接近待排序序列的边界值即最大或最小值时 左边或右边的子序列可能非常长而另一个子序列则可能很短。这会导致递归调用的深度增加同时每次递归处理的数据量也会变得不均匀。递归树变得不平衡一些子问题的规模很小而另一些子问题的规模则很大。这会增加算法中的比较次数和交换次数从而降低算法的效率。 在最坏的情况下当每次选择的基准元素都是待排序序列的最小值或最大值时快速排序会退化为冒泡排序。这是因为每次分割后其中一个子序列的长度为0即没有元素需要排序而另一个子序列的长度则为n-1即除了基准元素外的所有元素。这样算法需要执行n-1次递归调用每次递归调用只减少一个元素实际上就变成了冒泡排序的效果。 解决方法:三数取中 // 三数取中,取中间大的
// 解决问题1:避免了循环直接到相遇的情况
int getmid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left right]){return right;}else{return left;}}else{if (a[left] a[right]){return left;}else if (a[mid] a[right]){return mid;}else{return right;}}
}
void quicksort(int* a, int left, int right)
{if (left right){return;}//三数取中int mid getmid(a, left, right);Swap(a[mid], a[left]);int begin left;int end right;int key left;while (begin end){while (a[end] a[key] begin end){end--;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]);key begin;quicksort(a, left, key - 1);quicksort(a, key 1, right);
}解决问题2:当递归排序到后面剩下10个数左右时,递归开辟的栈帧 以key为基准开辟左右两个栈帧,类似于二叉树,消耗几乎一半的栈帧(二叉树往下子树越多), 解决方法:小区间优化 所以我们在是剩下10个左右元素个数((right - left 1) 10)需要排序时,不要再递归,而是调用其他合适排序算法进行排序 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void printarr(int* a, int sz)
{for (int i 0; i sz; i){printf(%d , a[i]);}printf(\n);
}// 三数取中,取中间大的
// 解决问题1:避免了循环直接到相遇的情况
int getmid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left right]){return right;}else{return left;}}else{if (a[left] a[right]){return left;}else if (a[mid] a[right]){return mid;}else{return right;}}
}void insertsort(int* a, int sz)
{for (int i 0; i sz - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
void quicksort(int* a, int left, int right)
{if (left right){return;}// 以key为基准开辟左右两个栈帧,类似于二叉树// 解决问题2:当递归排序到后面剩下10个数左右时,递归开辟的栈帧// 消耗几乎一半的栈帧(二叉树往下子树越多),// 所以我们可以在这时候调用 简单的其他排序来优化// 小区间优化if ((right - left 1) 10){//插入排序insertsort(a left, right - left 1);}else{//三数取中int mid getmid(a, left, right);Swap(a[mid], a[left]);int begin left;int end right;int key left;while (begin end){while (a[end] a[key] begin end){end--;}while (a[begin] a[key] begin end){begin;}Swap(a[begin], a[end]);}Swap(a[key], a[begin]);key begin;quicksort(a, left, key - 1);quicksort(a, key 1, right);}
} 分享结束啦!个人主页点这里~
