赞
踩
博主主页:LiUEEEEE
C语言专栏
数据结构专栏
力扣牛客经典题目专栏
任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
下文将对上述四种实现方法依次进行讲解。
其主要思想为:使用循环遍历数组
递归方法如上图所示(除3外其余递归交换位置为虚构,需实际计算得到)。
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } int PartSort1(int* a, int left, int right) { if (left >= right) return; int begin = left; int end = right; int keyi = left; while (begin < end) { while(begin < end && a[end] >= a[keyi]) { end--; } while (begin < end && a[begin] <= a[keyi]) { begin++; } Swap(&a[end], &a[begin]); } Swap(&a[end], &a[keyi]); keyi = begin; PartSort1(a, left, keyi - 1); PartSort1(a, keyi + 1, right); }
其主要思想为:使用循环遍历数组
int PartSort2(int* a, int left, int right) { if (left >= right) return; int key = a[left]; int keyi = left; int begin = left; int end = right; while (begin < end) { while (begin < end && a[end] >= key) { end--; } a[keyi] = a[end]; keyi = end; while (begin < end && a[begin] <= key) { begin++; } a[keyi] = a[begin]; keyi = begin; } a[keyi] = key; PartSort2(a, left, end - 1); PartSort2(a, end + 1, right); }
其主要思想为:
定义指针prev指向数组开始位置,cur指向数组开始第二个位置,并使用keyi记录数组中用作比较的数。
令cur向数组右端遍历,若出现小于keyi的数则停止遍历,转为prev进行遍历。
令prev向数组右端遍历,若出现大于keyi的数,则令其与cur交换位置,而后继续进行cur的遍历,直至cur达到数组末尾的下一位(即越界)。
当cur越界后将当前prev所代表的值与key所代表值进行交换,并将prev所处位置视为分界点,从分界点处分出两个新的子数组进行递归,直至所递归的数组L >= R。
递归结束。
其递归示意图与标题三中所展示一致,故不再做重复展示。
前后指针法快速排序代码如下所示:
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } int PartSort3(int* a, int left, int right) { if (left >= right) return; int prev = left; int cur = prev + 1; int key = left; while (cur <= right) { if (a[cur] < a[key] && a[++prev] != a[key]) Swap(&a[cur], &a[prev]); cur++; } Swap(&a[key], &a[prev]); PartSort3(a, left, prev - 1); PartSort3(a, prev + 1, right); }
使用栈来模拟系统中栈的功能,将数组的右左下标依次传入栈中,每一次取其栈顶位置数据分别作为单词快排的目标数组左下标和右下表(每一次取值后需删除栈顶元素)。
在单次快排完成后判断其在分段点所分两个新的子数组左右下标是否合理(是否存在左下标大于或等于右下标的行为),若不存在则将右子数组右左下标依次推入栈中,而后将左子数组右左下标依次推入栈中,进行下一轮循环。
其循环判断条件为栈中是否为空。
有关其入栈顺序可不做过多研究,但要保证的前提是所取出数值需与操作数组的左右下标相对应,以避免不必要麻烦。
非递归法快速排序代码如下所示:
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void QuickSortNonR(int* a, int left, int right) { ST s; STInit(&s); STPush(&s, right); STPush(&s, left); while (!STEmpty(&s)) { int begin = STTop(&s); STPop(&s); int end = STTop(&s); STPop(&s); int prev = begin; int cur = prev + 1; int key = begin; while (cur <= end) { if (a[cur] < a[key] && a[++prev] != a[key]) Swap(&a[cur], &a[prev]); cur++; } Swap(&a[key], &a[prev]); if (prev + 1 < end) { STPush(&s, end); STPush(&s, prev + 1); } if (begin < prev - 1) { STPush(&s, prev - 1); STPush(&s, begin); } } STDestroy(&s); }
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[right] > a[left]) return left; else return right; } else { if (a[mid] < a[right]) return mid; else if (a[right] < a[left]) return left; else return right; } }
void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) Swap(&a[j], &a[j + 1]); } } } if (right - left < 10) { BubbleSort(a, right - left + 1); }
至此快速排序的优化结束,其完整代码如下所示(前后指针法快速排序):
void QuickSort(int* a, int left, int right) { if (left >= right) return; int mid = GetMid(a, left, right); Swap(&a[left], &a[mid]); if (right - left < 10) { BubbleSort(a, right - left + 1); } else { int prev = left; int cur = prev + 1; int key = left; while (cur <= right) { if (a[cur] < a[key] && a[++prev] != a[key]) Swap(&a[cur], &a[prev]); cur++; } Swap(&a[key], &a[prev]); PartSort3(a, left, prev - 1); PartSort3(a, prev + 1, right); } }
十分感谢您观看我的原创文章。
本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
如需引用,注明地址。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。