快速排序
快速排序是建立在冒泡排序基础上的一种排序方法
基本思想 :通过一趟排序将要排序的数据分割成独立的两部分
其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现方法：
1.选择一个基准元素，通常选择第一个元素或者最后一个元素。
2.比较排序，将小于基准元素的数据移到左边，大于基准元素的数据移到右边。
3.再次对左右两边的数据进行排序。
4.重复步骤2和3，直到整个数据变成有序序列。
通关代码
int partition_array(int *arr, int l, int r)
// 编程实现arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大
// 返回基准所处位置
{
// 请在这里补充代码，完成本关任务
// 基准元素
int pivot = arr[l];
// 左右两边的指针
int i = l + 1;
int j = r;
// 将arr[l+1, r]分为两部分，左边比pivot小，右边比pivot大
while (i <= j)
{
// 左边找到一个比pivot大的元素
while (i <= r && arr[i] <= pivot)
{
i++;
}
// 右边找到一个比pivot小的元素
while (j >= l + 1 && arr[j] >= pivot)
{
j--;
}
// 如果左边比pivot大，右边比pivot小，交换两个元素
if (i < j)
{
swap(arr[i], arr[j]);
}
}
// 将pivot放到正确的位置
swap(arr[l], arr[j]);
// 返回pivot所处位置
return j;
}
int *quick_sort(int *arr, int l, int r)
// 基于partition_array函数编程实现快速排序：自上而下的递归方法
// 函数参数：有序数组arr 初始l=0，r=n-1
// 函数返回值：返回从小到大排序后的数组
{
// 请在这里补充代码，完成本关任务
if (l >= r)
{
return arr;
}
// 分区
int pivot = partition_array(arr, l, r);
// 左边排序
quick_sort(arr, l, pivot - 1);
// 右边排序
quick_sort(arr, pivot + 1, r);
return arr;
}
完整代码
#include#include #include using namespace std; void print_array(int *arr, int n); // 打印数组 int partition_array(int *arr, int l, int r); // arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大 // 返回基准所处位置 int *quick_sort(int *arr, int l, int r); // 快速排序：自上而下的递归方法，初始l=0，r=n-1 void print_array(int *arr, int n) // 打印数组 { if (n == 0) { printf("ERROR: Array length is ZEROn"); return; } printf("%d", arr[0]); for (int i = 1; i < n; i++) { printf(" %d", arr[i]); } printf("n"); } int partition_array(int *arr, int l, int r) // 编程实现arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大 // 返回基准所处位置 { // 请在这里补充代码，完成本关任务 // 基准元素 int pivot = arr[l]; // 左右两边的指针 int i = l + 1; int j = r; // 将arr[l+1, r]分为两部分，左边比pivot小，右边比pivot大 while (i <= j) { // 左边找到一个比pivot大的元素 while (i <= r && arr[i] <= pivot) { i++; } // 右边找到一个比pivot小的元素 while (j >= l + 1 && arr[j] >= pivot) { j--; } // 如果左边比pivot大，右边比pivot小，交换两个元素 if (i < j) { swap(arr[i], arr[j]); } } // 将pivot放到正确的位置 swap(arr[l], arr[j]); // 返回pivot所处位置 return j; } int *quick_sort(int *arr, int l, int r) // 基于partition_array函数编程实现快速排序：自上而下的递归方法 // 函数参数：有序数组arr 初始l=0，r=n-1 // 函数返回值：返回从小到大排序后的数组 { // 请在这里补充代码，完成本关任务 if (l >= r) { return arr; } // 分区 int pivot = partition_array(arr, l, r); // 左边排序 quick_sort(arr, l, pivot - 1); // 右边排序 quick_sort(arr, pivot + 1, r); return arr; } int main(int argc, const char *argv[]) { int n; scanf("%d", &n); int *arr; arr = (int *)malloc(sizeof(int) * n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } arr = quick_sort(arr, 0, n - 1); print_array(arr, n); return 0; }
