精华内容
下载资源
问答
  • 快速排序java代码实现

    千次阅读 2018-03-01 14:57:22
    说明: 快速排序是一个速度非常快的交换排序算法,它的基本思路很简单,从待排的数据序列中任取一个数据(如第一个数据)作为基准值,所有比它小的元素放到左边,所有比它大的元素放到右边。经过这样一趟下来,该...

    说明:

        快速排序是一个速度非常快的交换排序算法,它的基本思路很简单,从待排的数据序列中任取一个数据(如第一个数据)作为基准值,所有比它小的元素放到左边,所有比它大的元素放到右边。经过这样一趟下来,该序列形成左右两个子序列,左边序列中的数据元素的值都比基准值小,右边序列中数据元素的值都比基准值大。接下来对左右两个子序列进行递归排序。

    平均时间复杂度是T(n) = o(logn)

    实现步骤:

        1、定义一个变量i从坐起第一个索引开始,找大于基准值的元素的索引,并用i记录;

        2、定义一个变量j,从右起第一个索引开始,找小于基准值的元素的索引,并用j来记录。

        3、如果i < j,交换i、j两个索引处的元素。

        重复执行以上1、2、3步骤,直到i>=j,可以判断j左边的元素都小于基准值,j右边的元素都大于基准值,最后将基准值与j索引处的元素交换即可。

    代码:

    public class Test {
    
    	public static void main(String[] args) {
    		int[] data = new int[]{ 5, 3, 6, 2, 1, 9, 4, 8, 7, 10};
    		System.out.println("排序前的数组");
            print(data);
            System.out.println("开始排序");
            quickSort(data,0,data.length-1);
            System.out.println("排序后的数组");
            print(data);
    	}
    
    	/**
    	 * 快速排序
    	 * @param data	数组
    	 * @param begin	开始下标
    	 * @param end	结束下标
    	 */
    	private static void quickSort(int[] data, int begin, int end) {
    		if(begin>=end)return;
    		int point = data[begin];//保存起始值作为基准数
    		int i = begin+1;
    		int j = end;
    		while(true){
    			while(i<end && data[i]<point){//从前往后:找到大于point的数的下标i
    				i++;
    			}
    			while(j>begin && data[j]>point){//从后往前:找到小于point的数的下标j
    				j--;
    			}
    			if(i<j){//如果i在前面,则交换位置
    				swap(data,i,j);
    			}else{//否则退出循环
    				break;
    			}
    		}
    		//以上循环完成后,小于point的数全都在前面,大于point的数全都在后面,
    		//下标j对应的数data[j]是小于point的,所以要单独交换
    		System.out.println("交换前:");
    		print(data);
    		swap(data,begin,j);
    		System.out.println("交换后:");
    		print(data);
    		//递归两边
    		quickSort(data,begin,j-1);
    		quickSort(data,j+1,end);
    	}
    
    	/**
    	 * 打印数组
    	 * @param data
    	 */
    	private static void print(int[] data) {
    		for(int i=0;i<data.length;i++){
                System.out.print(data[i]+"\t");
            }
            System.out.println();
    	}
    
    	/**
    	 * 交换数组中两个不同下标位置对应的数据
    	 * @param data	数组
    	 * @param i		下标i
    	 * @param j		下标j
    	 */
        public static void swap(int[] data,int i,int j){
            if(i==j){
                return;
            }
            data[i] = data[i]+data[j];
            data[j] = data[i]-data[j];
            data[i] = data[i]-data[j];
        }
    }
    输出结果:

    排序前的数组
    5	3	6	2	1	9	4	8	7	10	
    开始排序
    交换前:
    5	3	4	2	1	9	6	8	7	10	
    交换后:
    1	3	4	2	5	9	6	8	7	10	
    交换前:
    1	3	4	2	5	9	6	8	7	10	
    交换后:
    1	3	4	2	5	9	6	8	7	10	
    交换前:
    1	3	2	4	5	9	6	8	7	10	
    交换后:
    1	2	3	4	5	9	6	8	7	10	
    交换前:
    1	2	3	4	5	9	6	8	7	10	
    交换后:
    1	2	3	4	5	7	6	8	9	10	
    交换前:
    1	2	3	4	5	7	6	8	9	10	
    交换后:
    1	2	3	4	5	6	7	8	9	10	
    排序后的数组
    1	2	3	4	5	6	7	8	9	10	
    




    展开全文
  • 快速排序 java代码

    2018-02-06 18:13:04
    java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码
  • 详细解释了快速排序java实现.里面有代码,还有注释说明
  • 快速排序java代码实现

    万次阅读 2018-08-18 10:45:07
    常用排序的时间及空间复杂度: 时间复杂度和空间复杂度详见:https://blog.csdn.net/jsjwk/article/details/84315770 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录...

     常用排序的时间及空间复杂度:

    时间复杂度和空间复杂度详见:https://blog.csdn.net/jsjwk/article/details/84315770

    稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

    一趟快速排序的算法是:

    1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

    2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

    3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;

    4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

    5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)

     

    示例

    假设用户输入了如下数组:

    下标012345
    数据627389

    创建变量i=0(指向第一个数据), j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

    我们要把所有比k小的数移动到k的左面,所以我们可以开始寻找比6小的数,从j开始,从右往左找,不断递减变量j的值,我们找到第一个下标3的数据比6小,于是把数据3移到下标0的位置,把下标0的数据6移到下标3,完成第一次比较:

    下标012345
    数据327689

    i=0 j=3 k=6

    接着,开始第二次比较,这次要变成找比k大的了,而且要从前往后找了。递加变量i,发现下标2的数据是第一个比k大的,于是用下标2的数据7和j指向的下标3的数据的6做交换,数据状态变成下表:

    下标012345
    数据326789

    i=2 j=3 k=6

    称上面两次比较为一个循环。

    接着,再递减变量j,不断重复进行上面的循环比较。

    在本例中,我们进行一次循环,就发现i和j“碰头”了:他们都指向了下标2。于是,第一遍比较结束。得到结果如下,凡是k(=6)左边的数都比它小,凡是k右边的数都比它大:

    下标012345
    数据326789

    如果i和j没有碰头的话,就递加i找大的,还没有,就再递减j找小的,如此反复,不断循环。注意判断和寻找是同时进行的。

    然后,对k两边的数据,再分组分别进行上述的过程,直到不能再分组为止。

    注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。

    java代码实例:

    public class QuickTest {
         public static void sort(int[] a) {
            if (a.length > 0) {
                sort(a, 0, a.length - 1);
            }
    
        }
    
        public static void sort(int[] a, int low, int height) {
            int i = low;
            int j = height;
            if (i > j) {//放在k之前,防止下标越界
                return;
            }
            int k = a[i];
    
            while (i < j) {
                while (i < j && a[j] > k) { //找出小的数
                    j--;
                }
                while (i < j && a[i] <= k) { //找出大的数
                    i++;
                }
                if (i < j) {//交换
                    int swap = a[i];
                    a[i] = a[j];
                    a[j] = swap;
                }
    
            }
             //交换K
            k = a[i];
            a[i] = a[low];
            a[low] = k;
    
            //对左边进行排序,递归算法
            sort(a, low, i - 1);
            //对右边进行排序
            sort(a, i + 1, height);
        }
    
    
        public static void main(String[] args) {
            int[] arr = {5, 9, 7, 4, 5, 7, 6, 1, 9, 9, 7, 4};
            System.out.println(Arrays.toString(arr));
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
    }
    

    结果为:

    [5, 9, 7, 4, 5, 7, 6, 1, 9, 9, 7, 4]
    [1, 4, 4, 5, 5, 6, 7, 7, 7, 9, 9, 9]

    展开全文
  • 主要介绍了Java 快速排序(QuickSort)原理及实现代码,有需要的朋友可以参考一下
  • 主要介绍了Java基于分治法实现快速排序算法,结合实例形式分析了java基于分治法的快速排序相关实现技巧,代码中备有较为详细的注释说明便于理解,需要的朋友可以参考下
  • 与本人博文《算法专项(1)——快速排序》相配套的工程源码,用JAVA实现
  • 快速排序Java代码简洁实现

    千次阅读 2020-04-29 16:29:11
    本文将阐述算法的基本思想,并用Java代码的形式实现快速排序代码。 算法思想 快速排序主要采用分治的基本思想,每次将一个位置上的数据归位,此时该数左边的所有数据都比该数小,右边所有的数据都比该数大,然后...

    学习过数据结构的同学们都知道,快速排序算法是一种时间复杂度为O(nlogn)的排序算法,在各种排序算法中算是较为高效的方法,企业面试中也经常有手撕快排的环节。本文将阐述算法的基本思想,并用Java代码的形式实现快速排序代码。

    算法思想

    快速排序主要采用分治的基本思想,每次将一个位置上的数据归位,此时该数左边的所有数据都比该数小,右边所有的数据都比该数大,然后递归将已归位的数据左右两边再次进行快排,从而实现所有数据的归位。

    举例

    我们有一组待排序数据:

    5 2 6 9 1 3 4 8 7 10

    我们首先拿到数组中的首个数字k=5,并且设置两个指针i和j。将i设置指向数组的起始数字5,j设置指向数组的末尾数字10。首先将j指向的数字与k比较,如果比k小,则将i和j指向的数字交换,如果不小于k则j指针不断向前移动。我们可以看到本例中j的移动过程是10->7->8->4,此时4比5小,则交换4和5,变成了如下序列:

    4 2 6 9 1 3 5 8 7 10

    每次交换后,另一个指针开始移动,i指针不断向后移动,寻找比5大的数字。i的移动过程是4->2->6,此时6比5大,则交换5和6,变成了如下序列:

    4 2 5 9 1 3 6 8 7 10

    再次轮到j指针向前移动,移动过程是6->3,此时3比5小,则交换3和5,变成了如下序列:

    4 2 3 9 1 5 6 8 7 10

    再次轮到i指针向后移动,移动过程是3->9,此时9比5大,则交换9和5,变成了如下序列:

    4 2 3 5 1 9 6 8 7 10

    再次轮到j指针向前移动,移动过程是9->1,此时1比5小,则交换1和5,变成了如下序列:

    4 2 3 1 5 9 6 8 7 10

    此时i指针和j指针相遇,数字5归位。再利用上述思想递归将5左右两边的序列进行排序,最终所有数字归位即可结束。

    Java代码实现

    public class QuickSort {
    	private void swap(int[] arr, int i, int j) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	
    	public void quickSort(int[] arr, int start, int end) {
    		if (start >= end)
    			return;
    		int k = arr[start];
    		int i = start, j = end;
    		while (i != j) {
    			while (i < j && arr[j] >= k)
    				--j;
    			swap(arr, i, j);
    			while (i < j && arr[i] <= k)
    				++i;
    			swap(arr, i, j);
    		}
    		quickSort(arr, start, i - 1);
    		quickSort(arr, i + 1, end);
    	}
    	
    	public static void main(String[] args) {
    		int[] arr = {5, 2, 6, 9, 1, 3, 4, 8, 7, 10};
    		new QuickSort().quickSort(arr, 0, arr.length - 1);
    		System.out.println(Arrays.toString(arr));
    	}
    }
    
    

    参考引用

    程序设计与算法(二)算法基础-快速排序

    展开全文
  • 网上关于快速排序的算法原理和算法实现都比较多,不过java实现并不多,而且部分实现很难理解,和思路有点不搭调。所以整理了这篇文章。如果有不妥之处还请建议。
  • 快速排序算法的Java代码实现, 本文通过详细注释解释实现逻辑.

    前面几篇博文用代码+注释的方式介绍了几种基本的排序, 文末有链接, 可以熟悉一下.
    今天的还是介绍一种适合大数据量的排序算法, 即快速排序, 简称快排, 也是面试中常见的算法题, 我试着用注释给详细阐述了实现逻辑

    一句话介绍实现逻辑: 使用分治思想, 找一个基准点(随意选, 本代码选的最末尾一个元素), 用来给数组内的元素分界, 通过挪动元素, 使得左边比基准点小, 右边的元素比基准点大, 然后, 使用相同的逻辑, 递归左右两边的元素, 直到子集中只剩下一个元素,得到最终排序好的结果.

    说起来容易, 实现起来, 还需要一番推敲, 好好研究一下代码, 欢迎读者朋友给予指正, 一起交流学习.
    代码中有详细注释, 如下:

    import org.junit.Test;
    
    /**
     * 功能说明:快速排序
     * 开发人员:@author MaLi
     */
    public class T05_QuickSort {
        /**
         * 排序入口
         *
         * @param arr 待排序数组
         */
        public void sort(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
            sort(arr, 0, arr.length - 1);
        }
    
        /**
         * 排序逻辑: 一句话概括, 找一个基准点(该程序选end位置的元素作为基准点), 基准点左边的比都是小的, 右边都是比基准点大的
         * 然后分治, 基准点两边各自执行相同的逻辑: 再各自找基准点, 各自的基准点的两边一边小, 一边大, 然后继续分治...
         * 直到基准点的两边只有一个元素
         * 思想是分治, 逻辑如上, 编程实现如下:
         * 1, 使用递归
         * 2, 选end, 也就是数组的最后一个元素作为基准点
         * 3, 选i作为 "已排序区间" 与"未排序区间"的分界
         * 4, 遍历未排序区间(使用j作为指针的循环), 如果比基准点小, 就放到已排序区间, 编程代码就是: 与i所在位置交换, i挪动到下一个位置(这是第一步)
         * 5, 关于j指针的循环遍历完成后, 交换基准点和i --> 目的: 为下面分治做准备, 这样基准点的两边有各自的特点: 左边都比基准点小, 右边反之;
         * 6, 基准点的两边递归上面的逻辑, 直到基准点的两边剩余一个元素, 递归结束, 数组已经有序了.
         *总结: 每一遍循环, 实现的结果有两个: 1,小的和大的分界;2, 基准点放到分界位置 --> 开启新的分治阶段
         *
         * @param arr   待排序数组
         * @param start 首元素位置
         * @param end   尾元素位置
         */
        public void sort(int[] arr, int start, int end) {
            // 递归结束条件: 只有一个元素
            if (start >= end) {
                return;
            }
            // 设定i为已排序与未排序的分界, 首先i指向未排序区间的第一个位置(这里刚开始, 初始化指向start)
            int i = start;
            // 关键逻辑1: 将数组中除去基准点外, 所有的元素以比基准点为标准分大小, 小的放左边, 大的放右边
            // 放左与放右, 体现在代码上就是是否交换i与j位置的元素, 如果小于基准点, 那么就将这个元素放到边界内
            for (int j = start; j < end; j++) {
                if (arr[j] < arr[end]) {
                    // 交换一下就放到边界内了
                    swap(arr, i, j);
                    // 还要把i边界往后挪动以为
                    i++;
                }
            }
            // 把基准点放到边界位置上, 这样才做到左边的比基准点小, 右边的比基准点大
            swap(arr, i, end);
            //递归: 分治即把左右两边按照相同逻辑处理
            sort(arr, start, i - 1);
            sort(arr, i + 1, end);
        }
    
        /**
         * 交换数组中两个位置上的元素
         *
         * @param arr    待排序数组
         * @param index1 交换位置的角标1
         * @param index2 交换位置的角标2
         */
        public void swap(int[] arr, int index1, int index2) {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }
        
        // 以下为测试代码
        @Test
        public void testSort() {
            int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
            sort(arr);
            for (int i : arr) {
                System.out.println(i);
            }
            System.out.println("-------------------");
            arr = new int[]{1};
            sort(arr);
            for (int i : arr) {
                System.out.println(i);
            }
            System.out.println("-------------------");
            arr = new int[]{};
            sort(arr);
            System.out.println(arr);
        }
    }
    

    排序算法快捷进入

    1, 插入排序
    2, 选择排序
    3, 归并排序
    4, 快速排序
    5, 冒泡排序
    不断补充…

    展开全文
  • 主要介绍了Java编程实现快速排序及优化代码详解,具有一定借鉴价值,需要的朋友可以了解下。
  • 主要介绍了java 算法之快速排序实现代码的相关资料,需要的朋友可以参考下
  • 快速排序——JAVA实现(图文并茂)

    万次阅读 多人点赞 2018-03-06 15:10:06
    那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待...
  • Java代码实现快速排序(QuickSort)

    千次阅读 2018-11-14 09:27:45
    Java代码实现快速排序(QuickSort) 核心思想 如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据为pivot(分区点)。 我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到...
  • 快速排序java实现

    万次阅读 多人点赞 2018-09-05 14:53:42
    那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,...
  • 冒泡排序 简单选择排序 直接插入排序 希尔排序 归并排序 快速排序等排序方法,使用java详细代码 附注释,清晰明白
  • 排序有哪几种方法?请列举。并用JAVA实现一个快速排序.,需要的朋友可以参考下
  • 快速排序Java实现--最简单的实现方法

    万次阅读 多人点赞 2017-09-18 13:41:06
    快速排序,顾名思义,是一种速度快,效率高的排序算法。 快排原理:  在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的...
  • 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。...
  • java实现快速排序

    千次阅读 多人点赞 2020-10-07 15:43:18
    什么是快速排序 ...从快速排序的基本思想可以分析出其实现思路: 一、选取一个枢轴元素(也叫基准元素) 二、将数组分割成两部分,一部分数据都小于或等于枢轴元素,另一部分数据都大于枢轴元素 三、对分割的子数
  • java实现快速排序算法

    千次阅读 2020-12-18 15:34:13
    快速排序 1、算法思想 快速排序是由冒泡排序改进而得到的,是一种分区交换排序方法。思想如下: 一趟快速排序采用从两头向中间扫描的方法,同时交换与基准记录逆序的记录。 (1)在待排序的N个记录中任取一个元素...
  • 主要介绍了java实现的各种排序算法代码示例,比较全面,代码亲测可用,如有不足之处,欢迎留言指出。
  • 快排Java代码实现(Quick Sort)

    千次阅读 2019-03-22 16:12:54
    基本思想:通过一趟快速排序将待排数组分割成独立的两份部分;其中一部分数组的值均比另一部分数组的值小,则可分别对着两部分数组继续进行排序,以达到整个序列有序。 快排的平均时间复杂度为n*log(n),最坏的...
  • 6、快速排序(Quick Sort) 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 6.1 ...
  • Java代码实现部分,比较有意思,也具参考性。像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java...
  • java代码实现排序算法(冒泡,快速,简单选择,堆排,直接插入,希尔,归并),代码本身的注释不多,主要注释的还是当前排序算法的一些特点,比如时间复杂度,空间复杂度,一趟排序后数列的特点。适合了解算法性质...
  • 快速排序Java实现

    千次阅读 2019-08-26 13:29:19
    快速排序Java实现 快速排序是一种分治的排序算法,将一个数组分成两个数组,将两部分独立地排序。一般策略是先取基准元素,又称切分元素,从数组右边开始向左扫描直到找到一个不大于它的元素填入到右边的坑内,然后...
  • java快速排序的两种思想与代码实现

    千次阅读 多人点赞 2019-01-17 20:50:49
    本文介绍了两种快速排序的思想,并提供了java快速排序算法的代码实现。另外还说明了什么是算法的稳定性
  • 快速排序算法的三种方式及其优化java实现1、快速排序算法的简绍2、快速排序的基本思想3、快速排序左右指针法图解4、快速排序左右指针法核心代码5、快速排序挖坑法图解6、快速排序挖坑法核心代码7、快速排序前后指...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 111,740
精华内容 44,696
关键字:

快速排序java代码实现

java 订阅