快速排序算法详解与实现

妖狐艹你老母 2022-08-27 13:57 179阅读 0赞

快速排序是一种分治排序算法。广泛认为它是解决一般问题的最佳排序算法。同插入排序一样，快速排序也属于比较排序的一种，而且不需要额外的存储空间。在处理中到大型数据集时，快速排序是一个比较好的选择。

由于快速排序是一种分治算法，因此可以用分治法的思想将排序分为三个步骤

1.分：设定一个分割值将数据分为两部分。

2.治：分别在两部分用递归的方式继续使用快速排序法。

3.合：对分割部分排序排序直至完成。

![Center][]

实现代码如下：

import java.util.Random;
    /**
     * 快速排序 {分，治，合}
     * @author kevin LUAN
     *
     */
    public class QuickSort {
    	public static void main(String[] args) {
    		int total = 5;
    		QuickSort quickSort = new QuickSort();
    		while (total > 0) {
    			Integer arr[] = randomArray(1000000);
    			long start = System.currentTimeMillis();
    			quickSort.sort(arr);
    			System.out.println("use time:" + (System.currentTimeMillis() - start));
    			quickSort.check(arr);
    			total--;
    		}
    	}
    
    	public void sort(Integer[] arr) {
    		mergeSort(arr, 0, arr.length - 1);
    	}
    
    	private void mergeSort(Integer arr[], int low, int high) {
    		int a = low;
    		int b = high;
    		int middle;
    		middle = getMiddle(arr, low, high);
    		while (low < high) {
    			while (high > low) {
    				/* 抵位小于中间值 */
    				if (arr[low] <= middle) {
    					low++;
    				} else {
    					// TODO 需要进入高位寻找交换值
    					break;
    				}
    			}
    			while (high > low) {
    				if (arr[high] > middle) {
    					high--;
    				} else {
    					swap(arr, low, high);
    					break;
    				}
    			}
    		}
    		/* 选择的分割值靠近边界 */
    		if (b == high || a == low) {
    			sort(arr, a, b + 1);
    			return;
    		}
    		/**
    		 * 递归【分,治,合】
    		 */
    		if (low - a > 0) {
    			mergeSort(arr, a, low);
    		}
    		if (b - high > 0) {
    			mergeSort(arr, high, b);
    		}
    	}
    
    	private void sort(Integer[] arr, int low, int high) {
    		for (int i = low; i < high; i++)
    			for (int j = i; j > low && ((Comparable) arr[j - 1]).compareTo(arr[j]) > 0; j--)
    				swap(arr, j, j - 1);
    	}
    
    	private void swap(Integer arr[], int a, int b) {
    		Integer av = arr[a];
    		arr[a] = arr[b];
    		arr[b] = av;
    	}
    
    	/**
    	 * 获取中间值
    	 * <p>
    	 * 快速排序算法是否高效主要取决于该值
    	 * </p>
    	 * 
    	 * @param arr
    	 * @param startIndex
    	 * @param endIndex
    	 * @return
    	 */
    	private int getMiddle(Integer arr[], int startIndex, int endIndex) {
    		Random random = new Random();
    		int max = endIndex - startIndex + 1;
    		int n1 = arr[random.nextInt(max) + startIndex];
    		int n2 = arr[random.nextInt(max) + startIndex];
    		int n3 = arr[random.nextInt(max) + startIndex];
    		if (n1 > n2 && n1 > n3) {
    			return getMaxVal(n2, n3);
    		} else if (n2 > n1 && n2 > n3) {
    			return getMaxVal(n1, n3);
    		} else if (n3 > n2 && n3 > n1) {
    			return getMaxVal(n1, n2);
    		} else {
    			if (n1 == n2) {
    				return n3;
    			} else if (n2 == n3) {
    				return n1;
    			} else {
    				/* (n1 == n3) */
    				return n2;
    			}
    		}
    	}
    
    	private int getMaxVal(int n2, int n3) {
    		if (n2 > n3) {
    			return n2;
    		} else {
    			return n3;
    		}
    	}
    
    	/**
    	 * 随机生成测试数值
    	 * <p>
    	 * 使用分治合算法数据越分散性能越高，越密集效率越低
    	 * </p>
    	 * 
    	 * @param total
    	 * @return
    	 */
    	public static Integer[] randomArray(int total) {
    		Random random = new Random();
    		Integer[] arrays = new Integer[total];
    		for (int i = 0; i < total; i++) {
    			if (i % 5 == 0) {
    				arrays[i] = -random.nextInt(10000);
    			} else {
    				arrays[i] = random.nextInt(10000);
    			}
    
    		}
    		return arrays;
    	}
    
    	/**
    	 * 检测排序后的结果是否正确
    	 * 
    	 * @param array
    	 */
    	public void check(Integer array[]) {
    		for (int i = 0; i < array.length - 1; i++) {
    			if (array[i] > array[i + 1]) {
    				throw new RuntimeException("出错了:" + array[i] + "==" + array[i + 1]);
    			}
    		}
    	}
    }

**对100万随机数进行排序运行结果如下（单位毫秒值）：**

use time:249

use time:205

use time:245

use time:220

use time:203

[Center]: /images/20220823/8e251d7fb6bb49b2b1ad088a97d177cc.png