帮忙写一个快速排序代码。
时间: 2024-05-02 16:18:27 浏览: 14
下面是Python语言的快速排序代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
```
该代码使用递归的方式实现了快速排序。首先,如果数组的长度小于等于1,则直接返回该数组,不需要排序。然后选择数组中间的元素作为基准值,将数组分为三部分:小于基准值的部分、等于基准值的部分和大于基准值的部分。接着,对小于基准值的部分和大于基准值的部分递归调用快速排序函数,最后将三部分合并起来返回即可。
相关问题
用Python写一个快速排序代码
以下是Python实现的快速排序代码:
```python
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quicksort(left) + [pivot] + quicksort(right)
```
快速排序的思路是将一个数组分成两个子数组,其中一个子数组的所有元素都小于另一个子数组的所有元素,然后对这两个子数组递归地进行快速排序。在上述代码中,pivot是选定的基准元素。在一次快速排序中,我们将数组中小于pivot的元素放到左边的子数组中,将大于pivot的元素放到右边的子数组中。最后,我们将这三个数组拼接在一起,返回一个完全排序的数组。
为了实现快速排序的递归过程,我们需要将左右子数组传递给quick排序函数,直到数组的长度小于或等于1。在这种情况下,我们可以直接返回数组,因为它已经被排序。
写一个快速排序代码 c++
好的,以下是快速排序的 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
int main() {
int arr[] = { 5, 2, 9, 3, 7, 6, 1, 8, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
```
快速排序的时间复杂度为 O(nlogn),是一种性能较好的排序算法。
相关推荐
![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_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)