{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 } 采用快速排序法,请写出经过一趟排序后的结果:
时间: 2023-09-25 15:12:11 浏览: 32
经过一趟排序后的结果为:
{ 31, 25, 18, 36, 47, 90, 65, 87, 79, 58 }
首先选取一个基准数,可以选择第一个数 47。然后从序列的左右两端开始扫描,设定两个指针 i 和 j,分别指向最左边和最右边。
从 j 开始向左扫描,直到找到一个数小于基准数 47,将其与基准数进行交换,然后 i 向右移动一位。
接着从 i 开始向右扫描,直到找到一个数大于基准数 47,将其与基准数进行交换,然后 j 向左移动一位。
重复上述过程,直到 i 和 j 相遇,此时将基准数与相遇的位置的数进行交换,就完成了一趟快速排序。
在本次排序中,经过一趟排序后,基准数 47 已经放置在了正确的位置,而序列被分成了左右两个子序列 [31, 25, 18, 36] 和 [90, 65, 87, 79, 58]。接下来可以对这两个子序列分别进行快速排序。
相关问题
给定一组整数: { 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 } 采用快速排序法,请写出经过一趟排序后的结果:和解析过程:
快速排序是一种基于分治思想的排序算法,它将原始数组划分成两个子数组,其中一个子数组的所有元素都比另一个子数组的所有元素小,然后递归地对两个子数组进行排序,直到整个数组都有序。
给定一组整数:{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 },第一趟快速排序的结果如下:
```
31, 25, 18, 36, 47, 90, 65, 87, 79, 58
```
解析:在第一趟快速排序中,我们选择数组的第一个元素47作为枢纽元素(pivot)。然后,我们将数组中小于等于枢纽元素的元素放在枢纽元素的左边,将大于枢纽元素的元素放在枢纽元素的右边。在这个过程中,我们使用两个指针i和j,分别从左往右和从右往左扫描数组,找到需要交换位置的元素。
具体地,我们首先从左往右扫描数组,找到第一个大于枢纽元素的元素36(i=3)。然后,从右往左扫描数组,找到第一个小于枢纽元素的元素31(j=7)。接下来,交换元素36和31的位置,此时数组变成了{ 47, 25, 87, 31, 90, 18, 65, 36, 79, 58 }。然后,继续从左往右扫描数组,找到第一个大于枢纽元素的元素90(i=4)。然后,从右往左扫描数组,找到第一个小于枢纽元素的元素58(j=9)。接下来,交换元素90和58的位置,此时数组变成了{ 47, 25, 87, 31, 58, 18, 65, 36, 79, 90 }。
最后,枢纽元素47和元素58交换位置,此时数组变成了{ 36, 25, 18, 31, 47, 58, 65, 87, 79, 90 }。现在,枢纽元素的位置已经确定了,小于枢纽元素的元素都在枢纽元素的左边,大于枢纽元素的元素都在枢纽元素的右边。接下来,我们递归地对枢纽元素的左边和右边的子数组进行快速排序。因此,第一趟快速排序后,数组的结果是31, 25, 18, 36, 47, 90, 65, 87, 79, 58。
请使用quick sort方法将数列65 58 95 10 57 62 13 106 78 23 85排序写出对应java代码
下面是使用快速排序算法对给定数列进行排序的Java代码:
```java
public class QuickSort {
public static void main(String[] args) {
int[] nums = {65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85};
quickSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
public static void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivot = nums[left]; // 以第一个元素为基准
int i = left + 1, j = right;
while (i <= j) {
while (i <= j && nums[i] < pivot) {
i++;
}
while (i <= j && nums[j] > pivot) {
j--;
}
if (i <= j) {
swap(nums, i, j);
i++;
j--;
}
}
swap(nums, left, j); // 将pivot归位
quickSort(nums, left, j - 1); // 对左边的子数组进行快排
quickSort(nums, j + 1, right); // 对右边的子数组进行快排
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```
输出结果为:[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)