企业网站建设600元,网络服务商简称,wordpress点评,做影视网站该怎么发展什么是快速排序#xff1f;
快速排序#xff08;Quick Sort#xff09; 是一种高效的分治法排序算法。它通过选择一个基准元素#xff0c;将数组分成小于基准的部分和大于基准的部分#xff0c;然后递归地对这些部分进行排序#xff0c;最终将它们合并起来#xff0c;完…什么是快速排序
快速排序Quick Sort 是一种高效的分治法排序算法。它通过选择一个基准元素将数组分成小于基准的部分和大于基准的部分然后递归地对这些部分进行排序最终将它们合并起来完成排序。
快速排序的步骤
1、选择枢轴基准元素从待排序的数组中选择一个元素作为枢轴。常见的选择方式是取第一个元素、最后一个元素、随机元素或通过三数取中法选择中间值作为枢轴。
2、划分操作将数组中的元素按照与枢轴的大小关系进行划分将小于等于枢轴的元素放在枢轴的左侧大于枢轴的元素放在枢轴的右侧。这一步骤通常使用双指针法来实现即从数组的两端同时向中间遍历交换不符合条件的元素直到两个指针相遇。
3、递归排序对划分后的左侧子数组和右侧子数组分别进行递归调用快速排序算法重复上述步骤直到子数组的长度为1或为空即无法再继续划分。
4、合并结果当递归调用完成后所有的子数组都已经有序。最后将左侧子数组、枢轴元素和右侧子数组依次合并起来即可得到完整的有序数组。
举例说明
假设我们有以下待排序的数组[49, 38, 65, 97, 76, 27, 13, 49]
1、选择基准 选择数组的第一个元素 49 作为基准。
2、分割 将数组分割成两部分小于 49 的部分为 [38, 27, 13]大于 49 的部分为 [65, 97, 76, 49]。
3、递归排序 对小于基准的部分 [38, 27, 13] 进行递归排序。 选择基准 在小于部分中选择第一个元素 38 作为基准。 分割 分割后小于 38 的部分为 [27, 13]大于 38 的部分为空。 递归排序 对小于 38 的部分 [27, 13] 进行排序得到 [13, 27]。
4、递归排序 对大于基准的部分 [65, 97, 76, 49] 进行递归排序。 选择基准 在大于部分中选择第一个元素 65 作为基准。 分割 分割后小于 65 的部分为 [49]大于 65 的部分为 [97, 76]。 递归排序 对小于 65 的部分 [49] 进行排序得到 [49]。 递归排序 对大于 65 的部分 [97, 76] 进行排序得到 [76, 97]。
5、合并 将小于基准的部分 [13, 27]、基准 38、大于基准的部分 [49] 合并得到 [13, 27, 38, 49]。
6、合并 将小于基准的部分 [13, 27, 38, 49]、基准 49、大于基准的部分 [65, 97, 76] 合并得到 [13, 27, 38, 49, 65, 97, 76]。
最终数组 [49, 38, 65, 97, 76, 27, 13, 49] 经过快速排序变为有序数组 [13, 27, 38, 49, 65, 76, 97, 49]。
示例代码
#include stdio.h// 快速排序算法
void QuickSort(int A[], int low, int high);// 划分函数将数组划分为两个子数组
int Partition(int A[], int low, int high);// 交换数组中的两个元素
void Swap(int A[],int a,int b);// 打印数组元素
void PrintfArray(int A[], int length);int main()
{int arr[] {49, 38, 65, 97, 76, 27, 13, 49};int length sizeof(arr) / sizeof(arr[0]);int i;QuickSort(arr, 0, length - 1);printf(排序后的数组);PrintfArray(arr,length);return 0;
} 划分函数的实现
//int Partition(int A[], int low, int high)
//{
// int pivot A[low]; // 选择第一个元素作为枢轴
// while (low high)
// {
// // 从右向左找到第一个小于等于枢轴的元素
// while (low high A[high] pivot)
// --high;
// A[low] A[high]; // 将该元素放入枢轴左侧
//
// // 从左向右找到第一个大于等于枢轴的元素
// while (low high A[low] pivot)
// low;
// A[high] A[low]; // 将该元素放入枢轴右侧
// }
// A[low] pivot; // 将枢轴元素放入正确的位置
// return low; // 返回枢轴的最终位置
//} 快速排序算法的实现
//void QuickSort(int A[], int low, int high)
//{
// if (low high)
// {
// int pivotpos Partition(A, low, high); // 划分数组
// QuickSort(A, low, pivotpos - 1); // 对枢轴左侧子数组进行快速排序
// QuickSort(A, pivotpos 1, high); // 对枢轴右侧子数组进行快速排序
// }
//}// 划分函数的实现
// 参数:
// A: 数组
// start: 子数组的起始索引
// end: 子数组的结束索引
// 返回值:
// 划分后枢轴的索引位置// 规则如果当前元素小于基准数时首先分割指示器右移一位
// 在A的基础之上如果当前元素下标大于分割指示器下标时当前元素和分割指示器所指元素交换
int Partition(int A[], int start, int end)
{if(startend)return start;int pivotstart; // 选择第一个元素作为枢轴int zoneIndexstart-1; // 将小于枢轴的元素放在左侧区域Swap(A,pivot,end); // 将枢轴元素放到最右侧int i;for(istart; iend; i) // 将小于等于枢轴的元素移到左侧区域{if(A[i]A[end]){zoneIndex;if(izoneIndex)Swap(A,i,zoneIndex);}}return zoneIndex; // 返回枢轴的最终位置
}// 快速排序算法的实现
// 参数:
// A: 数组
// start: 子数组的起始索引
// end: 子数组的结束索引
void QuickSort(int A[], int start, int end)
{int zoneIndexPartition(A,start,end); // 划分数组if(zoneIndexstart)QuickSort(A,start,zoneIndex-1); // 对枢轴左侧子数组进行快速排序if(zoneIndexend)QuickSort(A,zoneIndex1,end); // 对枢轴右侧子数组进行快速排序
}// 交换数组中的两个元素
// 参数:
// A: 数组
// a, b: 需要交换的元素索引
void Swap(int A[],int a,int b)
{int temp;tempA[a];A[a]A[b];A[b]temp;
}// 打印数组元素
// 参数:
// A: 数组
// length: 数组长度
void PrintfArray(int A[],int length)
{int i0;for(i0; ilength; i){printf(%d ,A[i]);}printf(\n);
}
