PTA(Basic Level) 1045：快速排序（C语言实现）

左手的ㄟ右手 2023-07-19 10:38 25阅读 0赞

## PTA(Basic Level) 1045：快速排序 （C语言实现） ##

分析：分析题目，怎样才能成为主元呢？  
①**主元的位置和排序后的位置相同，只有这样，才有可能让主元的前面元素小于主元，主元后面的元素大于主元**（这里和快速排序的联系：一趟快排的结果 \[ <v \] \[ v \] \[ >v\]，有一个元素在其最终位置上，且它前面的元素小于它，它后面的元素大于它，在递归对前后两个部分快排）  
②在满足上述条件的情况下，还应满足**主元是前面最大的元素**。  
举例：1 5 3 4 2 6 排序后：1 2 3 4 5  
对于1，满足①②  
对于5 ，不满足①  
对于 3 ，满足①不满足②，5>3  
对于4 ，满足①不满足②，5>4  
对于2，不满足①  
对于6，满足①②  
因此主元为 1 6  
**注意，即使所有元素都不是主元时，最后一行也要输出，输出空格，不然有一个测试点格式错误。**

#include <stdio.h>
    #include <stdlib.h>
    
    long cmp(const void *a, const void *b)
    { 
    	return *(long*)a-*(long*)b;
    }
    int main()
    { 
    	int n,i,j;
    	long a[100000]={ 0},b[100000]={ 0},max=0;
    	scanf("%d",&n);
    	for(i=0; i<n; i++)
    	{ 
    		scanf("%ld",&a[i]);
    		b[i]=a[i];
    	}
    	qsort(a,n,sizeof(a[0]),cmp);
    	for(i=0,j=0; i<n; i++)
    	{ 
    		if(b[i] > max)
    			max=b[i];
    		if(a[i] == b[i] && a[i]>=max)
    			b[j++]=a[i];
    	}
    	printf("%d\n",j);
    	for(i=0; i<j; i++)
    		i==0?printf("%ld",b[i]):printf(" %ld",b[i]);
      printf("\n");//没有主元时也要输出空格
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关 c语言实现快速排序

快速排序是一种快速的排序算法。它的基本思想是，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别

矫情吗；*/ 2024年03月26日 09:38/ 0 赞/ 723 阅读

相关 1045 快速排序（JAVA）

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的 N 个互不

蔚落/ 2023年09月28日 18:34/ 0 赞/ 13 阅读

相关 PTA(Basic Level) 1045：快速排序（C语言实现）

PTA(Basic Level) 1045：快速排序（C语言实现）分析：分析题目，怎样才能成为主元呢？ ①主元的位置和排序后的位置相同，只有这样，才有可能让主元的

左手的ㄟ右手/ 2023年07月19日 10:38/ 0 赞/ 26 阅读

相关快速排序 C语言实现

快速排序快速排序(Quick Sort )是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过

﹏ヽ暗。殇╰゛Y/ 2022年12月22日 11:12/ 0 赞/ 205 阅读

相关快速排序（C语言实现）

\include <stdio.h> int partition(int \A, int p, int r); void quick\_sort(int \

我不是女神ヾ/ 2022年07月21日 02:51/ 0 赞/ 181 阅读

相关 1045. 快速排序(25)

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的N个互不相同的

蔚落/ 2022年05月26日 07:18/ 0 赞/ 158 阅读

相关快速排序：C语言实现

一、快排概述快速排序是一个非常优秀且常用的排序算法，尤其是在大数据的排序应用中，最为常见。虽然“快速”，但逻辑也是最复杂，最难理解。本

逃离我推掉我的手/ 2022年04月05日 06:51/ 0 赞/ 345 阅读

相关快速排序-C语言实现

include<stdio.h> //快速排序完成 void QuickSort(int [],int,int); int FindPos(int a,

ゞ浴缸里的玫瑰/ 2022年04月02日 06:24/ 0 赞/ 249 阅读

相关快速排序 C语言实现

Program 1 \include "stdio.h" \include "conio.h" void quick\_sort(int \a,int left,int

叁歲伎倆/ 2022年03月29日 15:28/ 0 赞/ 238 阅读

相关 PAT~乙级~1045 快速排序 ~C++

题目描述：著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后

淩亂°似流年/ 2021年11月29日 15:56/ 0 赞/ 231 阅读