题目描述
快速排序的练习
注意:
本题如果采用常规的快速排序(选取左端为基准)会导致超时,为了防止时间复杂度到达(O(n^2))
,所以选择中间元素为基准值较好
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5
(选择中间元素为基准)C代码
#include <stdio.h>
#include <stdlib.h>
void QuickSort(int* arr, int low, int high) {
if (low >= high)
{
return;
}
int pivot = arr[(low + high) / 2];//让基准元素为中间元素,这样就可以防止当序列基本有序时时间复杂度达到O(n^2)
//先让左右指针指向边界外(这样做的目的是防止后面大量的边界条件判断),然后开始时先移动左右指针,让其向中间走
int left = low - 1;
int right = high + 1;
while (left < right)
{
while (arr[++left] < pivot);//在左边找到比基准元素大的位置
while (arr[--right] > pivot);//在右边找到比基准元素小的位置
if (left < right)//左右都找到之后交换位置即可
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
QuickSort(arr, low, right);//递归处理左序列
QuickSort(arr, right+1, high);//递归处理右序列
}
int main() {
int n;
scanf("%d", &n);
int* arr = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
QuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
常规快排(选择左端为基准)C代码
//一趟划分
int Partition(int* arr, int low, int high) {
int pivot = arr[low];//选取最左边的元素作为基准元素
while (low < high)
{
while (low < high && arr[high] >= pivot) {//选择了最左边的元素作为基准元素,判断的时候从右边开始
high--;
}
arr[low] = arr[high];//将右端比基准小的元素移到左端
while (low < high && arr[low] <= pivot)
{
low++;
}
arr[high] = arr[low];//将左端比基准大的元素移到右端
}
//退出循环的时候此时low == high
arr[low] = pivot;//将基准元素归位
return low;
}
//快速排序
void QuickSort(int* arr, int low, int high) {
if (low < high)
{
int pivotpos = Partition(arr, low, high);//得到基准元素的下标;划分
QuickSort(arr, low, pivotpos - 1);//递归对左表划分
QuickSort(arr, pivotpos + 1, high);//递归对右表划分
}
}