快速排序的原理其实很简单。
首先有一串数组
然后我们在数组内选一个数记为x,可以是第一个,最后一个,哪个都行,然后记录下来,就以取到最后一个元素为例吧。
(em,本来应该是随机取的,但是随机取的话,代码设计就有点麻烦,会碰到诸如角标越界,死循环之类的问题,这里就不做过多分析,有兴趣的小伙伴可以试试。)
然后呢,这个数组以x为界限分为前后两部分
然后对这前后两个部分的元素分别给指针进行遍历,注意一下遍历的方向,两个指针都往中间(也就是x)那边靠。
然后给个循环,让这两个部分每个元素同时与x进行大小比较,以从小到大排序为例的话,就是:
如果前面部分的遍历到的元素比x大,指针i就暂时停下来
后面部分如果遍历到比x小的,指针j也暂时停下来
然后比较两个指针的位置,
如果指针i在指针j的前面的话就交换两个指针指向的元素,然后两个指针继续刚才的比较操作
如果指针i在指针j的后面的话就停止整个遍历。
如此,就能保证在x左边的元素都比x小,在x的右边的元素都比x大。
然后不断递归上面的操作就行了。
附上代码如下:
package com.zero.workTest; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import static java.lang.System.exit; public class HomeWork { public static void main(String[] args) throws IOException { //这边使用的是流的形式输入,要是觉得麻烦的小伙伴可以选择用Scanner,这里就不展示了 BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); //这边比较懒,没有管非法输入的,毕竟只是为了实现算法,就直接转换过来了,下面也是,不在重复说明 int n = Integer.valueOf(bufferedReader.readLine()); String[] arr = bufferedReader.readLine().split(" "); if (n!=arr.length){ System.out.println("输入错误"); exit(0); } int[] arr2 = new int[n]; for (int i = 0;i<n;i++){ arr2[i] = Integer.valueOf(arr[i]); } fast_sort(arr2, 0, n-1); for (int i = 0;i<n;i++){ System.out.print(arr2[i]+" "); } } //快排实现 private static void fast_sort(int[] arr2, int l, int r) { if (l>=r) return; //注意这里要取等,如果不去等下面会死循环 int x = arr2[r]; int i = l-1; int j = r+1; while(i<j) { do { i++; } while (arr2[i] < x);//注意这里不能取到等,如果去等会越界 do { j--; } while (arr2[j] > x);//注意这里不能取到等,如果去等会越界 if (i<j) swap(arr2,i,j); } fast_sort(arr2,l,i-1); fast_sort(arr2,i,r); } private static void swap(int[] arr2, int i, int j) { int emp = arr2[i]; arr2[i] = arr2[j]; arr2[j] = emp; } }