快速排序算法的实现。任意输入20个整数,对这20个整数进行快速排序。要求使用末元素作为划分基准。
时间: 2024-05-15 12:15:46 浏览: 12
快速排序算法的实现:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left, right = [], []
for num in arr[:-1]:
if num < pivot:
left.append(num)
else:
right.append(num)
return quick_sort(left) + [pivot] + quick_sort(right)
```
其中,`arr`为待排序的数组,`pivot`为末元素作为划分基准,`left`和`right`分别为小于和大于基准的子数组。
对于给定的20个整数,可以通过以下代码进行快速排序:
```python
arr = [5, 9, 3, 7, 2, 8, 4, 1, 6, 0, 11, 15, 13, 17, 19, 12, 14, 16, 18, 10]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
输出结果为:
```
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
```
相关问题
快速排序算法的实现。任意输入20个整数,对这20个整数进行快速排序。要求使用末元素作为划分基准
快速排序是一种高效的排序算法,其基本思想是通过分治的方式将一个大问题分解成多个小问题,并通过递归的方式求解这些小问题,最终得到整个问题的解。
快速排序的具体实现如下:
1. 选择一个基准数,一般选择最后一个元素作为基准数;
2. 将数组分为左右两个子数组,使得左边子数组中的元素都小于基准数,右边子数组中的元素都大于等于基准数;
3. 递归地对左右子数组进行快速排序,直到子数组的长度为1或0。
以下是使用末元素作为划分基准的快速排序算法的实现:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[-1] # 选择末元素作为基准数
left = []
right = []
for i in range(len(arr)-1):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
# 测试
arr = [3,1,4,2,5,8,7,6,10,9,12,11,14,13,16,15,18,17,20,19]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
输出结果为:
```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
```
这样就完成了对任意输入20个整数的快速排序。
用c语言快速排序算法的实现任意输入20个整数,对这20个整数进行快速排序。要求使用末元素作为划分基准。
```c
#include <stdio.h>
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选取末元素作为划分基准
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[high]);
return i+1;
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
int main() {
int arr[20];
printf("请输入20个整数:\n");
for (int i = 0; i < 20; i++) {
scanf("%d", &arr[i]);
}
quicksort(arr, 0, 19);
printf("排序结果:\n");
for (int i = 0; i < 20; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)