分析与解法 而partition过程有以下两种实现： 解法一 这样，两个指针分别从数组的头部和尾部向数组的中间移动，如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。 思路有了，接下来，写代码实现： //判断是否为奇数 bool IsOddNumber(int data) { return data & 1 == 1; } //交换两个元素 void swap(int* x, int* y) { int temp = *x; *x = *y; *y = temp; } //奇偶互换 void OddEvenSort(int *pData, unsigned int length) { if (pData == NULL || length == 0) return; int *pBegin = pData; int *pEnd = pData + length - 1; while (pBegin < pEnd) { //如果pBegin指针指向的是奇数，正常，向右移 if (IsOddNumber(*pBegin)) { pBegin++; } //如果pEnd指针指向的是偶数，正常，向左移 else if (!IsOddNumber(*pEnd)) { pEnd--; } else { //否则都不正常，交换 swap(*pBegin, *pEnd); } } } 本方法通过头尾两个指针往中间扫描，一次遍历完成所有奇数偶数的重新排列，时间复杂度为O(n)。 partition分治过程，每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的序列，继而递归排序完整个数组。如下伪代码所示： PARTITION(A, p, r) 1 x ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5 then i ← i + 1 6 exchange A[i] <-> A[j] 7 exchange A[i + 1] <-> A[r] 8 return i + 1 举个例子如下：现要对数组data = {2, 8,7, 1, 3, 5, 6,
Read full article from The-Art-Of-Programming-By-July/02.06.md at master ・ julycoding/The-Art-Of-Programming-By-July ・ GitHub
No comments:
Post a Comment