快速排序-Hoare 递归版 C语言
个人主页点这里~
快速排序的简介:
快速排序的关键:
设置一个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);}
}分享结束啦!个人主页点这里~