八大排序之交换排序—快速排序

落日映苍穹つ 2022-05-13 04:44 224阅读 0赞

## 快速排序 ##

快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。  
**`基本思想`**：选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。  
时间复杂度：  
**`最差情况`**：当数组原本就按从小到大顺序排列时：  
10 20 30 40 50 60 70 80 第一轮比较，将10分别与20、30、…、80比较，共比较n-1次  
第二轮比较，将20分别与30、…、80比较，共比较n-2次  
…  
共比较(n-1)+(n-2)+…+1次，即时间复杂度为O(n2)，与冒泡排序时间复杂度一样

**`一般情况（最好情况）`**：时间复杂度为O(nlog2n)

代码1：

import java.util.Scanner;
    
    public class Main {
    	@SuppressWarnings("resource")
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		String[] st = sc.nextLine().split(" ");
    		int[] arr = new int[st.length];
    		for (int i = 0; i < arr.length; i++) {
    			arr[i] = Integer.parseInt(st[i]);
    		}
    		int low = 0, high = arr.length - 1;
    		quickSort(arr, low, high);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    		System.out.println();
    	}
    
    	private static void quickSort(int[] arr, int low, int high) {
    		if (low >= high) {
    			return;
    		}
    		// 对数组进行划分，比key小的元素在低位
    		int pt = partition(arr, low, high);
    		// 对arr[low,,,pt-1]和arr[pt+1,,,high]进行递归，每次比基准值小的在左，大的在右
    		quickSort(arr, low, pt - 1);
    		quickSort(arr, pt + 1, high);
    	}
    
    	// 每次以第一个元素即arr[low]为基准，比基准值小的在左，大的在右
    	// 返回基准值最终在数组中的位置
    	private static int partition(int[] arr, int low, int high) {
    		int key = arr[low];
    		while (low < high) {
    			// 从右端开始扫描，定位到第一个比key小的元素
    			while (low < high && arr[high] >= key) {
    				high--;
    			}
    			swap(arr, low, high);
    			// 从左端开始扫描，定位到第一个比key大的元素
    			while (low < high && arr[low] <= key) {
    				low++;
    			}
    			swap(arr, low, high);
    		}
    		return low;
    	}
    	
    	// 交换位置
    	private static void swap(int[] arr, int low, int high) {
    		int temp = arr[high];
    		arr[high] = arr[low];
    		arr[low] = temp;
    	}
    }

代码2：

import java.util.Scanner;
    
    public class Main {
    	@SuppressWarnings("resource")
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		String[] st = sc.nextLine().split(" ");
    		int[] arr = new int[st.length];
    		for (int i = 0; i < arr.length; i++) {
    			arr[i] = Integer.parseInt(st[i]);
    		}
    		int low = 0, high = arr.length - 1;
    		quickSort(arr, low, high);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    		System.out.println();
    	}
    
    	public static void quickSort(int[] arr, int left, int right) {
    		if (left < right) {// 如果只有1个元素就不执行，2个及以上元素才会执行
    			int pivot = arr[left]; // 设置为基准值
    			int low = left; // 左指针
    			int high = right; // 右指针
    			
    			while (low < high) {
    				while (low < high && arr[high] >= pivot) { // 右指针指向的值大于等于基准值
    					high--; // 右指针左移，直到指向的值小于基准值
    				}
    				arr[low] = arr[high]; // 将左指针指向的值和该值交换
    				while (low < high && arr[low] <= pivot) { // 左指针指向的值小于等于基准值
    					low++; // 左指针右移，直到指向的值大于基准值
    				}
    				arr[high] = arr[low]; // 将该值与右指针指向的值交换
    			}
    			arr[low] = pivot; // 将基准值填入正确的位置，这样得到基准值左边的数据都小于它，右边同理
    			quickSort(arr, left, low - 1);
    			quickSort(arr, low + 1, right);
    		}
    	}
    }