快速排序之Java实现

傷城~ 2022-06-16 06:53 42阅读 0赞

### 快速排序思想： ###

从数组中挑选一元素作为基数（一般选数组第一个数字），然后通过排序，将比此数大的排到它 的左边，比它小的排到右边；然后再分别对左右两边的子数组进行相应排序，直到子数组的长度是1 ，排序结束。

### 举例说明：一组数：arr  = \{5,9,1,3,52,13,2,8,4\} ###

选择第一个数字，5，作为基数，i = 0,j=8;

**(1)**从数组后边开始，4比5小，那么将4,赋值给arr\[0\],然后i++；此时 i = 1，j = 8;（首先从后往前比较，如果数字比基数小，那么此值赋给arr\[i++\]，下一步从前往后开始比较；如果数字比基数大，那么j--，下一步依旧从后边取数字与基数比较）。数组变成：\{4,9,1,3,52,13,2,8,4\}，i = 1, j =8

**(2)**从数组下标是1位置开始，9比5大，那么将9 的值赋给 arr\[8\];（从前往后比较，如果数字比基数大，那么此值赋给arr\[j--\]，下一步从后往前比较;如果数字比基数小，那么i++,下一步依旧从前往后比较）。数组变成：\{4,9,1,3,52,13,2,8,9\} , i = 1,j = 7

**(3)**数组下标是7的数字与5比较，比5 大，那么 ：数组变成：\{4,9,1,3,52,13,2,8,9\} , i = 1,j = 6

**(4)**数组下标是6的数字与5比较，2比5小，那么将2,赋值给arr\[1\],然后i++。此时数组变成：\{4,2,1,3,52,13,2,8,9\}， i = 2，j = 6;

**(5)**数组下标是2的数字与5比较，1比5小，i++。此时数组变成：\{4,2,1,3,52,13,2,8,9\}， i = 3，j = 6;

**(6)**数组下标是3的数字与5比较，3比5小，i++。此时数组变成：\{4,2,1,3,52,13,2,8,9\}， i = 4，j = 6;

**(7)**数组下标是4的数字与5比较，52比5大，那么将52的值赋给 arr\[6\]，且 j--。此时数组变成：\{4,2,1,3,52,13,52,8,9\}， i = 4，j =5;

**(8)**数组下标是5的数字与5比较，13比5大，那么 j--。此时数组变成：\{4,2,1,3,52,13,52,8,9\}， i = 4，j =4;

**(9)**令arr\[i\] = 5，即arr\[4\] = 5。此时数组：\{4,2,1,3,5,13,52,8,9\}， i = 4，j =4;

**(10)**然后基数左右两边的子数组再按照上述逻辑递归操作即可。

代码实现：

public static void quickSort(int [] arr,int begin,int end) throws Exception{
    		if(arr == null || begin < 0 || end < 0 || begin > end)
    			throw new Exception("参数输入有误");
    		if(begin < end){
    			int first = begin;
    			int last = end;
    			int temp = arr[first];
    			while(first < last){
    				while(first < last && arr[last] > temp){
    					last--;
    				}
    				if(first < last)
    				arr[first++] = arr[last];
    				while(first < last && arr[first] < temp){
    					first++;
    				}
    				if(first < last)
    				arr[last--] = arr[first];
    			}
    			arr[first] = temp;
    			quickSort(arr,begin,first-1);
    			quickSort(arr,first+1,end);
    		}
    	}

测试：

public static void main(String[] args) throws Exception {
    		int [] arr = {5,9,1,3,52,13,2,8,4};
    		quickSort(arr,0,8);
    		for(int i : arr){
    			System.out.println(i);
    		}
    	}