数组（五）--快速排序

系统管理员 2021-09-14 08:14 302阅读 0赞

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

它的基本思想是：

> 一趟快速排序的算法是：

> > 1）设置两个变量i、j， [排序][Link 2] 开始的时候：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-完成的时候，此时令循环结束）。
> > 
> > ![632025-20151209115932433-376548233.png][]  
> > 
> > 
> >     public class Demo9 {
> >     	public static void main(String[] args){
> >     		int[] arr={4,2,9,3,5,8,7,1,6};
> >     		int start=0;
> >     		int end=arr.length-1;
> >     		quickSort(arr,start,end);
> >     		printArray(arr);
> >     	}
> >     	
> >     	public static void quickSort(int[] arr,int low,int high){
> >     		int start=low;
> >     		int end=high;
> >     		int key=arr[low];
> >     		while(start<end){
> >     			//从后往前开始比较
> >     			while(end>start && arr[end]>=key)//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
> >     				end--;
> >     			if(arr[end]<=key){
> >     				int temp=arr[end];
> >     				arr[end]=arr[start];
> >     				arr[start]=temp;
> >     			}
> >     			//从前往后比较
> >     			while(end>start && arr[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置，然后又从后往前比较
> >     				start++;
> >     			if(arr[start]>=key){
> >     				int temp=arr[start];
> >     				arr[start]=arr[end];
> >     				arr[end]=temp;	
> >     			}
> >     		//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
> >     		}
> >     		//递归
> >     		if(start>low) 
> >     			quickSort(arr,low,start-1);
> >     		if(start<high) 
> >     			quickSort(arr,end+1,high);
> >     				
> >     	}
> >     	
> >     	//打印数组
> >     		public static void printArray(int[] arr){
> >     			System.out.print("[");
> >     			for(int i=0;i<arr.length;i++){
> >     				if(i!=arr.length-1)
> >     					System.out.print(arr[i]+" ");
> >     				else
> >     					System.out.print(arr[i]+"]");
> >     			}
> >     		}
> >     }
> > 
> >   
> >   
> >

[Link 1]: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
[Link 2]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F
[632025-20151209115932433-376548233.png]: /images/20210720/606c8d8aeb3e42639919dbd15e56eb77.png