设有数字序列a:{12, 8,1,3, 5, 10, 7, 13}, 写出快速排序一次快排的过程及结果(升序)
时间: 2023-10-06 13:13:29 浏览: 68
给定一个数列,用快速排序算法把它排成升序
5星 · 资源好评率100%
快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,以达到整个序列有序的目的。
以升序排序a序列为例,一次快排的过程如下:
1. 选择pivot(枢轴),将待排记录序列按照pivot分成两部分;
- 可以选择第一个元素作为pivot,即pivot=12;
- 也可以在待排记录序列中随机选择一个元素作为pivot。
2. 进行一趟快排,将待排记录序列分成两部分:
- 将比pivot小的元素都放到pivot左边;
- 将比pivot大的元素都放到pivot右边;
- pivot所在位置也就是分界点。
3. 递归进行快速排序:
- 对pivot左边的序列进行快速排序;
- 对pivot右边的序列进行快速排序。
一次快排的结果如下:
1. 选择pivot=12,待排记录序列为:{8,1,3,5,10,7,13};
2. 一趟快排后,序列变为:{8,1,3,5,7,10,13,12},pivot所在位置为7;
3. 对pivot左边的序列{8,1,3,5,7}进行递归快速排序,选择pivot=8;
4. 一次快排后,序列变为:{1,3,5,7,8},pivot所在位置为0;
5. 对pivot右边的序列{10,13,12}进行递归快速排序,选择pivot=10;
6. 一次快排后,序列变为:{10,13,12},pivot所在位置为0;
7. 对pivot左边的序列{13,12}进行递归快速排序,选择pivot=13;
8. 一次快排后,序列变为:{12,13},pivot所在位置为0;
9. 对pivot右边的序列{}(空序列)进行递归快速排序,返回空序列。
最终,整个序列有序,结果为:{1,3,5,7,8,10,12,13}。
阅读全文