1. 快速排序

喜欢ヅ旅行 2022-04-02 08:47 80阅读 0赞

要求根据给定输入，按照课堂给定的快速排序算法进行排序，输出排序结果和median3的返回值。

注：1,cutoff值为5，不足cutoff使用插入排序。

2,输入、输出格式参见测试用例0。

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" rel="nofollow"><img alt="关于“测试输入”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" rel="nofollow"><img alt="关于“期待的输出”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“时间限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“内存限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" rel="nofollow"><img alt="关于“{$a} 个额外进程”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77937&amp;test=100765&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>41↵</li> 
     <li>17↵</li> 
     <li>34↵</li> 
     <li>0↵</li> 
     <li>19↵</li> 
     <li>#↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77937&amp;test=100765&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>After&nbsp;Sorting:↵</li> 
     <li>0&nbsp;17&nbsp;19&nbsp;34&nbsp;41&nbsp;↵</li> 
     <li>Median3&nbsp;Value:↵</li> 
     <li>none↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>测试用例 2</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77937&amp;test=100766&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>61↵</li> 
     <li>59↵</li> 
     <li>82↵</li> 
     <li>-10↵</li> 
     <li>31↵</li> 
     <li>-2↵</li> 
     <li>-3↵</li> 
     <li>10↵</li> 
     <li>2↵</li> 
     <li>108↵</li> 
     <li>12↵</li> 
     <li>80↵</li> 
     <li>-21↵</li> 
     <li>127↵</li> 
     <li>12↵</li> 
     <li>#↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77937&amp;test=100766&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>After&nbsp;Sorting:↵</li> 
     <li>-21&nbsp;-10&nbsp;-3&nbsp;-2&nbsp;2&nbsp;10&nbsp;12&nbsp;12&nbsp;31&nbsp;59&nbsp;61&nbsp;80&nbsp;82&nbsp;108&nbsp;127&nbsp;↵</li> 
     <li>Median3&nbsp;Value:↵</li> 
     <li>12&nbsp;-3&nbsp;61&nbsp;↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

#include <stdio.h>
    #include<stdlib.h>
    #include <string.h>
    int cutoff = 5;
    int numbers[1000], mid=0, midnumbers[100];
    
    void InsertSort(int num[],int left,int right){
        int temp, j;
        for(int i=left + 1; i<=right; i++){
            temp = num[i];
            for(j = i - 1;j >= 0 && num[j] > temp;j--)
            {
                num[j+1] = num[j];
            }
            if (j != i - 1)
                num[j+1] = temp;
        }
    }
    
    int  MidCheck(int numbers[], int left, int right)
    {
        int mid = (left + right) / 2;
        int temp[3];
        temp[2] = numbers[right];
        temp[1] = numbers[mid];
        temp[0] = numbers[left];
        for(int i=0;i<3;i++)
            for(int j=i+1;j<3;j++)
                if(temp[i]>temp[j]){
                    int a = temp[i];
                    temp[i]=temp[j];
                    temp[j]=a;
                }
        numbers[left] = temp[0];
        numbers[right] = temp[1];
        numbers[mid] = temp[2];
        
        return temp[1];
    }
    
    void Sort(int numbers[], int left, int right)
    {
        if (right - left < cutoff)
        {
            InsertSort(numbers, left, right);
        }
        else
        {
            midnumbers[mid++] = MidCheck(numbers, left, right);
        
            int pivot = numbers[right];
            int i = left ,j = right-1;
            while(1)
            {
                while (i < j && numbers[i] < pivot)i++;
                while (i < j && pivot < numbers[j])j--;
                if (i < j)
                {
                    int c = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = c;
                    i++,j--;
                }
                else break;
            }
            if (numbers[i] >= pivot)
            {
                numbers[right] = numbers[i];
                numbers[i] = pivot;
            }
            Sort(numbers, left, i-1);
            Sort(numbers, i+1, right);
        }
    }
    int main() {
        int count = 0;
        char x[20];
        while(1){
            scanf("%s",x);
            if(strcmp(x,"#")==0)
                break;
            numbers[count++] = atoi(x);
        }
    
        Sort(numbers,0,count-1);
        
        printf("After Sorting:\n");
        for(int i=0;i<count;i++){
            printf("%d ",numbers[i]);
        }
        printf("\nMedian3 Value:\n");
        if(mid > 0){
            for(int i=0;i<mid;i++)
                printf("%d ",midnumbers[i]);
            printf("\n");
        }
        else {
            printf("none\n");
        }
        return 1;
    }