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

    2019-09-26 17:11:33
    蓝桥杯 快速排序 【题目描述 - Problem Description】 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于...

    蓝桥杯 快速排序

    【题目描述 - Problem Description】

    排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。

    其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。

    这样,排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。

    下面的代码是一种实现,请分析并填写划线部分缺少的代码。

     1 #include <stdio.h>
     2 
     3 void swap(int a[], int i, int j)
     4 {
     5     int t = a[i];
     6     a[i] = a[j];
     7     a[j] = t;
     8 }
     9 
    10 int partition(int a[], int p, int r)
    11 {
    12     int i = p;
    13     int j = r + 1;
    14     int x = a[p];
    15     while(1){
    16         while(i<r && a[++i]<x);
    17         while(a[--j]>x);
    18         if(i>=j) break;
    19         swap(a,i,j);
    20     }
    21     _______________;//填空位置
    22     return j;
    23 }
    24 
    25 void quicksort(int a[], int p, int r)
    26 {
    27     if(p<r){
    28         int q = partition(a,p,r);
    29         quicksort(a,p,q-1);
    30         quicksort(a,q+1,r);
    31     }
    32 }
    33     
    34 int main()
    35 {
    36     int i;
    37     int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
    38     int N = 12;
    39     
    40     quicksort(a, 0, N-1);
    41     
    42     for(i=0; i<N; i++) printf("%d ", a[i]);
    43     printf("\n");
    44     
    45     return 0;
    46 }

     

    【题解】

    快排的思想就是区间整理,实现策略大同小异……

    在partition没有使用赋值实现交换,那么填空部分则不会是直接赋值。

    在看循环中的下标,跳过首发元素,那么需要补充的代码就是将x归位。(可以通过只是递归从输出看出)

    观察循环结束后的区间状态:x[<=x,j下标落脚][i下标落脚,>=x]

    所以直接交换初始x的位置p,和符合条件的下标j

     

    【最终结果】

    swap(a, p, j)

    转载于:https://www.cnblogs.com/Simon-X/p/6528733.html

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

    万次阅读 多人点赞 2019-07-29 18:24:42
    快速排序 题目描述 快速排序算法是典型的分治思想的运用。它使用某个key把全部元素分成两组,其中一组的元素不大于另一组。然后对这两组再次进行递归排序。 以下代码实现了快速排序。请仔细阅读代码,填写缺少...
    
     快速排序
    
    
    题目描述
    
    快速排序算法是典型的分治思想的运用。它使用某个key把全部元素分成两组,其中一组的元素不大于另一组。然后对这两组再次进行递归排序。
    
        以下代码实现了快速排序。请仔细阅读代码,填写缺少代码的部分。
    
    static void f(int[] x, int left, int right)
    {
        if(left >= right) return;
        
        int key = x[(left+right)/2];
        
        int li = left;
        int ri = right;
        while(li<=ri){
            while(x[ri]>key) ri--;
            while(x[li]<key) li++;
            
            if(________________){    //填空位置
                int t = x[li];
                x[li] = x[ri];
                x[ri] = t;
                li++;
                ri--;
            }    
        }
        
        if(li < right) f(x, li, right);
        if(ri > left) f(x, left, ri);
    }
    
    请分析代码逻辑,并推测划线处的代码,通过网页提交。
    注意:仅把缺少的代码作为答案,千万不要填写多余的代码、符号或说明文字!!
    
    li <= ri
    
    
    展开全文
  • Java实现第九届蓝桥杯快速排序

    万次阅读 多人点赞 2019-07-28 12:30:21
    快速排序 以下代码可以从数组a[]中找出第k小的元素。 它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。 请仔细阅读分析源码,填写划线部分缺失的内容。 package bb; import java.util.Random; public ...
    
     快速排序
    
    

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

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

    请仔细阅读分析源码,填写划线部分缺失的内容。

    package bb;
    import java.util.Random;
    public class JB18_5快速排序 {
        public static int quickSelect(int a[], int l, int r, int k) {
            Random rand = new Random();
            int p = rand.nextInt(r - l + 1) + l;
            int x = a[p];
            int tmp = a[p];
            a[p] = a[r];
            a[r] = tmp;
            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)// (1)说明到底了
                return a[i];
            if (i - l + 1 < k)
                return quickSelect(a, i + 1, r, k - i + l - 1); // 填空
            // qsort(a, i + 1, right);
            // (3)先试试k,
            // (4)再考虑:k要移动到等于(i - l + 1),试试k-(i - l + 1)
            else
                // i - l + 1 > k
                return quickSelect(a, l, i - 1, k);// (2)qsort(a, left, 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));
            // int [] a = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12, 2};
            // System.out.println(quickSelect(a, 0, a.length-1, 6));
        }
    }
    
    展开全文
  •  用递归来实现快速排序(quick sort)算法。快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x。首先对数组中的元素进行调整,使x放在正确的位置上。同时,所有比x小的数都位于它的左边,所有比x大...

    资源限制
    时间限制:1.0s 内存限制:256.0MB
    问题描述
      用递归来实现快速排序(quick sort)算法。快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x。首先对数组中的元素进行调整,使x放在正确的位置上。同时,所有比x小的数都位于它的左边,所有比x大的数都位于它的右边。然后对于左、右两段区域,递归地调用快速排序算法来进行排序。
      输入格式:输入只有一行,包括若干个整数(不超过10个),以0结尾。
      输出格式:输出只有一行,即排序以后的结果(不包括末尾的0)。
    输入输出样例
    样例输入
    5 2 6 1 7 3 4 0
    样例输出
    1 2 3 4 5 6 7

    解题思路:
    解决这道题最重要的是理解快速排序的过程,菜鸟教程上有该算法的详细的步骤https://www.runoob.com/w3cnote/quick-sort.html,本质就是不断填坑,首先将最左边的数挖出,然后从最右边开始向左找比挖出来的数小的填上去,然后再从左边向右找到比初始坑大的数填到刚才挖的坑,反复直到相遇,然后在各自的区间再重复做这样的事情,代码如下:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int a[10];
    
    void quick_sort(int s[], int l, int r){
    	if(l < r){
    		int i = l;
    		int j = r;
    		int x = s[l];
    		while(i < j){
    			while(i < j && a[j] >= x){
    				j --;
    			}
    			if(i < j){
    				s[i ++] = s[j];
    			}
    			while(i < j && a[i] < x){
    				i ++;
    			}
    			if(i < j){
    				s[j --] = s[i];
    			}
    		}	
    		s[i] = x;
    		quick_sort(s, l, i - 1);
    		quick_sort(s, i + 1, r);
    	}
    } 
    
    int main(){
    	int index = 0;
    	int num;
    	while(1){
    		cin >> num;
    		if(num == 0){
    			break;
    		}
    		a[index ++] = num;
    	}
    	quick_sort(a, 0, index - 1);
    	for(int i = 0; i < index; i ++){
    		cout << a[i] << " ";
    	}	
    	return 0;
    }
    
    展开全文
  • 首先分享一篇讲快速排序的,讲的可好了!浅显易懂,值得一看~ 快速排序 一份有注释的代码: public class Demo5 { // 以下代码可以从数组a[]中找出第k小的元素。 public static int quickSelect(int a[], int l, ...
  • 快速排序排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。其思想是:先选一个“标尺”,用它把整个队列过一遍筛子,以保证:其左边的元素都不大于它,其右边的元素都不小于它。这样,排序问题就被分割...
  • 第九届蓝桥杯快速排序

    千次阅读 2018-04-01 20:41:43
    标题:快速排序。 以下代码可以从数组a[]中找出第k小的元素。它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。请仔细阅读分析源码,填写划线部分缺失的内容。#include &lt;stdio.h&gt; int ...
  • 快速排序 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序...
  • 利用快速排序思想,每次把一个数找到他应该在的位置,然后如果当前位置满足条件,直接返回,如果这个数(包括这个数) 前面的数的个数小于k,那么第k大在后面的区间,否则在前面的区间,同时还要修改参数。 复杂度...
  • 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序问题就被分割为两个子区间。 再分别对子...
  • 蓝桥杯java排序之快速排序

    千次阅读 2017-02-24 16:46:41
    一、快速排序算法的基本特性 时间复杂度:O(n*lgn) 最坏:O(n^2) 空间复杂度:O(n*lgn) 不稳定。 快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)。 通常是...
  • java蓝桥杯练习 快速排序 资源限制 时间限制:1.0s 内存限制:512.0MB 问题描述  快速排序是最经常使用的一种排序方式,对于给定的n个数组成的一个数组,请使用快速排序对其进行排序。  现给定一序列,请用快速...
  • 蓝桥杯——快速排序

    2020-02-17 12:53:33
    快速排序 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。 这样,排序问题就...
  • 蓝桥杯试题 ------快速排序 问题描述   用递归来实现快速排序(quick sort)算法。快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x。首先对数组中的元素进行调整,使x放在正确的位置上。同时,...
  • 标题:快速排序。 以下代码可以从数组a[]中找出第k小的元素。 它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。 请仔细阅读分析源码,填写划线部分缺失的内容。 #include <stdio.h> int quick_...
  • 文章目录蓝桥杯 快速排序????题目描述分析 蓝桥杯 快速排序???? 题目描述 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 426
精华内容 170
关键字:

蓝桥杯快速排序