6-1 sdut-C语言实验-快速排序

6-1 sdut-C语言实验-快速排序

分数 20

全屏浏览

切换布局

作者 马新娟

单位 山东理工大学

本题要求实现一个快速排序函数。

给定 N ( N<= 100000 ) 个 int 范围内的整数，要求用快速排序对数据进行升序排列。

函数接口定义：

void Quick_sort (int array[], int l, int r);

其中 array[] 、 l 、r 都是用户传入的参数。 array[] 是需要排序的数组，数组长度不会超过100000； l 和 r 是需要进行排序的左端点和右端点。

裁判测试程序样例：

#include <stdio.h>

void Quick_sort (int array[], int l, int r);

int main()
{

int N, array[100000];
scanf("%d", &N);
for(int i=0; i<N; i++)
{
scanf("%d", &array[i]);
}

Quick_sort(array, 0, N-1);

for(int i=0; i<N; i++)
{
printf("%d ", array[i]);
}
printf("\n");
return 0;
}

/* 请在这里填写答案 */

###输入样例：

1. 8
2. 49 38 65 97 76 13 27 49

###输出样例：

13 27 38 49 49 65 76 97

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

void Quick_sort (int array[], int l, int r)
{
    if(l>=r)
        return;
    int l1=l;
    int r1=r;
    int p=array[l];
    while(l1<r1)
    {
        while(array[r1]>p&&l1<r1)
        {
            r1--;
        }
        if(l1<r1)
        {
            array[l1]=array[r1];
            l1++;
        }
        while(array[l1]<p&&l1<r1)
        {
            l1++;
        }
        if(l1<r1)
        {
            array[r1]=array[l1];
            r1--;
        }
 
    }
    array[r1]=p;
//max
    Quick_sort ( array, l, l1-1);
    Quick_sort ( array, r1+1, r);
 
}

void Quick_sort(int array[], int l, int r) {

   // 基础条件：如果范围无效，立即返回。

   if (l >= r)

       return;

   // 初始化两个指针和枢纽元（pivot）。

   int l1 = l;

   int r1 = r;

   int p = array[l]; // 选择第一元素作为枢纽元。

   // 分区过程。

   while (l1 < r1) {

       // 将右指针向左移动，直到找到小于或等于枢纽元的元素。

       while (array[r1] > p && l1 < r1) {

           r1--;

       }

       // 如果左指针的元素小于枢纽元并且右指针还没有越过左指针，就交换它们。

       if (l1 < r1) {

           array[l1] = array[r1];

           l1++;

       }

       // 将左指针向右移动，直到找到大于枢纽元的元素。

       while (array[l1] < p && l1 < r1) {

           l1++;

       }

       // 如果右指针的元素大于枢纽元并且左指针还没有越过右指针，就交换它们。

       if (l1 < r1) {

           array[r1] = array[l1];

           r1--;

       }

   }

   // 将枢纽元放到正确的位置。

   array[r1] = p;

   // 递归地将快速排序应用于子数组。

   Quick_sort(array, l, r1 - 1);

   Quick_sort(array, r1 + 1, r);

}