C++ 双指针算法详解：原理、应用及快速排序和归并排序实现

C++\u53cc\u6307\u9488\u7b97\u6cd5\u89e3\u6790\u548c\u5b9e\u73b0\n\n\u5f15\u8a00\uff1a\n\u53cc\u6307\u9488\u7b97\u6cd5\u662f\u4e00\u79cd\u5e38\u7528\u7684\u7b97\u6cd5\u6280\u5de7\uff0c\u5b83\u53ef\u4ee5\u5728\u201cO(n)\u201d\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u89e3\u51b3\u4e00\u4e9b\u95ee\u9898\u3002\u672c\u7bc7\u5c06\u4ecb\u7ecd\u53cc\u6307\u9488\u7b97\u6cd5\u7684\u57fa\u672c\u539f\u7406\u548c\u5e38\u89c1\u5e94\u7528\uff0c\u5e76\u7ed9\u51fa\u5feb\u901f\u6392\u5e8f\u548c\u56de\u5408\u6392\u5e8f\u7684\u5b9e\u73b0\u4ee3\u7801\u3002\n\n\u4e00\u3001\u53cc\u6307\u9488\u7b97\u6cd5\u7684\u57fa\u672c\u539f\u7406\n\u53cc\u6307\u9488\u7b97\u6cd5\u662f\u6307\u5728\u6570\u7ec4\u6216\u94fe\u6570\u7ec4\u4e2d\u4f7f\u7528\u4e24\u4e2a\u6307\u9488\u6765\u89e3\u51b3\u95ee\u9898\u7684\u4e00\u79cd\u7b97\u6cd5\u6280\u5de7\u3002\u5b83\u7684\u57fa\u672c\u539f\u7406\u662f\u901a\u8fc7\u63a7\u5236\u4e24\u4e2a\u6307\u9488\u7684\u79fb\u52a8\u6765\u8fbe\u5230\u9884\u671f\u7684\u76ee\u6807\uff0c\u5e38\u5e38\u6709\u4ee5\u4e0b\u51e0\u79cd\u60c5\u51b5\uff1a\n1\u3001\u4e24\u4e2a\u6307\u9488\u4ece\u6570\u7ec4\u7684\u4e24\u7aef\u5411\u4e2d\u95f4\u79fb\u52a8\uff0c\u76f4\u5230\u76f8\u9047\u6216\u4ea4\u53c9\u3002\n2\u3001\u4e00\u4e2a\u6307\u9488\u5728\u6570\u7ec4\u4e2d\u5411\u524d\u79fb\u52a8\uff0c\u53e6\u4e00\u4e2a\u6307\u9488\u5728\u6570\u7ec4\u4e2d\u5411\u540e\u79fb\u52a8\u3002\n3\u3001\u4e00\u4e2a\u6307\u9488\u5728\u6570\u7ec4\u4e2d\u6309\u67d0\u79cd\u6761\u4ef6\u79fb\u52a8\uff0c\u53e6\u4e00\u4e2a\u6307\u9488\u6309\u53e6\u4e00\u79cd\u6761\u4ef6\u79fb\u52a8\u3002\n\n\u4e8c\u3001\u53cc\u6307\u9488\u7b97\u6cd5\u7684\u5e38\u89c1\u5e94\u7528\n1\u3001\u5224\u65ad\u6570\u7ec4\u4e2d\u662f\u5426\u5b58\u5728\u67d0\u4e2a\u5143\u7d20\uff1a\n \u4f7f\u7528\u4e24\u4e2a\u6307\u9488\u5206\u522b\u6307\u5411\u6570\u7ec4\u7684\u5934\u548c\u5c3e\uff0c\u7136\u540e\u6839\u636e\u9898\u76ee\u8981\u6c42\u79fb\u52a8\u6307\u9488\uff0c\u6700\u7ec8\u5224\u65ad\u662f\u5426\u627e\u5230\u76ee\u6807\u5143\u7d20\u3002\n\n2\u3001\u627e\u5230\u6570\u7ec4\u4e2d\u7684\u4e24\u4e2a\u6570\u4e4b\u548c\uff1a\n \u4f7f\u7528\u4e24\u4e2a\u6307\u9488\u5206\u522b\u6307\u5411\u6570\u7ec4\u7684\u5934\u548c\u5c3e\uff0c\u6839\u636e\u4e24\u6570\u4e4b\u548c\u4e0e\u76ee\u6807\u503c\u7684\u5173\u7cfb\u79fb\u52a8\u6307\u9488\uff0c\u6700\u7ec8\u627e\u5230\u76ee\u6807\u5143\u7d20\u3002\n\n3\u3001\u5224\u65ad\u94fe\u6570\u7ec4\u662f\u5426\u6709\u73af\uff1a\n \u4f7f\u7528\u4e24\u4e2a\u6307\u9488\uff0c\u4e00\u4e2a\u6307\u9488\u6bcf\u6b21\u79fb\u52a8\u4e00\u4e2a\u8282\u70b9\uff0c\u53e6\u4e00\u4e2a\u6307\u9488\u6bcf\u6b21\u79fb\u52a8\u4e24\u4e2a\u8282\u70b9\uff0c\u5982\u679c\u4e24\u4e2a\u6307\u9488\u80fd\u591f\u76f8\u9047\uff0c\u5219\u94fe\u6570\u7ec4\u6709\u73af\u3002\n\n\u4e09\u3001\u5feb\u901f\u6392\u5e8f\u7684\u5b9e\u73b0\u4ee3\u7801\n\u5feb\u901f\u6392\u5e8f\u662f\u4e00\u79cd\u5e38\u7528\u7684\u6392\u5e8f\u7b97\u6cd5\uff0c\u5b83\u7684\u57fa\u672c\u601d\u8def\u662f\u9009\u62e9\u4e00\u4e2a\u5143\u7d20\u4f5c\u4e3a\u57fa\u51c6\uff0c\u5c06\u6bd4\u57fa\u51c6\u5c0f\u7684\u5143\u7d20\u653e\u5728\u57fa\u51c6\u7684\u5de6\u4fa7\uff0c\u6bd4\u57fa\u51c6\u5927\u7684\u5143\u7d20\u653e\u5728\u57fa\u51c6\u7684\u53f3\u4fa7\uff0c\u7136\u540e\u5bf9\u5de6\u53f3\u4e24\u4e2a\u5b50\u6570\u7ec4\u8fdb\u884c\u9000\u5f52\u6392\u5e8f\u3002\n\n\u4ee5\u4e0b\u662f\u4f7f\u7528\u53cc\u6307\u9488\u7b97\u6cd5\u5b9e\u73b0\u7684\u5feb\u901f\u6392\u5e8f\u7684\u201cC++\u201d\u4ee3\u7801\uff1a\n\n```cppvoid quickSort(vector& nums, int left, int right) { if (left >= right) { return; } int pivot = nums[left]; // \u9009\u62e9\u7b2c\u4e00\u4e2a\u5143\u7d20\u4f5c\u4e3a\u57fa\u51c6 int i = left, j = right; while (i < j) { while (i < j && nums[j] >= pivot) { j--; } if (i < j) { nums[i] = nums[j]; i++; } while (i < j && nums[i] < pivot) { i++; } if (i < j) { nums[j] = nums[i]; j--; } } nums[i] = pivot; quickSort(nums, left, i - 1); quickSort(nums, i + 1, right);}

\n\n\u56db\u3001\u56de\u5408\u6392\u5e8f\u7684\u5b9e\u73b0\u4ee3\u7801\n\u56de\u5408\u6392\u5e8f\u662f\u4e00\u79cd\u7a33\u5b9a\u7684\u6392\u5e8f\u7b97\u6cd5\uff0c\u5b83\u7684\u57fa\u672c\u601d\u8def\u662f\u5c06\u6570\u7ec4\u5206\u6210\u4e24\u4e2a\u5b50\u6570\u7ec4\uff0c\u5206\u522b\u8fdb\u884c\u6392\u5e8f\uff0c\u7136\u540e\u5c06\u4e24\u4e2a\u5b50\u6570\u7ec4\u5408\u5e76\u6210\u4e00\u4e2a\u6709\u5e8f\u7684\u6570\u7ec4\u3002\n\n\u4ee5\u4e0b\u662f\u4f7f\u7528\u53cc\u6307\u9488\u7b97\u6cd5\u5b9e\u73b0\u7684\u56de\u5408\u6392\u5e8f\u7684\u201cC++\u201d\u4ee3\u7801\uff1a\n\n```cppvoid merge(vector& nums, int left, int mid, int right) { vector temp(right - left + 1); int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (nums[i] < nums[j]) { temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; } } while (i <= mid) { temp[k++] = nums[i++]; } while (j <= right) { temp[k++] = nums[j++]; } for (int p = 0; p < temp.size(); p++) { nums[left + p] = temp[p]; }}

void mergeSort(vector& nums, int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right);}

\n\n\u7ed3\u8a00\uff1a\n\u53cc\u6307\u9488\u7b97\u6cd5\u662f\u4e00\u79cd\u975e\u5e38\u5b9e\u7528\u7684\u7b97\u6cd5\u6280\u5de7\uff0c\u5728\u89e3\u51b3\u4e00\u4e9b\u7279\u5b9a\u95ee\u9898\u65f6\u53ef\u4ee5\u5927\u5927\u63d0\u9ad8\u7b97\u6cd5\u7684\u6548\u7387\u3002\u672c\u7bc7\u4ecb\u7ecd\u4e86\u53cc\u6307\u9488\u7b97\u6cd5\u7684\u57fa\u672c\u539f\u7406\u548c\u5e38\u89c1\u5e94\u7528\uff0c\u5e76\u7ed9\u51fa\u4e86\u5feb\u901f\u6392\u5e8f\u548c\u56de\u5408\u6392\u5e8f\u7684\u5b9e\u73b0\u4ee3\u7801\u3002\u5e0c\u671b\u672c\u7bc7\u5bf9\u60a8\u4e86\u89e3\u548c\u638c\u63e1\u53cc\u6307\u9488\u7b97\u6cd5\u6709\u6240\u5e2e\u52a9\u3002\n\n\u53c2\u8003\u8d44\u6599\uff1a\n1\u3001\u201chttps://www.geeksforgeeks.org/two-pointers-technique/\u201d\n2\u3001\u201chttps://leetcode-cn.com/tag/two-pointers/\u201