关系营销案例,东莞网站优化中易,自己做网站有名,网站备案接入方式引言#xff1a;在上一篇中我们详细介绍了快速排序和改进#xff0c;并给出了其中的一种实现方式-挖坑法 但其实快速排序有多种实现方式#xff0c;这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示#xff0c;下面的两种实现会容易许多。 … 引言在上一篇中我们详细介绍了快速排序和改进并给出了其中的一种实现方式-挖坑法 但其实快速排序有多种实现方式这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示下面的两种实现会容易许多。 一、左右指针法 首先进行“三数取中” 这样就完成了比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, arryleft);//最后两个指针重合将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);
}
好了这是本篇文章的所有内容了希望对你有所帮助
