Chinaunix首页 | 论坛 | 博客

wyh1791的ChinaUnix博客

首页　| 　博文目录　| 　关于我

wyh1791

  • 博客访问： 164998
  • 博文数量： 56
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 593
  • 用 户 组： 普通用户
  • 注册时间： 2014-02-18 09:59
文章分类

全部博文（56）

文章存档

2019年（1）

2018年（26）

2016年（1）

2015年（6）

2014年（22）

我的朋友
最近访客
推荐博文
相关博文
快速排序

分类： Java

2014-03-23 21:52:51

1. 轴=(left+right)/2


点击(此处)折叠或打开

  1. /**
  2.  * @author:      吴永行
  3.  * @dateTime:     2014-3-23 下午9:23:30
  4.  * @description:     
  5.  *
  6.  */
  7. package 经典算法大全;

  9. import java.util.Random;

  11. public class _38_快速排序法_2 {

  13.     static final int MAX = 10;

  15.     static final void swap(int[] a, int i, int j) {
  16.         int t;
  17.         t = a[i];
  18.         a[i] = a[j];
  19.         a[j] = t;
  20.     }

  22.     public static void main(String[] args) {
  23.         int number[] = new int[MAX + 1];
  24.         int i, num;
  25.         Random random = new Random();
  26.         System.out.format("排序前：");
  27.         for (i = 0; i < MAX; i++) {
  28.             number[i] = Math.abs(random.nextInt()) % 100;
  29.             System.out.format("%d ", number[i]);
  30.         }
  31.         quicksort(number, 0, MAX - 1);
  32.         System.out.format("\n排序后：");
  33.         for (i = 0; i < MAX; i++)
  34.             System.out.format("%d ", number[i]);
  35.         System.out.format("\n");
  36.     }

  38.     /**
  39.      * @author:      吴永行
  40.      * @dateTime:     2014-3-23 下午9:27:21
  41.      * @description:     
  42.      * @param number
  43.      * @param i
  44.      * @param j
  45.      *
  46.      */
  47.     private static void quicksort(int[] number, int left, int right) {
  48.         int i, j, s;
  49.         if (left < right) {
  50.             s = number[(left + right) / 2];
  51.             i = left - 1;
  52.             j = right + 1;
  53.             while (true) {
  54.                 while (number[++i] < s)
  55.                     ; // 向右找
  56.                 while (number[--j] > s)
  57.                     ; // 向左找
  58.                 if (i >= j)
  59.                     break;
  60.                 swap(number, i, j);
  61.             }
  62.             quicksort(number, left, i - 1); // 对左边进行递回
  63.             quicksort(number, j + 1, right); // 对右边进行递回
  64.         }
  65.     }
  66. }

2. 使用分割的方式


点击(此处)折叠或打开

  1. /**
  2.  * @author:      吴永行
  3.  * @dateTime:     2014-3-23 下午9:32:33
  4.  * @description:     
  5.  *
  6.  */
  7. package 经典算法大全;

  9. import java.util.Random;

  11. public class _39_快速排序法_3 {

  13.     /**
  14.      * @author:      吴永行
  15.      * @dateTime:     2014-3-23 下午9:32:33
  16.      * @description:     
  17.      * @param args
  18.      *
  19.      */

  21.     static final int MAX = 10;

  23.     static final void swap(int[] a, int i, int j) {
  24.         int t;
  25.         t = a[i];
  26.         a[i] = a[j];
  27.         a[j] = t;
  28.     }

  30.     public static void main(String[] args) {
  31.         int number[] = new int[MAX + 1];
  32.         int i, num;
  33.         Random random = new Random();
  34.         System.out.format("排序前：");
  35.         for (i = 0; i < MAX; i++) {
  36.             number[i] = Math.abs(random.nextInt()) % 100;
  37.             System.out.format("%d ", number[i]);
  38.         }
  39.         quicksort(number, 0, MAX - 1);
  40.         System.out.format("\n排序后：");
  41.         for (i = 0; i < MAX; i++)
  42.             System.out.format("%d ", number[i]);
  43.         System.out.format("\n");
  44.     }

  46.     /**
  47.      * @author:      吴永行
  48.      * @dateTime:     2014-3-23 下午9:41:21
  49.      * @description:     
  50.      * @param number
  51.      * @param i
  52.      * @param j
  53.      *
  54.      */
  55.     private static void quicksort(int[] number, int left, int right) {
  56.         int q;
  57.         if (left < right) {
  58.             q = partition(number, left, right);
  59.             quicksort(number, left, q - 1);
  60.             quicksort(number, q + 1, right);
  61.         }
  62.     }

  64.     /**
  65.      * @author:      吴永行
  66.      * @dateTime:     2014-3-23 下午9:42:02
  67.      * @description:     
  68.      * @param number
  69.      * @param left
  70.      * @param right
  71.      * @return
  72.      *
  73.      */
  74.     private static int partition(int[] number, int left, int right) {
  75.         int i, j, s;
  76.         s = number[right];
  77.         i = left - 1;
  78.         for (j = left; j < right; j++) {
  79.             if (number[j] <= s) {
  80.                 i++;
  81.                 swap(number, i, j);
  82.             }
  83.         }
  84.         swap(number, i + 1, right);
  85.         return i + 1;
  86.     }

  88. }








阅读(833) | 评论(0) | 转发(0) |
0

上一篇：Clipx Expression: size > 0 解决方法

下一篇：基数排序法

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6