: 对序列:(18,24,3,7,9,21,42,11,8)进行快速排序;
时间: 2024-05-22 07:10:29 浏览: 18
快速排序是一种基于分治思想的排序算法。其基本思路是选定一个基准元素,将序列中小于基准元素的部分放在前面,大于基准元素的部分放在后面,再对这两部分分别进行快速排序。以下是对给定序列进行快速排序的步骤:
1. 选定基准元素,可以选择第一个元素,即18;
2. 定义两个指针,i 和 j,分别指向序列的第一个元素和最后一个元素;
3. 指针 i 向右移动,直到找到一个大于等于基准元素的元素;
4. 指针 j 向左移动,直到找到一个小于等于基准元素的元素;
5. 如果 i < j,则交换元素 i 和 j;
6. 重复步骤 3-5 直到 i >= j;
7. 将基准元素和 j 指向的元素交换;
8. 对序列的左半段和右半段分别进行快速排序,直到序列完全有序。
按照上述步骤,对序列(18,24,3,7,9,21,42,11,8)进行快速排序的过程如下:
1. 选定基准元素 18;
2. i = 1,j = 9;
3. i 向右移动,直到找到元素 24;
4. j 向左移动,直到找到元素 8;
5. 交换元素 24 和 8;
6. i 向右移动,直到找到元素 21;
7. j 向左移动,直到找到元素 9;
8. 交换元素 21 和 9;
9. i 向右移动,直到找到元素 42;
10. j 向左移动,直到找到元素 7;
11. 交换元素 42 和 7;
12. i = j,循环结束;
13. 将基准元素 18 和 j 指向的元素 9 交换,序列变为(9,8,3,7,18,21,42,11,24);
14. 对左半段(9,8,3,7)进行快速排序,选定基准元素 9,序列变为(3,7,8,9),再对右半段(21,42,11,24)进行快速排序,选定基准元素 21,序列变为(11,21,24,42);
15. 最终,序列完全有序,为(3,7,8,9,11,21,24,42)。
因此,对序列(18,24,3,7,9,21,42,11,8)进行快速排序后得到的有序序列为(3,7,8,9,11,21,24,42)。