概述
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序
算法描述
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
- 从数列中挑出一个元素,称为 “基准”(pivot)
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
动图演示
算法实现
Java代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
public class Test { public static void main(String[] args){ int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19}; System.out.println("排序前:"); for (int i : arr) { System.out.print(i+" "); } System.out.println(); quickSort(arr, 0, arr.length-1); System.out.println("排序后:"); for (int i : arr) { System.out.print(i+" "); } } public static void quickSort(int[] arr,int low,int high){ int i,j,temp,t; if(low>high){ return; } i=low; j=high; temp = arr[low]; while (i<j) { while (temp<=arr[j]&&i<j) { j--; } while (temp>=arr[i]&&i<j) { i++; } if (i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } arr[low] = arr[i]; arr[i] = temp; quickSort(arr, low, j-1); quickSort(arr, j+1, high); } }
|
运行结果
PS.
搬运地址: 十大经典排序算法(动图演示) - 一像素 - 博客园 (cnblogs.com)