快速排序的划分

Question

老师好，我按照双指针的方法自己实现了一下划分，但是有个问题，标记处这两个语句交换一下位置，交换前是有序正确的，交换后就是错的，我不知道为啥...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int _partition(int A[],int left,int right){     int temp = rand() % (right - left + 1) + left;           swap(A[left],A[temp]);           temp = left;           while(left < right){             //***这是交换前，是正确的         while(left < right && A[right] > A[temp]) right--;         while(left < right && A[left] <= A[temp]) left++;         //***这是交换后，是错误的         while(left < right && A[left] <= A[temp]) left++;         while(left < right && A[right] > A[temp]) right--;                   swap(A[left],A[right]);      }           swap(A[temp],A[left]);           return left; }

Answer 1

liuyubobobo 2021-01-25 01:51:10

你的这两种写法都是错误的。

为了测试方便，你可以把随机化去掉。int temp = left。

在这个只包含三个元素的测试用例下，这两个写法都不能成功完成排序：

3 1 2

你可以使用这个测试用例跟踪一下你的这个逻辑，看最终返回的索引是什么，A 被整理成了什么样子，返回的索引是否将将整个数组按照快速排序的要求，进行了切分，

继续加油！：）

• 提问者 托尔的眼镜 #1

  非常感谢！

Answer 2

提问者 托尔的眼镜 2021-01-25 02:21:51

好像可以啊，，我刚刚用3 1 2试了，一般的案例也试了，能正确排序，但是相对慢一点。。

刚才没打掉，打掉了也正常的

这个是随机生成的测试。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

int _partition4(int A[],int left,int right){     //int temp = rand() % (right - left + 1) + left;           //swap(A[left],A[temp]);           int temp = left;           while(left < right){                   while(left < right && A[left] <= A[temp]) left++;         while(left < right && A[right] >= A[temp]) right--;                   swap(A[left],A[right]);      }           if(A[left] <= A[temp]){         swap(A[temp],A[left]);         return left;     }else{         swap(A[temp],A[left-1]);         return left-1;     }  }   void _quickSort(int A[],int left,int right){     if(left >= right) return;           int p = _partition4(A,left,right);           _quickSort(A,left,p-1);     _quickSort(A,p+1,right); }   void quickSort(int A[],int n){     srand((unsigned)time(NULL));     _quickSort(A,0,n-1); }   int main(){           int A[3] = {3,1,2};           quickSort(A,3);           for(int i = 0;i<3;i++){         printf("%d ",A[i]);      }     int *arr = generateRandomArray(1000000,0,1000000);           testSort("quickSort",quickSort,arr,1000000);           return 0; }

• liuyubobobo #1

  我建议你随机生成数据，或者生成 n 个数字的全排列多测试一下，这个逻辑目测有问题的。最典型的是，标定点放在了最左边，但是下面的比较，标定点 left 参与了进去。不是从 left + 1 开始的。

• liuyubobobo #2

  你这个截图我看不见partition，随机有没有打掉？我这里测试有问题的。

• 提问者 托尔的眼镜 回复 liuyubobobo #3

  老师这个我考虑了，因为left这个标定点按照我的逻辑就是在左边的，所以排除不排除都行

点开查看后面1条评论

Answer 3

提问者 托尔的眼镜 2021-01-24 23:54:52

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

int _partition1(int A[],int left,int right){     int temp = rand() % (right - left + 1) + left;            swap(A[left],A[temp]);           temp = left;           while(left < right){                   while(left < right && A[left] <= A[temp]) left++;         while(left < right && A[right] >= A[temp]) right--;                   swap(A[left],A[right]);      }           if(A[left] <= A[temp]){         swap(A[temp],A[left]);         return left;     }else{         swap(A[temp],A[left-1]);         return left-1;     }       }

一点点试出来了(＠_＠;)，交换前能保证left及之前的数都小于等于选定的数，交换后不能，要再做一个判断

• liuyubobobo #1

  大赞！不过你这样写，其实没有解决我们引入双路快拍的核心原因：面对大量重复元素，这样写还是退化成 n^2 的算法了。可以使用课程中的方式做一下性能测试试试看？继续加油！：）

• 提问者 托尔的眼镜 回复 liuyubobobo #2

  嗯呐好的~