精华内容
参与话题
问答
  • 快速排序---(面试碰到过好几次)

    万次阅读 多人点赞 2018-09-10 12:20:21
       快速排序,说白了就是给基准数据找其正确索引位置的过程.    如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示...

    原理:

       快速排序,说白了就是给基准数据找其正确索引位置的过程.
       如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示标志:low指向起始位置,high指向末尾.
    这里写图片描述
       首先从后半部分开始,如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小(如上图中18<=tmp),就将high位置的值赋值给low位置 ,结果如下:
    这里写图片描述
    然后开始从前往后扫描,如果扫描到的值小于基准数据就让low加1,如果发现有元素大于基准数据的值(如上图46=>tmp),就再将low位置的值赋值给high位置的值,指针移动并且数据交换后的结果如下:
    这里写图片描述
    然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将low位置的值赋值给high位置的值 ,结果如下:
    然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将high位置的值赋值给low位置的值,结果如下:
    这里写图片描述
    然后再开始从前往后遍历,直到low=high结束循环,此时low或high的下标就是基准数据23在该数组中的正确索引位置.如下图所示.
    这里写图片描述
      这样一遍走下来,可以很清楚的知道,其实快速排序的本质就是把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.
      以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。

    一些小结论

    从上面的过程中可以看到:

      ①先从队尾开始向前扫描且当low < high时,如果a[high] > tmp,则high–,但如果a[high] < tmp,则将high的值赋值给low,即arr[low] = a[high],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了
      ②同理,当从队首开始向队尾进行扫描时,如果a[low] < tmp,则low++,但如果a[low] > tmp了,则就需要将low位置的值赋值给high位置,即arr[low] = arr[high],同时将数组扫描方式换为由队尾向队首进行扫描.
      ③不断重复①和②,知道low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置.

    按照上诉理论我写的代码如下:

    package com.nrsc.sort;
    
    public class QuickSort {
    	public static void main(String[] args) {
    		int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
    		quickSort(arr, 0, arr.length - 1);
    		System.out.println("排序后:");
    		for (int i : arr) {
    			System.out.println(i);
    		}
    	}
    
    	private static void quickSort(int[] arr, int low, int high) {
    
    		if (low < high) {
    			// 找寻基准数据的正确索引
    			int index = getIndex(arr, low, high);
    
    			// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
    			//quickSort(arr, 0, index - 1); 之前的版本,这种姿势有很大的性能问题,谢谢大家的建议
    			quickSort(arr, low, index - 1);
    			quickSort(arr, index + 1, high);
    		}
    
    	}
    
    	private static int getIndex(int[] arr, int low, int high) {
    		// 基准数据
    		int tmp = arr[low];
    		while (low < high) {
    			// 当队尾的元素大于等于基准数据时,向前挪动high指针
    			while (low < high && arr[high] >= tmp) {
    				high--;
    			}
    			// 如果队尾元素小于tmp了,需要将其赋值给low
    			arr[low] = arr[high];
    			// 当队首元素小于等于tmp时,向前挪动low指针
    			while (low < high && arr[low] <= tmp) {
    				low++;
    			}
    			// 当队首元素大于tmp时,需要将其赋值给high
    			arr[high] = arr[low];
    
    		}
    		// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
    		// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
    		arr[low] = tmp;
    		return low; // 返回tmp的正确位置
    	}
    }
    
    
    展开全文
  • Z平台-开源免费的JAVA快速开发平台

    万次阅读 多人点赞 2019-08-24 19:26:39
    Z平台是开源免费的JAVA快速开发平台,通过Z平台集成开发环境,以零编码、动态配置的方式能够快速开发BS管理系统。同时该平台还可以做为APP、微信、各种小程序等项目的服务端来使用,为前端项目提供数据接口。并且Z...

    平台简述 

             Z平台是开源免费的JAVA快速开发平台,通过Z平台集成开发环境,以零编码、动态配置的方式能够快速开发BS管理系统。同时该平台还可以做为APP、微信、各种小程序等项目的服务端来使用,为前端项目提供数据接口。并且Z平台也内置了代码生成器组件,可以通过生成代码方式来完成项目的开发工作。

    源码仓库

    https://gitee.com/zj1983/zz

    使用教程

    基础教程:https://edu.csdn.net/course/detail/29220

    演示系统

    https://www.zframeworks.com/

    开发技巧

    https://blog.csdn.net/qq_38056435/article/details/103386195

    平台价值

    • 提升软件开发速度,缩短软件开发周期。

    • 降低软件开发BUG率,缩短软件测试周期。

    • 降低项目所需高级开发人员比例,减少项目用工成本支出。

    平台特点

    永久开源免费

    Z平台为开源免费项目,可以应用在所有商业或非商业项目中进行使用。

    学习成本低

    Z平台所使用的框架都是热门的开源技术框架。学习资料丰富。核心框架为Spring + SpringMVC + Mybatis组成。

    技术成熟稳定

    Z平台所应用的基础框架都是经过长时间沉淀成熟稳定的开源框架。在稳定性方面值得信赖。

    适用用户

    Z平台功能

    非专业人士

    企业信息管理人员

    计算机专业学生

    程序员

    安装部署

    YES

    YES

    YES

    YES

    平台功能

    YES

    YES

    YES

    YES

    表单开发

    YES

    YES

    YES

    YES

    报表开发

    NO

    YES

    YES

    YES

    工作流程配置

    NO

    YES

    YES

    YES

    自动任务配置

    NO

    NO

    YES

    YES

    接口开发

    NO

    NO

    YES

    YES

    框架修改

    NO

    NO

    NO

    YES

    展开全文
  • 白话经典算法系列之六 快速排序 快速搞定

    万次阅读 多人点赞 2011-08-13 17:19:58
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的...
     快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。

    总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定

     

    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    该方法的基本思想是:

    1.先从数列中取出一个数作为基准数。

    2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

    3.再对左右区间重复第二步,直到各区间只有一个数。

     

    虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明:挖坑填数+分治法

    先来看实例吧,定义下面再给出(最好能用自己的话来总结定义,这样对实现代码会有帮助)。

     

    以一个数组作为示例,取区间第一个数为基准数。

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    72

    6

    57

    88

    60

    42

    83

    73

    48

    85

    初始时,i = 0;  j = 9;   X = a[i] = 72

    由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。

    从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

     

    数组变为:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    48

    6

    57

    88

    60

    42

    83

    73

    88

    85

     i = 3;   j = 7;   X=72

    再重复上面的步骤,先从后向前找,再从前向后找

    从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

    从i开始向后找,当i=5时,由于i==j退出。

    此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

     

    数组变为:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    48

    6

    57

    42

    60

    72

    83

    73

    88

    85

    可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

     

     

    对挖坑填数进行总结

    1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

    2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

    照着这个总结很容易实现挖坑填数的代码:

    int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
    {
    	int i = l, j = r;
    	int x = s[l]; //s[l]即s[i]就是第一个坑
    	while (i < j)
    	{
    		// 从右向左找小于x的数来填s[i]
    		while(i < j && s[j] >= x) 
    			j--;  
    		if(i < j) 
    		{
    			s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑
    			i++;
    		}
    
    		// 从左向右找大于或等于x的数来填s[j]
    		while(i < j && s[i] < x)
    			i++;  
    		if(i < j) 
    		{
    			s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑
    			j--;
    		}
    	}
    	//退出时,i等于j。将x填到这个坑中。
    	s[i] = x;
    
    	return i;
    }
    

    再写分治法的代码:

    void quick_sort1(int s[], int l, int r)
    {
    	if (l < r)
        {
    		int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
    		quick_sort1(s, l, i - 1); // 递归调用 
    		quick_sort1(s, i + 1, r);
    	}
    }

    这样的代码显然不够简洁,对其组合整理下:

    //快速排序
    void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
    		//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
    				j--;  
                if(i < j) 
    				s[i++] = s[j];
    			
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
    				i++;  
                if(i < j) 
    				s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用 
            quick_sort(s, i + 1, r);
        }
    }

    快速排序还有很多改进版本,如随机选择基准数,区间内数据较少时直接用另的方法排序以减小递归深度。有兴趣的筒子可以再深入的研究下。

     

    注1,有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。

     

     转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/6684558

    展开全文
  • 快速排序基本思路(通俗易懂+例子)

    万次阅读 多人点赞 2017-07-02 22:06:32
    快速排序今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单 下面进行简单的试试快速排序的基本思想是 1、先从数列中取出一个数作为基准数 2、分区过程,将比这个数大的数全放到它的...

    快速排序

    今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单
    下面进行简单的试试

    快速排序的基本思想是

    1、先从数列中取出一个数作为基准数

    2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边

    3、再对左右区间重复第二步,直到各区间只有一个数

    概括来说为 挖坑填数+分治法

    下面举例来进行说明,主要有三个参数,i为区间的开始地址,j为区间的结束地址,X为当前的开始的值

    第一步,i=0,j=9,X=21

    0 1 2 3 4 5 6 7 8 9
    21 32 43 98 54 45 23 4 66 86

    第二步,从j开始由,后向前找,找到比X小的第一个数a[7]=4,此时i=0,j=6,X=21
    进行替换

    0 1 2 3 4 5 6 7 8 9
    4 32 43 98 54 45 23 21 66 86

    第三步,由前往后找,找到比X大的第一个数a[1]=32,此时i=2,j=6,X=21

    0 1 2 3 4 5 6 7 8 9
    4 21 43 98 54 45 23 32 66 86

    第四步,从j=6开始由,由后向前找,找到比X小的第一个数a[0]=4,此时i=2,j=0,X=21,发现j<=i,所以第一回结束

    可以发现21前面的数字都比21小,后面的数字都比21大
    接下来对两个子区间[0,0]和[2,9]重复上面的操作即可

    下面直接给出过程,就步详细解说了

    i=2,j=6,X=43

    0 1 2 3 4 5 6 7 8 9
    4 21 43 98 54 45 23 32 66 86

    i=4,j=6,X=43

    0 1 2 3 4 5 6 7 8 9
    4 21 32 98 54 45 23 43 66 86

    i=4,j=5,x=43

    0 1 2 3 4 5 6 7 8 9
    4 21 32 43 54 45 23 98 66 86

    i=5,j=5,x=43

    0 1 2 3 4 5 6 7 8 9
    4 21 32 23 43 45 54 98 66 86

    然后被分为了两个子区间[2,3]和[5,9]

    …最后排序下去就是最终的答案

    0 1 2 3 4 5 6 7 8 9
    4 21 23 32 43 45 54 66 86 98

    总结:

    1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

    2.j–由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。


    代码

    class Solution {
    	public void sort(int left,int right,int[] array) {
    		if (left>=right) return ;
    		int start=left;
    		int end=right;
    		int flag=left;
    		while(left<right) {
    			while ((left<right)&&(array[right]>=array[flag])) {
    				right--;
    			}
    			if (array[right]<array[flag]) {
    				int tmp=array[right];
    				array[right]=array[flag];
    				array[flag]=tmp;
    				flag=right;
    			}
    			while ((left<right)&&(array[left]<=array[flag])) {
    				left++;
    				}
    			if (array[left]>array[flag]) {
    				int tmp=array[left];
    				array[left]=array[flag];
    				array[flag]=tmp;
    				flag=left;
    			}
    		}
    		sort(start, left-1, array);
    		sort(left+1, end, array);
    	}
    }
    

    分享一个比较牛逼的学习java的网站,基础知识和架构等都有,连接如下:
    http://how2j.cn?p=54321
    在这里插入图片描述

    展开全文
  • 快速排序(过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧...
  • 快速排序算法——C/C++

    万次阅读 多人点赞 2019-06-12 22:55:14
    快速排序 1、算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 2、实现原理 ...
  • 上个厕所的功夫,就学会了“快速排序”算法

    万次阅读 多人点赞 2020-05-17 20:25:09
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像BAT、TMD等知名IT公司都喜欢考查快速排序原理和手写...
  • 算法 - 快速排序(C#)

    万次阅读 多人点赞 2019-01-29 20:29:11
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 快速排序(QuickSort)是对冒泡排序的一种... * 然后再按此方法对这两部分数据分别进行快速排序,整个排序...
  • 快速幂算法——带你从零开始一步一步优化 目录 快速幂算法——带你从零开始一步一步优化 什么是快速幂算法 再次思考 快速幂算法初步入门 压榨性能再优化 终极优化 参考资料 博客文章版权声明 什么是...
  • 快速排序(三种算法实现和非递归实现)

    万次阅读 多人点赞 2017-11-29 18:41:44
    快速排序(Quick Sort)是对冒泡排序的一种改进,基本思想是选取一个记录作为枢轴,经过一趟排序,将整段序列分为两个部分,其中一部分的值都小于枢轴,另一部分都大于枢轴。然后继续对这两部分继续进行排序,从而使...
  • 算法 - 快速求一个整数的7倍

    万次阅读 多人点赞 2019-02-26 10:29:23
    分享一个大牛的人工智能教程。零基础!...乘法运算相对比较慢,所以快速的方法就是将这个乘法转换成加减法和移位操作。 可以将此整数先左移三位(*8)然后再减去原值:X &lt;&lt; 3 – X。 ...
  • vim之快速查找功能

    万次阅读 多人点赞 2016-11-16 16:15:38
    vim有强大的字符串查找功能。 我们通常在vim下要查找字符串的时候, 都是输入 / 或者 ? 加 需要查找的字符串来进行搜索,比如想搜索 super 这个单词, 可以输入 /super 或者 ?super, 两者的区别是前者是从上往...
  • 快速排序算法

    万次阅读 多人点赞 2019-01-11 21:09:08
    但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到...
  • 用C语言实现快速排序算法

    万次阅读 多人点赞 2016-11-04 22:33:13
    一、快速排序算法(Quicksort) 1. 定义 快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进,采用了一种分治的策略。 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中...
  • 快速排序法(详解)

    万次阅读 多人点赞 2019-07-01 17:27:49
    假设对以下10个数进行快速排序: 6 1 2 7 9 3 4 5 10 8 我们先模拟快速排序的过程:首先,在这个序列中随便找一个数作为基准数,通常为了方便,以第一个数作为基准数。 6 1 2 ...
  • 快速排序

    万次阅读 2020-04-24 01:10:08
    文章目录快速排序算法排序流程动图算法分析java代码 快速排序算法 快速排序是一种分治的排序算法,和冒泡排序同属于交换排序。 快速排序在每一轮都挑选一个基准元素,并让比它小的元素移到数列的一边,比它大的元素...
  • 快速排序(java实现)

    万次阅读 多人点赞 2018-09-05 14:53:42
    那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,...
  • 十分钟快速Maven下载和安装说明

    万次阅读 多人点赞 2018-01-25 10:58:23
    注意:安装Maven3之前需要安装jdk1.7以上版本,下面介绍的是最新版Maven官网下载并安装, 每个人使用的编辑器不同,在这里我就不介绍了,可以去网上查对应编辑器Maven配置方法。 ... ...第二步,解压文件包 ...
  • 图解快速排序(C++实现)

    万次阅读 多人点赞 2019-03-05 10:25:18
    参考大话数据结构这本书对快速排序的讲解,本文作一个梳理,并在最后给出快排的C++实现代码。 假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到...
  • 快速

    万次阅读 多人点赞 2019-02-18 11:24:54
    以前我看快速幂真的看不懂,但是当我慢慢对递归(递归大法好)有一些理解后,对二分又理解一些后,就能够自己写出快速幂的递归写法了。 求 a^b % m的值,这个用普通算法我就不说了,时间复杂度O(b) 当我知道快速...
  • idea快速编码之常用快捷键使用操作方法

    万次阅读 多人点赞 2020-05-04 20:29:24
    IDEA快捷键使用教程目录一、 日常开发常用快捷键二、 快速查找及替换三、 快速重构四、 基础编码相关快捷键五、 修改快捷键5.1 查找快捷键5.2 自定义快捷键 一、 日常开发常用快捷键 简介:介绍日常开发中高频使用到...
  • IDEA快速显示Run DashBoard

    万次阅读 2020-09-21 04:50:45
    双击Shift进行搜索 输入 DashBoard 如果没有服务则进行添加 选择Springboot即可 如下就算完成了,新版本的IDEA Run Dashboard改名成Service了其它和以前一样 ...最后只需要启动springboot项目即可 ...
  • 快速幂算法可以说是ACM一类竞赛中必不可少,并且也是非常基础的一类算法,鉴于我一直学的比较零散,所以今天用这个帖子总结一下 快速乘法通常有两类应用:一、整数的运算,计算(a*b) mod c 二、矩阵快速乘法 一、...

空空如也

1 2 3 4 5 ... 20
收藏数 849,516
精华内容 339,806
关键字:

快速