用分治算法实现快速排序代码
时间: 2024-05-02 17:14:38 浏览: 88
快速排序是一种常用的排序算法,它通过分治的思想将一个大问题分解为多个小问题来解决。下面是用分治算法实现快速排序的代码:
```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) # 递归地对左右两部分进行快速排序
# 示例使用
arr = [5, 2, 9, 1, 7, 6, 3]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
相关问题
java分治算法实现快速排序
Java中的分治算法实现快速排序的步骤如下:
1. 选择一个基准元素(pivot),可以是数组中的任意一个元素。
2. 将数组分成两部分,小于等于基准元素的放在左边,大于基准元素的放在右边。
3. 对左右两部分分别进行递归调用快速排序算法,直到每个部分只有一个元素或为空。
4. 合并左右两部分,得到最终排序结果。
下面是Java代码实现快速排序的示例:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 获取基准元素的位置
quickSort(arr, low, pivotIndex - 1); // 对左侧子数组进行快速排序
quickSort(arr, pivotIndex + 1, high); // 对右侧子数组进行快速排序
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准元素
int i = low + 1; // 左指针
int j = high; // 右指针
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
swap(arr, i, j); // 交换左右指针所指向的元素
}
}
swap(arr, low, j); // 将基准元素放到正确的位置上
return j; // 返回基准元素的位置
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7, 6, 3};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
C++用分治算法快速排序
C++中使用分治算法实现快速排序,其基本思想是:选取一个基准元素,将待排序序列分成两个子序列,使得左边的子序列都小于等于基准元素,右边的子序列都大于等于基准元素,然后对左右两个子序列分别进行递归排序,最终得到有序序列。快速排序的时间复杂度为O(nlogn)。
具体实现步骤如下:
1. 选取一个基准元素,一般是第一个或最后一个元素。
2. 从序列的两端开始向中间扫描,将小于基准元素的元素交换到左边,将大于基准元素的元素交换到右边,直到左右两端相遇。
3. 将基准元素交换到中间位置,此时基准元素左边的元素都小于等于它,右边的元素都大于等于它。
4. 对左右两个子序列分别进行递归排序,直到子序列长度为1或0。
下面是C++代码实现快速排序:
```c++
#include<iostream>
using namespace std;
int partition(int r[], int low, int high)//划分函数
{
int i = low, j = high, pivot = r[low];
while (i < j) {
while (i < j && r[j] > pivot) //向左移动 ,停 j--;
if (i < j) swap(r[i++], r[j]);
while (i < j && r[i] <= pivot) //向右移动,停 i++;
if (i < j) swap(r[i], r[j--]);
}
return i;//返回最终划分完成后基准所在元素的位置
}
void QuickSort(int R[], int low, int high)
{
int mid;
if (low < high) {
mid = partition(R, low, high);
QuickSort(R, low, mid - 1);
QuickSort(R, mid + 1, high);
}
}
int main()
{
int i, N;
int *a;
cout << "请输入要排序数据的个数:";
cin >> N;
a = new int[N];
cout << "请输入要排序数据:";
for (i = 0; i < N; i++) cin >> a[i];
cout << endl;
QuickSort(a, 0, N - 1);
cout << "排序后序列为:" << endl;
for (i = 0; i < N; i++) {
if (i != 0) cout << " ";
cout << a[i];
}
cout << endl;
return 0;
}
```