- public class Test1 {
- /**
- * @param args
- */
- public static void main(String[] args)
- {
- int [] arr ={10,45,31,56,78,120,120,86};
- print(arr);
- quickSort(arr,0,arr.length-1);
- print(arr);
-
- }
- /**
- *
- * @param arr
- * @param l
- * @param r
- * 快速排序
- */
- public static void quickSort(int [] arr,int l, int r)
- {
- //分治法
- if(l<r)
- {
- //获得第一次分成两段的位置
- int pos = getPos(arr,l,r);
-
- //对分成的两段分别递归调用
- quickSort(arr,l,pos-1);
- quickSort(arr,pos+1,r);
- }
- }
- /**
- *
- * 获取数组第一个元素在排好序好的数组中的位置,并将该元素放在该位置上
- */
- public static int getPos(int[] arr,int l, int r)
- {
- int key = arr[l];
- while(l<r)
- {
- //从后向前找到第一个小于key的元素。
- while(l<r && arr[r]>=key)
- r--;
- swap(arr,l,r);
-
- //交换位置换,从前向后找到第一个大于key的元素。
- while(l<r&& arr[l]<key)
- l++;
- swap(arr,l,r);
- }
- //循环结束后,r=l;
- return r;
- }
- /**
- * 数组元素位置交换
- */
- public static void swap(int [] arr,int x,int y)
- {
- int temp = arr[x];
- arr[x] = arr[y];
- arr[y] = temp;
- }
- /**
- *数组打印方法
- */
- public static void print(int [] arr)
- {
- for(int x:arr)
- {
- System.out.print(x+" ");
- }
- System.out.println();
- }
-
- }
复制代码 我先贴个快速排序的 |