快速排序数据结构排序算法优化
2017-11-29 15:22
79人阅读
评论(0)
收藏
分类:
快速排序初步了解:
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。后面将提供一种快排的优化方式可以尽量避免出现Ο(n2)的复杂度。
基本思路
1.先从数据当中找出一个数据作为参照数
2.然后开始分区操作,大于参照数的就放到参照数右边,小于参照数的就放到参照数的左边.
3.然后对左右分区继续进行该操作,知道区间里面只有一个数据的是时候,快排完成
排序效果:
一、左右指针法
<1>思路:给定一个数组,再给定左右区间的下标值left,right(此处我给的是左右闭区间),给定一个基准值为arr[right],接下来就是循环和递归的过程。单趟过程中,先让begin记录该区间的第一个下标(就像一个指针指向头一样),end记录最后一个值的下标,基准值为该区间的最后一个值。循环过程中,begin记录比基准值大的值,end记录比基准值小的值,判断如果begin和end还未相遇,则交换对应的值,再进行循环直至begin和end相遇。相遇后此时单趟排序完成,现在begin和end指向一个元素,该元素左侧都是比基准值小的值,右侧都是比基准值大的,将begin对应的值与基准值进行交换,开始递归左半区间和右半区间,重复上述过程。
<2>图示单趟过程:
整体过程如下:
1 5 6 2 7 4
1 2 6 5 7 4
1 2 4 5 7 6
1 2 4 5 6 7
<3>实现代码
- //左右指针法
- void LRPoint(int* arr, int left, int right)
- {
- if (left >= right)
- return;
- assert(arr);
- int begin = left;
- int end = right;
- int key = arr[end];
- while (begin < end)
- {
- while (begin < end && arr[begin] <= key)
- begin++;
- while (begin < end && arr[end] >= key)
- end--;
- if (begin < end)
- swap(arr[begin], arr[end]);
- }
- //begin end指向一起,与key交换
- swap(arr[begin], arr[right]);
- LRPoint(arr, left,begin - 1);
- LRPoint(arr, begin+1,right);
- }
二、挖坑法
<1>思路:大体上如同左右指针法,但是左右指针法是在begin和end符合条件的值后,将begin和end对应的值进行交换;而挖坑法则是边找边替换,在最后再将key填入坑中。图中橙色元素由于此处的值赋值到了别处,可以形象的看做是一个“坑”。
<2>图示单趟过程:
整体过程如下:
1 5 6 2 7 4
1 5 6 2 7 5
1 2 6 2 7 5
1 2 6 6 7 5
1 2 4 6 7 5
1 2 4 6 7 6
1 2 4 5 7 6
1 2 4 5 7 7
1 2 4 5 6 7
<3>实现代码
- void PitPoint(int* arr, int left, int right)
- {
- if (left >= right)
- return;
- int begin = left;
- int end = right;
- int key = arr[right];
- while (begin < end)
- {
- while (begin < end && arr[begin] <= key)
- begin++;
- arr[end] = arr[begin];
- while (begin < end && arr[end] >= key)
- end--;
- arr[begin] = arr[end];
- }
- arr[end] = key;
- PitPoint(arr, left, begin - 1);
- PitPoint(arr, begin + 1, right);
- }
三、前后指针法
<1>思路:一开始使用cur记录left位置,prev记录cur的前一个位置,利用cur来寻找比基准值小的值,需要注意的是只有当arr[cur] < arr[right]和++prev != cur两个条件都满足才进行交换,此处还涉及如果arr[cur] < arr[right]不满足则不进行prev++,当条件都满足时进行交换,出了循环后将基准值放在prev++的位置。看着代码自己缕一遍就会发现规律了。
<2>图示单趟过程:
整体过程如下:
1 5 6 2 7 4
1 2 6 5 7 4
1 2 4 5 7 6
1 2 4 5 6 7
<3>实现代码
- void FBPoint(int* arr, int left, int right)
- {
- if (left >= right)
- return;
- int cur = left;
- int prev = left - 1;
- while (cur < right)
- {
- if (arr[cur] < arr[right] && ++prev != cur)
- swap(arr[cur], arr[prev]);
- ++cur;
- }
- swap(arr[++prev], arr[right]);
- FBPoint(arr, left, prev - 1);
- FBPoint(arr, prev + 1, right);
- }
四、非递归实现
<1>思路:
用栈来模拟实现递归操作,每次从栈中取出对应的左右边界进行操作;在push边界的顺序与取栈顶数据作为左右边界的顺序要对应。
<2>实现代码:
- void NRQuickSort(int* arr, int sz)
- {
- assert(arr);
- stack<int> s;
- int left = 0;
- int right = sz;
- s.push(right);
- s.push(left);
- while (!s.empty())
- {
- left = s.top();
- s.pop();
- right = s.top();
- s.pop();
- if (left < right)
- {
- int begin = left;
- int end = right;
- int key = arr[right];
- while (begin < end)
- {
- //1,5,6,2,7,4
- while (begin < end && arr[begin] <= key)
- begin++;
- while (begin < end && arr[end] >= key)
- end--;
- if (begin < end)
- swap(arr[begin], arr[end]);
- }
- swap(arr[begin], arr[right]);
- s.push(right);
- s.push(begin + 1);
- s.push(begin - 1);
- s.push(left);
- }
- }
- }
五、优化
<1>通过三数取中法选取key的下标:
当按照上面的代码如果每次取key的时候取到了待排序列中最大的或者最小的. 也就是序列有序的时候,快速排序的时间复杂度为O(N^2),我们可以通过选择合适的key值来进行优化:也就是所谓的三数取中法(给定左右区间的下标,计算出中间下标,并返回这三个值中不大不小的那个),将该下标所对应的值和区间最右侧的值进行交换即可。拿左右指针法优化举例:
- int GetMid(int* a, int left, int right)
- {
- int mid = left + ((right - left) >> 1);
- // left mid
- if (a[left] < a[mid])
- {
- if (a[right] < a[left])
- return left;
- else if (a[right] > a[mid])
- return mid;
- else
- return right;
- }
- else
- {
- //mid left
- if (a[right] < a[mid])
- return mid;
- else if (a[right] < a[left])
- return left;
- else
- return right;
- }
- }
- void LRPoint(int* arr, int left, int right)
- {
- if (left >= right)
- return;
- assert(arr);
- int begin = left;
- int end = right;
- swap(arr[end], arr[GetMid(arr, left, right)]);
- int key = arr[end];
- while (begin < end)
- {
- while (begin < end && arr[begin] <= key)
- begin++;
- while (begin < end && arr[end] >= key)
- end--;
- if (begin < end)
- swap(arr[begin], arr[end]);
- }
- //begin end指向一起,与key交换
- swap(arr[begin], arr[right]);
- LRPoint(arr, left,begin - 1);
- LRPoint(arr, begin+1,right);
- }