快速排序

灰太狼 2023-07-05 14:29 11阅读 0赞

快速排序：

挖坑填数：先取第一个数，然后从后往前找 比这个数小的，放在第一个位置上，然后再正着往前找比最开始的数大的，放在后面缺的坑里。然后再从后面那个坑开始往前找比最开始的数小的，放在前面那个坑里。直到最中间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTgxMTU0_size_16_color_FFFFFF_t_70][]

### 代码实现： ###

public class QuickSort {
    	public static void main(String[] args) {
    		int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
    		quickSort(arr, 0, arr.length - 1);
    		System.out.println("排序后:");
    		for (int i : arr) {
    			System.out.println(i);
    		}
    	}
    
    	private static void quickSort(int[] arr, int low, int high) {
    
    		if (low < high) {
    			// 找寻基准数据的正确索引
    			int index = getIndex(arr, low, high);
    
    			// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
    			quickSort(arr, 0, index - 1);
    			quickSort(arr, index + 1, high);
    		}
    
    	}
    
    	private static int getIndex(int[] arr, int low, int high) {
    		// 基准数据
    		int tmp = arr[low];
    		while (low < high) {
    			// 当队尾的元素大于等于基准数据时,向前挪动high指针
    			while (low < high && arr[high] >= tmp) {
    				high--;
    			}
    			// 如果队尾元素小于tmp了,需要将其赋值给low
    			arr[low] = arr[high];
    			// 当队首元素小于等于tmp时,向前挪动low指针
    			while (low < high && arr[low] <= tmp) {
    				low++;
    			}
    			// 当队首元素大于tmp时,需要将其赋值给high
    			arr[high] = arr[low];
    
    		}
    		// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
    		// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
    		arr[low] = tmp;
    		return low; // 返回tmp的正确位置
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTgxMTU0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020021517240427.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTgxMTU0,size_16,color_FFFFFF,t_70