蓝桥杯—排序

﹏ヽ暗。殇╰゛Y 2022-06-18 11:25 277阅读 0赞

2016年第七届第4题

快速排序

排序在各种场合经常被用到。  
快速排序是十分常用的高效率的算法。  
  
其思想是：先选一个“标尺”，  
用它把整个队列过一遍筛子，  
以保证：其左边的元素都不大于它，其右边的元素都不小于它。  
  
这样，排序问题就被分割为两个子区间。  
再分别对子区间排序就可以了。  
  
下面的代码是一种实现，请分析并填写划线部分缺少的代码。  
  
  
\#include <stdio.h>  
  
void swap(int a\[\], int i, int j)  
\{  
int t = a\[i\];  
a\[i\] = a\[j\];  
a\[j\] = t;  
\}  
  
int partition(int a\[\], int p, int r)  
\{  
int i = p;  
int j = r + 1;  
int x = a\[p\];  
while(1)\{  
while(i<r && a\[++i\]<x);  
while(a\[--j\]>x);  
if(i>=j) break;  
swap(a,i,j);  
\}  
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_;  
return j;  
\}  
  
void quicksort(int a\[\], int p, int r)  
\{  
if(p<r)\{  
int q = partition(a,p,r);  
quicksort(a,p,q-1);  
quicksort(a,q+1,r);  
\}  
\}  
  
int main()  
\{  
int i;  
int a\[\] = \{5,13,6,24,2,8,19,27,6,12,1,17\};  
int N = 12;  
  
quicksort(a, 0, N-1);  
  
for(i=0; i<N; i++) printf("%d ", a\[i\]);  
printf("\\n");  
  
return 0;  
\}  
  
  
注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

#include <stdio.h>
    
    void swap(int a[], int i, int j)
    {
    	int t = a[i];
    	a[i] = a[j];
    	a[j] = t;
    }
    
    int partition(int a[], int p, int r)
    {
        int i = p;
        int j = r + 1;
        int x = a[p];
        while(1){
            while(i<r && a[++i]<x);
            while(a[--j]>x);
            if(i>=j) break;
            swap(a,i,j);
        }
    	swap(a,p,j);   //快速排序，填空位置为经过比较之后，将最初选的“标尺”放在中间，即：标尺左边的数小于标尺，右边的数则大于它
        return j;
    }
    
    void quicksort(int a[], int p, int r)
    {
        if(p<r){
            int q = partition(a,p,r);
            quicksort(a,p,q-1);
            quicksort(a,q+1,r);
        }
    }
    
    int main()
    {
    	int i;
    	int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
    	int N = 12;
    
    	quicksort(a, 0, N-1);
    
    	for(i=0; i<N; i++) printf("%d ", a[i]);
    	printf("\n");
    
    	return 0;
    }

运行结果：

![Center][]

2013年第四届第六题

标题：三部排序  
  
一般的排序有许多经典算法，如快速排序、希尔排序等。  
  
但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。  
  
比如，对一个整型数组中的数字进行分类排序：  
  
使得负数都靠左端，正数都靠右端，0在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!!  
  
以下的程序实现了该目标。  
  
其中x指向待排序的整型数组，len是数组的长度。  
  
void sort3p(int\* x, int len)  
\{  
int p = 0;  
int left = 0;  
int right = len-1;  
  
while(p<=right)\{  
if(x\[p\]<0)\{  
int t = x\[left\];  
x\[left\] = x\[p\];  
x\[p\] = t;  
left++;  
p++;  
\}  
else if(x\[p\]>0)\{  
int t = x\[right\];  
x\[right\] = x\[p\];  
x\[p\] = t;  
right--;  
\}  
else\{  
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_; //填空位置 p++  
\}  
\}  
  
\}  
  
如果给定数组：  
25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0  
则排序后为：  
\-3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25

#include <iostream>
    using namespace std;
    
    void sort3p(int* x, int len)
    {
    	int p = 0;
    	int left = 0;
    	int right = len-1;
    
    	while(p<=right){
    		if(x[p]<0){
    			int t = x[left];
    			x[left] = x[p];
    			x[p] = t;
    			left++;
    			p++;
    		}
    		else if(x[p]>0){
    			int t = x[right];
    			x[right] = x[p];
    			x[p] = t;
    			right--;
    		}
    		else{
    			p++;  //该三部排序算法的直观意思就是，负数放左边，正数放右边，零放在中间。那样，每个数就要判断一下，放在哪里，该如何移动。
    		}
    	}
    
    }
    int main()
    {
        int x[] = {25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
        int len = 14;
        sort3p(x, len);
        for(int i = 0; i < len; i++) {
            cout<<x[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

运行结果：

![Center 1][]

## 桶排序 ##

/*
    桶排序
    思想：
    申请一个大小为 11 的数组 int a[11]。刚开始的时候，我们将 a[0]~a[10]都初始化为 0，表示这些分数还都没有人得过。
    例如 a[0]等于 0 就表示目前还没有人得过 0 分，同理 a[1]等于 0 就表示目前还没有人得过 1 分……a[10]等于 0 就表示目前还
    没有人得过 10 分。不同的分数所对应的单元格则存储着此分数的人数。
    */
    #include <stdio.h>
    int main()
    {
        int a[11],i,j,t;
        for(i=0; i<=10; i++)
            a[i]=0;         //初始化为0
        for(i=1; i<=5; i++) //循环读入5个数
        {
            scanf("%d",&t); //把每一个数读到变量t中
            a[t]++;         //进行计数
        }
        for(i=0; i<=10; i++) //依次判断a[0]~a[10]
            for(j=1; j<=a[i]; j++) //出现了几次就打印几次
                printf("%d ",i);
        getchar();
        getchar();
                    //这里的getchar();用来暂停程序，以便查看程序输出的内容
                    //也可以用system("pause");等来代替
        return 0;
    }

运行结果：

![Center 2][]

## 冒泡排序    ##

/*
    冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换
    过来。
    */
    #include <stdio.h>
    int main()
    {
        int a[100],i,j,t,n;
        scanf("%d",&n); //输入一个数n，表示接下来有n个数
        for(i=1; i<=n; i++) //循环读入n个数到数组a中
            scanf("%d",&a[i]);
    //冒泡排序的核心部分
        for(i=1; i<=n-1; i++) //n个数排序，只用进行n-1趟
        {
            for(j=1; j<=n-i; j++) //从第1位开始比较直到最后一个尚未归位的数
            {
                if(a[j]<a[j+1]) //比较大小并交换
                {
                    t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                }
            }
        }
        for(i=1; i<=n; i++) //输出结果
            printf("%d ",a[i]);
        getchar();
        getchar();
        return 0;
    }

运行结果：

![Center 3][]

## 快速排序 ##

/*
    思想：将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。
    “二分思想”
    */
    #include <stdio.h>
    int a[101],n;     //定义全局变量，这两个变量需要在子函数中使用
    void quicksort(int left,int right)
    {
        int i,j,t,temp;
        if(left>right)
            return;
        temp=a[left]; //temp中存的就是基准数
        i=left;
        j=right;
        while(i!=j)
        {
                     //顺序很重要，要先从右往左找
            while(a[j]>=temp && i<j)
                j--;
                     //再从左往右找
            while(a[i]<=temp && i<j)
                i++;
                     //交换两个数在数组中的位置
            if(i<j)  //当哨兵i和哨兵j没有相遇时
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
                     //最终将基准数归位
        a[left]=a[i];
        a[i]=temp;
        quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
        quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程
    }
    int main()
    {
        int i,j,t;
                     //读入数据
        scanf("%d",&n);
        for(i=1; i<=n; i++)
            scanf("%d",&a[i]);
        quicksort(1,n); //快速排序调用
                        //输出排序后的结果
        for(i=1; i<=n; i++)
            printf("%d ",a[i]);
        getchar();
        getchar();
        return 0;
    }

运行结果：  
![Center 4][]

[Center]: /images/20220618/0408475ca3254baeb297688b69925123.png
[Center 1]: /images/20220618/6b1dd53ad3cd4fd6ba8dd1f4aeafdfb9.png
[Center 2]: /images/20220618/21a95198830d48a1bdbb38f6ca235aec.png
[Center 3]: /images/20220618/ac971074f08c488db67932a7d438cc4e.png
[Center 4]: /images/20220618/817f6957e7994bdf8af14d48924f9196.png