iLeichun

当前位置: 首页 > 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 }

 

更多