数据结构—快速排序（续）

引言：在上一篇中我们详细介绍了快速排序和改进，并给出了其中的一种实现方式-挖坑法

但其实快速排序有多种实现方式，这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示，下面的两种实现会容易许多。

 一、左右指针法

 首先进行“三数取中”

 

 

这样就完成了比4小的在左边，比4大的在右边。

就继续递归就好了。

下面是代码：

int mid_quick_number(int* arry, int left, int right) {int mid = left + (right - left >> 1);//去中间数防止普通求中间数溢出问题,//同时注意优先级，+ -的优先级高于》《if (arry[mid] > arry[left]) {if (arry[right] > arry[mid]) {mid = mid;}else if(arry[right]>arry[left]){mid = right;}else {mid = left;}}else {if (arry[right] < arry[mid]) {mid = mid;}else if (arry[right] > arry[left]) {mid = left;}else {mid = right;}}return mid;
}
//左右指针法
void dfs_quick_sort2(int* arry, int left, int right) {if ((right - left) <= 0)return;int mid = mid_quick_number(arry, left, right);swap(arry + mid, arry + left);int key = arry[left];int start = left;int end = right;while (start < end) {while (start < end && key <= arry[end]) {end--;}//右指针去找比key小的，停下while (start < end && key >= arry[start]) {start++;}//左指针去找大的，停下swap(arry + start, arry + end);//交换大的和小的}swap(arry + end, arry+left);//最后两个指针重合，将key与right或左的值交换dfs_quick_sort2(arry, left, start - 1);dfs_quick_sort2(arry, start + 1, right);
}

二、前后指针法

 

 

这样就可以把它拆分成两段，在对这两段进行递归即可。

 下面来看代码：

//前后指针法
void dfs_quick_sort3(int* arry, int left, int right) {if ((right - left) <= 0)return;int mid = mid_quick_number(arry, left, right);swap(arry + mid, arry + left);int key = arry[left];int cur = left;int pre = left - 1;while (cur <= right) {while (cur <= right && arry[cur] >= key) {cur++;}if (cur <= right) {pre++;swap(arry + cur, arry + pre);}}if (pre == left-1)pre++;dfs_quick_sort3(arry, left, pre);dfs_quick_sort3(arry, pre + 1, cur - 1);
}

好了，这是本篇文章的所有内容了，希望对你有所帮助！