可以用dev-c++递归方法编写快速排序的程序
时间: 2024-10-10 12:11:49 浏览: 19
快速排序是一种常用的高效排序算法,它通过分治策略实现。在Dev-C++中使用递归方式编写快速排序的步骤如下:
1. 定义一个函数,通常命名为`quickSort`,接受一个数组、起始下标和结束下标作为参数。
2. **基础情况**:如果数组长度小于等于1,则直接返回,因为长度为1或0的数组已经是有序的。
3. **选择枢轴**:从给定区间内选取一个元素作为枢轴(通常是最后一个元素),常见的做法是将第一个元素与最后一个元素交换位置,然后选取中间的元素作为枢轴。
4. **分割数组**:创建两个指针,一个(`low`)从左向右找到第一个大于或等于枢轴的元素,另一个(`high`)从右向左找到第一个小于枢轴的元素。然后交换这两个元素,使得枢轴右侧始终都是比它大的元素,左侧总是比它小的元素。
5. **递归调用**:对`low`到`high-1`的子数组和`high+1`到最后的子数组分别递归调用`quickSort`。
6. **合并结果**:当所有子数组都排好序后,整个数组也就被排序了。
下面是一个简单的Dev-C++代码示例:
```cpp
#include<iostream>
using namespace std;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; // increment index of smaller element
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[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
```