java快速排序讲解

淩亂°似流年 2023-03-01 13:54 1阅读 0赞

今天最后一篇排序了  
快速排序，快速排序，就是快速的排列一个数组  
是什么代码敢让它称之为**快速排序**  
让我们看看其中的原理：

--------------------

原理：  
和其他两种排序不同的是，它要选一个基准数，这个基准数可以是中间的那个数，也可以是任意一个数，大于基准数的放在右边，小于基准数的放于左边，这样的话一个有序的数组又诞生了  
理清思路，看看它是怎么实践操作的

--------------------

**为了更好的演示，我们给出一个无序数组**

--------------------

一个无序的数组就在这了

int a[]={ 3,8,1,0,14};

#### 第一趟排序 ####

1.  选一个基准数，我们选第一个数
2.  从第2个数开始比较
3.  第二个数8比3大，不动
4.  第三个数1比3小，放在数组的左边，数组为1，3，8，0，14
5.  第四个数0比3小，放在数组的左边，数组为1，0，3，8，14
6.  第5个数14比3大，不动

#### 第二趟排序 ####

1.  还是选一个基准数，我们选第一个数1
2.  从第二个数开始比较
3.  第二个数0比1小，放在数组的左边，数组为0，1，3，8，14
4.  第三个数3比1大，不动
5.  第四个数8比1大，不动
6.  第五个数14比1大，不动

……经过若干次的排序后

数组已经是有序数组了

# 代码 #

选一个基准数，然后定义两个数left和right，就迎刃而解了

/** * 功能：演示快速排序法 */
    package lesson_18;
    
    public class Quick_sort { 
    
    	/** * @param args */
    	public static void main(String[] args) { 
    		// TODO 自动生成的方法存根
    		int arr[]={ 1,45,62,6,24};
    		
    		QuickSort qs =new QuickSort();
    		qs.sort(0,arr.length,arr);
    	}
    }
    
    //快速排序法
    class QuickSort
    { 
    	public void sort(int left,int right,int [] array)
    	{ 
    		int l =left;
    		int r =right;
    		int pivot =array[(left+right)/2];
    		int temp=0;
    		
    		while(l<r)
    		{ 
    			while(array[l]<pivot) l++;
    			while(array[r]>pivot) r--;
    			
    			if(l>=r) break;
    			
    			temp=array[l];
    			array[l]=array[r];
    			array[r]=temp;
    			
    			if(array[l]==pivot) --r;
    			if(array[r]==pivot) ++l;
    		}
    		
    		if(l==r)
    		{ 
    			l++;
    			r--;
    		}
    		
    		if(left<r) sort(left,r,array);
    		if(right>l) sort(l,right,array);
    		
    		for(int i=0;i<array.length;i++)
    		{ 
    			System.out.print(array[i]+" ");
    		}
    	}
    }

冒泡排序:[https://blog.csdn.net/weixin\_45445598/article/details/107605033][https_blog.csdn.net_weixin_45445598_article_details_107605033]  
选择排序：[https://blog.csdn.net/weixin\_45445598/article/details/107606792][https_blog.csdn.net_weixin_45445598_article_details_107606792]

[https_blog.csdn.net_weixin_45445598_article_details_107605033]: https://blog.csdn.net/weixin_45445598/article/details/107605033
[https_blog.csdn.net_weixin_45445598_article_details_107606792]: https://blog.csdn.net/weixin_45445598/article/details/107606792