{57, 68, 59, 52, 72, 28, 96, 33, 24}快速排序过程
时间: 2023-10-08 07:14:18 浏览: 62
快速排序 java代码
快速排序的过程如下:
1. 选择一个基准数,一般选择第一个数,即57;
2. 将所有比基准数小的数放在基准数前面,比基准数大的数放在基准数后面。具体方法是维护两个指针,一个指针从左边开始遍历,一个指针从右边开始遍历,当左边的指针指向的数比基准数大,右边的指针指向的数比基准数小,就交换这两个数;
3. 重复第2步,直到左右两个指针相遇,此时基准数的位置就确定了;
4. 对基准数左边的子数组和右边的子数组分别进行递归排序。
按照以上过程对给定序列{57, 68, 59, 52, 72, 28, 96, 33, 24}进行快速排序的过程如下:
1. 基准数为57,左指针指向57,右指针指向24;
2. 左指针指向68,右指针指向33,交换这两个数,得到{57, 33, 59, 52, 72, 28, 96, 68, 24};
3. 左指针指向59,右指针指向28,交换这两个数,得到{57, 33, 28, 52, 72, 59, 96, 68, 24};
4. 左指针指向52,右指针指向72,不交换,继续移动指针;
5. 左指针指向72,右指针指向59,交换这两个数,得到{57, 33, 28, 52, 59, 72, 96, 68, 24};
6. 左指针指向96,右指针指向68,交换这两个数,得到{57, 33, 28, 52, 59, 72, 68, 96, 24};
7. 左指针指向68,右指针指向24,交换这两个数,得到{57, 33, 28, 52, 59, 24, 68, 96, 72};
8. 左指针指向24,右指针指向59,交换这两个数,得到{24, 33, 28, 52, 57, 59, 68, 96, 72};
9. 左指针指向57,右指针指向68,不交换,继续移动指针;
10. 左指针指向59,右指针指向96,不交换,继续移动指针;
11. 左右指针相遇,此时基准数的位置确定,左边的子数组为{24, 33, 28, 52, 57},右边的子数组为{59, 68, 96, 72};
12. 对左边的子数组进行递归排序,基准数为24,左边的子数组为{33, 28},右边的子数组为{52, 57};
13. 对左边的子数组进行递归排序,基准数为33,左边的子数组为{28},右边的子数组为{52, 57};
14. 对左边的子数组进行递归排序,基准数为28,左边的子数组为空,右边的子数组为{52, 57};
15. 对右边的子数组进行递归排序,基准数为52,左边的子数组为空,右边的子数组为{57};
16. 对右边的子数组进行递归排序,基准数为57,左边的子数组为空,右边的子数组为空;
17. 将左边的子数组{28}和右边的子数组{52, 57}合并,得到{28, 52, 57};
18. 将左边的子数组{33, 28}和右边的子数组{52, 57}合并,得到{28, 33, 52, 57};
19. 对右边的子数组进行递归排序,基准数为59,左边的子数组为{68, 72},右边的子数组为{96};
20. 对左边的子数组进行递归排序,基准数为68,左边的子数组为空,右边的子数组为{72};
21. 对右边的子数组进行递归排序,基准数为72,左边的子数组为空,右边的子数组为空;
22. 将左边的子数组{68}和右边的子数组{72}合并,得到{68, 72};
23. 将左边的子数组{28, 33, 52, 57}和右边的子数组{68, 72}合并,得到{28, 33, 52, 57, 68, 72};
24. 对右边的子数组进行递归排序,基准数为96,左边的子数组为空,右边的子数组为空;
25. 将左边的子数组{59, 68, 72}和右边的子数组{96}合并,得到{59, 68, 72, 96};
26. 最终得到有序序列{24, 28, 33, 52, 57, 59, 68, 72, 96}。
阅读全文