排序的相关算法--快排2（非递归）【菜鸟学习日记】

今天接着上一篇，优化改进一下快排，以及非递归去实现，并且分析一下它的相关效率问题

上一篇我们用了三种方法实现了基础快排，但是也有一些问题要去进行改进

---

问题一、快排给数据时，如果遇到最坏的情况

这里我们要对快排算法进行分析

分析快排的时间效率，取决于进行了多少趟排序，也就是我们递归的深度

这里我们分析最好与最坏的情况

我们分别都来画图示意一下

1、快排最好的情况–每趟又能将所排的序列一分为二，将表分成两个大小相等的序列，类似于折半查找，效率为O（NlogN)

这个例子还不是最理想的，但大致就是像这个例子一样

2、快排的最坏情况–序列已经排好

第一趟进行n-1次比较，第二趟n-2 … (n-1)+(n-2)+…+1=n2/2

所以快排的效率就是O（logN)

---

如果是像这样的情况，第一次选key时，我们就要注意，不要选到9，所以我们写了一个函数，三数取中，避免我们选到当前待排序列的最大或最小

//三数取中（优化快排的最坏情况） int GetMidIndex(int*a, int left, int right) { int mid = left + ((right - left) >> 1); //left mid right //三个数比大小，取中数，这样就可以避免掉最坏的情况 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left]<a[right]) { return right; } else { return left; } } else //left>mid { if (a[mid] > a[right]) { return mid; } else if (a[left]>a[right]) { return right; } else { return left; } } }

---

问题二、对于栈，害怕栈溢出的优化

对于小区间用插入排序

//对于递归版的再优化，少用栈帧 void QuickSortBetter(int*a, int left, int right) { //a不能为空 assert(a); //a不能只有一个数 if (left >= right) return; //小区间进行优化，不用递归更快 if (right - left < 10) { //小区间用插入排序 InsertSort(a + left, right - left + 1); } else { int div = _PartSort2(a, left, right); //再排剩下的左边的和右边的区域 QuickSortBetter(a, left, div - 1); QuickSortBetter(a, div + 1, right); } }

还有就是非递归的实现

//非递归实现快排--用栈 void QuickSortNonR(int* a, int begin, int end) { stack<int> s; if (begin < end) { s.push(end); s.push(begin); } //当栈里还有数，说明还有待排列的区间 while (!s.empty()) { int left = s.top(); s.pop(); int right = s.top(); s.pop(); int div = _PartSort2(a, left, right); if (left < div - 1) //说明左区域还有至少两个数，还要排,将其Push,待排 { s.push(div - 1); s.push(left); } if (div + 1 < right) { s.push(right); s.push(div + 1); } } //排列完成 }