快速排序顺利用递归原理,把数组无限制的分成两部分,直到所有数据都排好序为止。
分析:快速排序的基本思想是通过一趟排序将要排序的数据分割成两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后按此方法对这两部分数据分别
进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
步骤:
如果要排序的数组是A[0].........A[N-1],首先任意选取一个数据(通常选用第一个数据)作为中间数据,然后将所有比他小的数都放到它前面,所有比他大的数据都放到它
后面,这个过程称为一趟快速排序。一趟快速排序的算法如下:
(1)设置两个变量i,j,排序开始的时候:i=1,j=N-1.
(2)以第一个数组元素作为中间数据,赋值给pivot,即pivot=A[0]。
(3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于X的值。
(4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于X的值,并与上一步找到的数字交换。
(5)重复3,4步,直到i>=j。
(6)然后把j所在的数字与pivot交换。
(7)最后把j以前的数组和j到最后的数组,在进行递归的快速排序。- public class Sort {
- /**
- * 快速排序
- */
- public static void main(String[] args) {
- int arr[] = {4,12,5,1,97,16,3,7};
- quickSort(arr,0,arr.length-1);
- printArr(arr);
- }
- //用递归让整个数组序列化
- private static void quickSort(int[] arr, int begin, int end) {
- if(begin>end){
- return ;
- }
- int i = onceSort(arr,begin,end);
- quickSort(arr,begin,i-1);
- quickSort(arr,i+1,end);
- }
- //打印数组
- private static void printArr(int[] arr) {
- for(int i : arr){
- System.out.print(i+"\t");
- }
-
- }
- //一趟快速排序,并返回用于下次分组的中间值i
- public static int onceSort(int[]arr,int begin,int end){
- int i = begin;
- int j = end;
- int key = arr[i];
-
- while(j>i){
- while(arr[j]>key&&j>i){
- j--;
- }
- if(j>i){
- arr[i] = arr[j];
- arr[j] = key;
- }
- while(arr[i]<key&&j>i){
- i++;
- }
- if(j>i){
- arr[j] = arr[i];
- arr[i] = key;
- }
- }
-
- return i;
- }
- }
复制代码 |