A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© yxz 中级黑马   /  2013-9-8 21:58  /  1059 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

快速排序的效率很高,算法也比较经典。
  1. public class Test3 {
  2.         public static void main(String args[]) {
  3.                 int[] lst = getReandArray(20, 100);
  4.                 quickSort(lst, 0, lst.length - 1);
  5.                 prtArray(lst);
  6.         }

  7.         // 获取指定长度的数组,内部填充int型随机数
  8.         public static int[] getReandArray(int lenght, int max) {
  9.                 int[] lst = new int[lenght];
  10.                 for (int i = 0; i < lenght; i++)
  11.                         lst[i] = (int) (Math.random() * max);
  12.                 return lst;
  13.         }

  14.         // 自动输出数组
  15.         public static void prtArray(int[] list) {
  16.                 int i = 0;
  17.                 while (i < list.length) {
  18.                         System.out.print(list[i++] + "\t");
  19.                 }
  20.         }

  21.         // 针对array类型的swap
  22.         public static void swap(int[] lst, int x, int y) {
  23.                 int temp = lst[x];
  24.                 lst[x] = lst[y];
  25.                 lst[y] = temp;
  26.         }

  27.         // 实现快排算法
  28.         public static void quickSort(int[] list, int l, int r) {
  29.                 int i = l + 1, j = r;
  30.                 int key = list[l];

  31.                 if (l >= r)
  32.                         return;
  33.                 while (true) {
  34.                         while (list[j] > key)
  35.                                 j--;
  36.                         while (list[i] < key && i < j)
  37.                                 i++;
  38.                         if (i >= j)
  39.                                 break;
  40.                         swap(list, i, j);
  41.                         if (list[i] == key)
  42.                                 j--;
  43.                         else
  44.                                 i++;
  45.                 }
  46.                 swap(list, l, j);

  47.                 if (l < i - 1)
  48.                         quickSort(list, l, i - 1);
  49.                 if (j + 1 < r)
  50.                         quickSort(list, j + 1, r);
  51.         }
  52. }
复制代码

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马