快速排序(划分函数)
时间: 2023-11-23 10:57:28 浏览: 29
快速排序是一种常用的排序算法,其核心思想是通过划分将待排序序列分成两个子序列,其中一个子序列的所有元素都比另一个子序列的所有元素小,然后再对这两个子序列分别进行排序,最终得到一个有序序列。划分函数是快速排序的核心,它的作用是将待排序序列划分成两个子序列。以下是一个快速排序的划分函数的示例代码:
```python
def partition(arr, low, high):
pivot = arr[low] # 选取第一个元素作为枢轴
while low < high:
while low < high and arr[high] >= pivot:
high -= 1
arr[low] = arr[high]
while low < high and arr[low] <= pivot:
low += 1
arr[high] = arr[low]
arr[low] = pivot
return low
```
该划分函数的输入参数为待排序序列arr、序列的起始位置low和序列的结束位置high。该函数首先选取序列的第一个元素作为枢轴,然后从序列的两端开始向中间扫描,将小于枢轴的元素移到序列的左边,将大于枢轴的元素移到序列的右边,最终将枢轴放到序列的中间位置,返回枢轴的下标。
相关问题
c语言快速排序的函数
C语言中的快速排序函数如下:
```c
// 交换两个元素的函数
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); // 指向小于枢轴的元素
for (int j = low; j <= high - 1; 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); // 对右半部分进行排序
}
}
```
使用示例:
```c
#include <stdio.h>
int main() {
int arr[] = {6, 2, 8, 4, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
这是一个经典的快速排序实现,通过选择一个枢轴元素,将数组划分为两个部分,左边的元素小于枢轴,右边的元素大于枢轴。然后递归地对两个部分进行排序,直到排序完成。
快速排序partITiron函数代码
以下是使用C++实现的快速排序Partition函数的代码:
```c++
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选取最后一个元素作为基准值
int i = low - 1; // i为小于等于基准值的元素的最后一个下标
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; // 返回基准值的下标
}
```
Partition函数的作用是将一个数组划分为小于等于基准值和大于基准值两部分,同时返回基准值的下标。在快速排序算法中,我们将数组不断地分成两部分并分别排序,直到数组全部有序。其中,Partition函数是快速排序算法的核心部分,它将时间复杂度从O(N^2)降低到了O(NlogN)。
相关推荐
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)