排序算法之快速排序

秒速五厘米 2021-09-18 04:24 377阅读 0赞

快速排序是一种高效的排序算法，它采用分而治之的思想，把大的拆分成小的，小的再拆分为更小的。  
其原理是：对于给定的数组，通过一趟排序之后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，知道序列中的所有数值均有序为止。

其算法步骤主要是：

1.  分解。将输入的序列 arr\[ m…n \] 划分成两个非空子序列 arr\[ m…k \] 和 arr\[ k+1…n \]，arr\[ m…k \] 中的所有值都比 arr\[ k+1…n \] 小。
2.  递归求解。通过递归调用进行排序。
3.  合并。由于对分解出的两个子序列的排序是针对当前数组进行的，所以排完序后，不需要再进行合并。

例如：  
arr = \{ 5, 4, 2, 9, 6, 1 \}  
首先定义 int index = 5（arr\[0\]）， int left = 0，int right=5  
1.开始从左到有遍历数组，找比index小的值，放在left = 0的位置  
条件： left<right 如果 arr\[right\] >= index，那么继续向左遍历 right–（找第一个小于 index 的值）；  
找到之后，判断 left < right arr\[left++\] = arr\[right\]  
也就是：  
arr=\{1,4,2,9,6,1\}  
这个时候 left = 1，right=5  
2. 开始从右向左遍历数组，找比index大的值，放在right = 5的位置  
条件：left<right 如果 arr\[left\] <index，那么继续向右遍历 left++(找比index大的值)  
找到之后，判断 left < right arr\[right–\] = arr\[left\]  
也就是：  
arr=\{1,4,2,9,6,9\}  
依次类推…

示例代码：

public class QuickSort {
    
    	public static void sort(int[] arr, int low, int high) {
    		// 定义两个指针，保存左指针，右指针
    		int left = low;
    		int right = high;
    		int index = arr[low]; // 保存基准值（作为比较用）
    		while(left < right) {
    			// 从右向左遍历，找到比index小的值，交换位置
    			while(left < right && arr[right] >= index) {
    				right--;
    			}
    			if(left < right) {
    				arr[left++] = arr[right];
    			}
    			// 从左向右遍历，找到比index大的值，交换位置
    			while(left < right && arr[left] < index) {
    				left++;
    			}
    			if(left < right) {
    				arr[right--] = arr[left];
    			}
    		}
    		arr[left] = index;
    		sort(arr,low,left-1);
    		sort(arr,left+1,high);	
    	}
    	public static void main () {
    		int[] arr = new int[] { 5, 4, 2, 9, 6, 1 };
           	sort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
    	}
    
    }