java数据结构之快速排序

红太狼 2022-04-04 04:27 192阅读 0赞

快速排序（Quicksort）是对[冒泡排序][Link 1]的一种改进。

快速排序由 C. A. R. Hoare 在 1962 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[递归][Link 2]进行，以此达到整个数据变成有序[序列][Link 3]。

java代码如下：

package 数据结构;
    
    public class kuaisupaixu {
        public static int quicksort(long arr[],int left,int right,long center){//一开始用最右边的数据作为中间值
        	int leftenum=left-1;
        	int rightenum=right;
        	while(true){
        		while(leftenum<rightenum&&arr[++leftenum]<center);
        		while(rightenum>leftenum&&arr[--rightenum]>center);
        		if(leftenum>=rightenum){
        			break;
        		}
        		else{//如果此时左边下标没有大于右边，则互相交换数据即可
        			long change;
        		change=arr[leftenum];
        		arr[leftenum]=arr[rightenum];
        		arr[rightenum]=change;
        		}
        	}
        	long change1;//循环结束的位置与中间值数据交换
        	change1=arr[right];
        	arr[right]=arr[leftenum];
        	arr[leftenum]=change1;
        	return leftenum;//得到的位置作为下一次排序的中间值
        }
        public static void display(long arr[]){//打印数据
        	for(int i=0;i<arr.length;i++){
        		System.out.print(arr[i]+" ");
        		
        	}
        	System.out.println("\n");
        }
        public static void sort(long arr[],int left,int right){//递归进行排序
        	if(right-left<=0){
        		return;
        	}
        	else{
        		long point=arr[right];//设置关键字
        		int rr=quicksort(arr,left,right,point);
        		sort(arr,left,rr-1);//对左边快速排序
        		sort(arr,rr+1,right);//对右边快速排序
        	}
        }
    }

测试：

package 数据结构;
    
    public class Testkuaisupaixu {
    public static void main(String args[]){
    	long arr[]=new long[10];
    	for(int i=0;i<10;i++){
    		arr[i]=(long)(Math.random()*99);
    	}
    	kuaisupaixu.display(arr);
    	kuaisupaixu.sort(arr, 0, arr.length-1);
    	kuaisupaixu.display(arr);
    }
    }

最后输出结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfX2xpeW9uZw_size_16_color_FFFFFF_t_70][]

好啦,这次就到这里啦，有问题可以和我留言哦！

邮箱：2321591758@qq.com

其他博客的链接：

[Github个人网站][Github]      [知乎][Link 4]      [简书][Link 5]

欢迎各位访问哦，这次就到这里啦！

[Link 1]: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
[Link 2]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695
[Link 3]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfX2xpeW9uZw_size_16_color_FFFFFF_t_70]: /images/20220404/eef1beaf8d7448d6bcf6ce7ef5440acf.png
[Github]: http://www.imlowliness.club
[Link 4]: https://www.zhihu.com/people/li-yong-ji-suan-ji/activities
[Link 5]: https://www.jianshu.com/u/6c1284ced65e