精华内容
下载资源
问答
  • 蓝桥杯快速排序问题

    2021-03-12 16:12:19
    蓝桥杯快速排序问题 看之前一定要把心沉下来,我觉得如果不明白快速排序算法的话一定要先看链接内容,很难有哪篇博客让你1分钟解决这个问题,重要的是心静并且肯花时间 先来看下题目要求: 快速排序 排序在各种...

    蓝桥杯快速排序问题

    看之前一定要把心沉下来,我觉得如果不明白快速排序算法的话一定要先看链接内容,很难有哪篇博客让你1分钟解决这个问题,重要的是心静并且肯花时间
    先来看下题目要求:

    
    快速排序
    
    排序在各种场合经常被用到。
    快速排序是十分常用的高效率的算法。
    
    其思想是:先选一个“标尺”,
    用它把整个队列过一遍筛子,
    以保证:其左边的元素都不大于它,其右边的元素都不小于它。
    
    这样,排序问题就被分割为两个子区间。
    再分别对子区间排序就可以了。
    
    下面的代码是一种实现,请分析并填写划线部分缺少的代码。
    
    
    #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;
    }
    
    
    注意:只填写缺少的内容,不要书写任何题面已有代码或说明性文字。
    
    
    

    不明白的同学可以看下快速排序到底是什么意思,其实题中的文字部分也已经说明,不过为了防止大家不懂,我把快速排序动态过程链接放在这里
    快速排序
    其实就是左指针一直往左,直到找到一个比标准大的数,右指针一直向右找到一个比标准小的数, 以视频中的序列为例
    3 5 8 1 2 9 4 7 6
    在进入while循环后执行第一条语句发现a[++i]=5>3,左指针不动,有指针在执行完while语句后,指向2,然后就把2和5换位置,再次进入while(1)循环,执行完循环体内的两个小循环后,左指针指向8,右指针指向1,最后序列变成:
    3 2 1 8 5 9 4 7 6
    注意此仍然无法跳出while(1)循环,直到第三次进入此循环后,左右指针执行完两条循环语句后会恰好交换位置,那么我们下一步要做的即是填空内容,显然,我们需要把a[j]=1(右指针指向的元素)和a[p](基本元素)交换位置即可,那么答案就显而易见了。

    展开全文
  • 首先分享一篇讲快速排序的,讲的可好了!浅显易懂,值得一看~ 快速排序 一份有注释的代码: public class Demo5 { // 以下代码可以从数组a[]中找出第k小的元素。 public static int quickSelect(int a[], int l, ...

    前言:
    答案:a, i + 1, r, k - (i - l + 1)
    首先分享一篇讲快速排序的,讲的可好了!浅显易懂,值得一看~
    快速排序
    一份有注释的代码:

    public class Demo5 {
    	// 以下代码可以从数组a[]中找出第k小的元素。
    	public static int quickSelect(int a[], int l, int r, int k) {
    		// 1、随机选择一个元素作为基准元素(此时选择的基准元素为x)
    		Random rand = new Random();
    		int p = rand.nextInt(r - l + 1) + l;
    		int x = a[p];
    		
    		// 这里令我们随机选择的元素a[p]与数组最右端的元素a[r]互换
    		int tmp = a[p];
    		a[p] = a[r];
    		a[r] = tmp;
    		
    		// 2、相当于设置两个指针i和j,i为左指针,j为右指针,它们分别指向数组最左和最右的元素
    		int i = l, j = r;
    		while (i < j) {
    			//3、将左指针指向的元素与基准元素相比较,如果左指针指向的元素小于基准元素,则左指针向右移动一位
    			while (i < j && a[i] < x)
    				i++;
    			//4、通过上一步的移动,左指针左边的元素全部比基准元素小,令数组最右的元素(此时的数组最右的元素等于基准元素x)等于此时左指针指向的元素,右指针向左移动一位,此时的a[j]大于等于x
    			if (i < j) {
    				a[j] = a[i];
    				j--;
    			} 
    			
    			//5、将右指针指向的元素与基准元素相比较,如果右指针指向的元素大于基准元素,则右指针向左移动一位
    			while (i < j && a[j] > x)
    				j--;
    			//6、通过上一步的移动,右指针右边的元素全部比基准元素大,令左指针指向的元素等于此时右指针指向的元素,左指针向右移动一位,此时的a[i]小于等于x
    			if (i < j) {
    				a[i] = a[j];
    				i++;
    			} 
    		}
    		//7、通过步骤3、4、5、6后,可以确定a[i]的位置就是我们选择的基准元素排序后应该所在的位置
    		a[i] = x;
    		//8、令基准元素位置的索引i等于p
    		p = i;
    		//9、通过算式i - l + 1得到的是在数组中第几小的元素,若它等于k,则得到题目要求的数组a[]中第k小的元素
    		if (i - l + 1 == k)
    			return a[i];
    		//若小于k,即我们所求的元素在i的右边,此时左指针指向的元素为a[p+1],右指针指向的元素依旧是a[r],所求第k小的元素变为第k - (i - l + 1)小
    		if (i - l + 1 < k)
    			return quickSelect(a, i + 1, r, k - (i - l + 1)); // 填空
    		else
    			//若大于k,即我们所求的元素在i的左边,此时左指针指向的元素为认为a[l],右指针指向的元素为a[i-1],仍旧是求第k小的元素
    			return quickSelect(a, l, i - 1, k);
    	}
    
    	public static void main(String args[]) {
    		int[] a = { 1, 4, 2, 8, 5, 7 };
    		System.out.println(quickSelect(a, 0, 5, 4));
    	}
    
    }
    
    
    展开全文
  • 蓝桥杯 快速排序

    2019-03-20 18:17:28
    快速排序 以下代码可以从数组a[]中找出第k小的元素。 它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。 请仔细阅读分析源码,填写划线部分缺失的内容。 #include <stdio.h> int quick_select...

    快速排序 

    以下代码可以从数组a[]中找出第k小的元素。

    它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。

    请仔细阅读分析源码,填写划线部分缺失的内容。
    #include <stdio.h>
    int quick_select(int a[], int l, int r, int k) {
        int p = rand() % (r - l + 1) + l;
        int x = a[p];
        {int t = a[p]; a[p] = a[r]; a[r] = t;}
        int i = l, j = r;
        while(i < j) {
            while(i < j && a[i] < x) i++;
            if(i < j) {
                a[j] = a[i];
                j--;
            }
            while(i < j && a[j] > x) j--;
            if(i < j) {
                a[i] = a[j];
                i++;
            }
        }
        a[i] = x;
        p = i;
        if(i - l + 1 == k) return a[i];
        if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
        else return quick_select(a, l, i - 1, k);
    }
        
    int main()
    {
        int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
        printf("%d\n", quick_select(a, 0, 14, 5));
        return 0;
    }

    注意:只填写划线部分缺少的代码,不要抄写已经存在的代码或符号。

     

    答案:a, i+1, r, r-(i-l+1)

    展开全文
  • 第九届蓝桥杯快速排序

    千次阅读 2018-04-01 20:41:43
    标题:快速排序。 以下代码可以从数组a[]中找出第k小的元素。它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。请仔细阅读分析源码,填写划线部分缺失的内容。#include &lt;stdio.h&gt; int ...

    标题:快速排序。

    以下代码可以从数组a[]中找出第k小的元素。


    它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。


    请仔细阅读分析源码,填写划线部分缺失的内容。
    #include <stdio.h>
    
    int quick_select(int a[], int l, int r, int k) {
        int p = rand() % (r - l + 1) + l;
        int x = a[p];
        {int t = a[p]; a[p] = a[r]; a[r] = t;}
        int i = l, j = r;
        while(i < j) {
            while(i < j && a[i] < x) i++;
            if(i < j) {
                a[j] = a[i];
                j--;
            }
            while(i < j && a[j] > x) j--;
            if(i < j) {
                a[i] = a[j];
                i++;
            }
        }
        a[i] = x;
        p = i;
        if(i - l + 1 == k) return a[i];
        if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
        else return quick_select(a, l, i - 1, k);
    }
        
    int main()
    {
        int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
        printf("%d\n", quick_select(a, 0, 14, 5));
        return 0;
    
    }

    通过做这道题,我认识到认真审题的重要性,我从头开始理解他的代码,前三个参数好理解就是快速排序的知识,但是第四个是第K小的数,所以我们在下手之前一定要读懂题意。

    我的答案:a,i+1,r,r-k+1    最后一个参数猜的成分比较大。



    展开全文
  • Java实现第九届蓝桥杯快速排序

    万次阅读 多人点赞 2019-07-28 12:30:21
    快速排序 以下代码可以从数组a[]中找出第k小的元素。 它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。 请仔细阅读分析源码,填写划线部分缺失的内容。 package bb; import java.util.Random; public ...
  • 快速排序 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序...
  • java实现第四届蓝桥杯快速排序

    千次阅读 2019-07-29 18:25:00
    快速排序 题目描述 快速排序算法是典型的分治思想的运用。它使用某个key把全部元素分成两组,其中一组的元素不大于另一...
  • Java实现 蓝桥杯VIP 算法训练 快速排序

    万次阅读 多人点赞 2019-06-18 22:34:44
    public class 快速排序 { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int a=sc.nextInt(); int[] ar=new int[a]; for(int i=0;i<a;i++){ ...
  • 蓝桥杯java排序之快速排序

    千次阅读 2017-02-24 16:46:41
    一、快速排序算法的基本特性 时间复杂度:O(n*lgn) 最坏:O(n^2) 空间复杂度:O(n*lgn) 不稳定。 快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)。 通常是...
  • 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序问题就被分割为两个子区间。 再分别对子区间...
  • 蓝桥杯快速排序详解

    千次阅读 2018-03-22 22:50:59
    快速排序排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。其思想是:先选一个“标尺”,用它把整个队列过一遍筛子,以保证:其左边的元素都不大于它,其右边的元素都不小于它。这样,排序问题就被分割...
  • 快速排序 #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]; ...
  •  用递归来实现快速排序(quick sort)算法。快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x。首先对数组中的元素进行调整,使x放在正确的位置上。同时,所有比x小的数都位于它的左边,所有比x大...
  • 快速排序排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。其思想是:先选一个“标尺”,用它把整个队列过一遍筛子,以保证:其左边的元素都不大于它,其右边的元素都不小于它。这样,排序问题就被分割...
  • 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序问题就被分割为两个子区间。 再分别对子...
  • 算发标签:快速排序 题目描述: 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于...
  • 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序问题就被分割为两个子区间。 再分别对子...
  • 试题 算法提高 快速排序...
  • 它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。 请仔细阅读分析源码,填写划线部分缺失的内容。 #include <stdio.h> int quick_select(int a[], int l, int r, int k) { int p = rand() % ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,627
精华内容 650
关键字:

蓝桥杯快速排序