排序算法之快速排序

蔚落 2022-06-09 06:49 284阅读 0赞

package com.lin.sort;
    /** 
     * @author 作者 林尤庆
     * @version 创建时间：2016-8-12 下午02:42:05 
     * 类说明 :快速排序法(Quick Sort)
     * 
     * 快速排序的最坏时间复杂度为O(n^2).
     * 快速排序所占用的辅助空间为递归时所需栈的深度，故空间复杂度为O（log2(n)）。同时，快速排序是不稳定的排序。
     */
    public class QuickSort {
    
    	public void swap(int a[],int i,int j){
    		int temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
    	
    	public int partSort(int a[],int low,int high){
    		int pivot,p_pos,i;
    		p_pos=low;
    		pivot=a[p_pos];
    		for(i=low+1;i<=high;i++){
    			if(a[i]>pivot){
    				p_pos++;
    				swap(a, p_pos, i);
    			}
    		}
    		swap(a, low, p_pos);
    		return p_pos;
    	}
    	
    	public void quicksort(int a[],int low,int high){
    		int pivot;
    		if(low<high){
    			pivot=partSort(a, low, high);
    			quicksort(a, low, pivot-1);
    			quicksort(a, pivot+1, high);
    		}
    	}
    	
    	public static void main(String[] args) {
    		// 快速排序法(Quick Sort)
    		int vec[] = new int[] { 37, 46, 33, -5, 17, 51 };
    		QuickSort s = new QuickSort();
    		long begin = System.currentTimeMillis();
    		for (int k = 0; k < vec.length; k++) {
    			s.quicksort(vec, 0, vec.length-1);
    		}
    		long end = System.currentTimeMillis();
    		System.out.println("快速法用时为：" + (end - begin));
    		// 打印排序好的结果
    		for (int i = 0; i < vec.length; i++) {
    			System.out.print(vec[i]+" ");
    		}
    	}
    }

测试结果：

快速法用时为：0
    51 46 37 33 17 -5

发表评论取消回复

表情：

评论列表（有 0 条评论，284人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法之快速排序

快速排序是一种基于分治思想的排序算法。它的基本思想是通过一趟排序将待排数据分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，然后再分别对这两部分继续进行排序，重

谁践踏了优雅/ 2024年03月23日 07:09/ 0 赞/ 115 阅读

相关排序算法之快速排序

\[交换排序-快速排序\] 1.算法思想：选择一个元素作为基准，先从右向左遍历数组寻找比基准小的数a，然后从左向右寻找比基准大的数b，交换a和b的值，当左右会面

叁歲伎倆/ 2022年12月29日 14:25/ 0 赞/ 201 阅读

相关排序算法之快速排序

> 快速排序。 > 从数组中取出一个基准数，遍历数组中的每个元素，与基准数比较大小，将小于基准数的元素放在其左侧，大于基准数的元素放在其右侧， >

小咪咪/ 2022年11月03日 04:11/ 0 赞/ 253 阅读

相关排序算法之_快速排序

排序算法之-快速排序 package com.weidd.best.sort; / @program: SortDemo

水深无声/ 2022年10月30日 13:21/ 0 赞/ 243 阅读

相关排序算法之快速排序

同样的先上这张图 ![Center][] 下面分析交换排序之快速排序：快速排序的思想是先选择一个基准元素（一般取第一个元素），然后对剩下的元素作两端遍历，左边找

Dear 丶/ 2022年09月25日 15:24/ 0 赞/ 277 阅读

相关排序算法之快速排序

快速排序的基本思想是：通过一趟排序将要排序的[数据分割][Link 1]成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行

爱被打了一巴掌/ 2022年08月06日 13:22/ 0 赞/ 269 阅读

相关排序算法之快速排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

朴灿烈づ我的快乐病毒、/ 2022年06月16日 08:41/ 0 赞/ 321 阅读

相关排序算法之快速排序

package com.lin.sort; / @author 作者林尤庆 @version 创建时间：2016-8-12 下午02

蔚落/ 2022年06月09日 06:49/ 0 赞/ 285 阅读

相关排序算法之快速排序

快速排序是冒泡排序的改进版，也是最好的一种内排序，也是作为程序员必须掌握的一种排序方法。快速排序的基本思想是 > 1、先从数列中取出一个数作为基准数 > 2、分区过程，

系统管理员/ 2022年01月22日 10:29/ 0 赞/ 350 阅读

相关排序算法之快速排序

快速排序是一种高效的排序算法，它采用分而治之的思想，把大的拆分成小的，小的再拆分为更小的。其原理是：对于给定的数组，通过一趟排序之后，将原序列分为两部分，其中前一部分的所

秒速五厘米/ 2021年09月18日 04:24/ 0 赞/ 439 阅读