Java趣味编程：快速排序法

当前位置：首页 > Java

Java趣味编程：快速排序法

分类:Java 来源:网络时间:2010-09-14 23:42:57

　　快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数(以它为基准点吧) 的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

　　java

　　1 void quickSort(int[] arr, int left, int right){
　　2 int p = partition(arr, left, right);
　　3 quickSort(arr, left, p-1);
　　4 quickSort(arr, p+1, right);
　　5 }
　　6 //1:
　　7 int partition(int[] arr, int left, int right){
　　8 int p = left/2 + right/2;
　　9 while(left < right){
　　10 while(left < p && arr[left] <= arr[p]){
　　11 left++;
　　12 }
　　13 while(right > p && arr[right] >= arr[p]){
　　14 right--;
　　15 }
　　16 swap(arr[left], arr[right]);
　　17 }
　　18 return p;
　　19 }
　　20
　　21 /*2: compare首先从high位置向前搜索找到第一个小于compare值的索引，并置换(这时high索引位置上的值为compare值);然后从 low位置往后搜索找到第一个大于compare值的索引，并与high索引上的值置换(这时low索引位置上的值为compare值);重复这两步直到 low=high为止。*/
　　22 int partition(int[] arr, int left, int right){
　　23 compare = a[left];
　　24 while(left < right){
　　25 while(left=compare){
　　26 right--;
　　27 }
　　28 swap(arr[left], arr[right]);
　　29
　　30 while(left
　　31 left++;
　　32 }
　　33 swap(arr[left], arr[right]);
　　34 }
　　35 return left;
　　36 }

加入收藏 | 浏览(5793)

上一篇：Java游戏开发现状分析和走向
下一篇：实习欢迎你——2009暑假实习

iLeichun

Java趣味编程：快速排序法