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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© q757571446 中级黑马   /  2015-6-15 23:13  /  596 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

基础视频中学的数组排序是选择排序和冒泡排序,其实这两种算法的效率相对比较低下。在考虑最坏情况下,每次都需要遍历整个数组才能够确定一个最大值。而快速排序算法是直接取数组中的中间值,将比这个中间值大的放在中间值右边,比这个中间值小的放在左边。将一个数组分成两个部分,然后反复执行以上动作。例如:
通过反复递归就可以将一个数组排序正常
  1.         public static void quickSort(int sortarray[], int lowIndex, int highIndex) {
  2.                 int lo = lowIndex;// 记录最小索引
  3.                 int hi = highIndex;// 记录最大索引
  4.                 int mid;// 记录分界点元素
  5.                 if (highIndex > lowIndex) {
  6.                         mid = sortarray[(lowIndex + highIndex) / 2];// 确定中间分界点元素值
  7.                         while (lo <= hi) {
  8.                                 while ((lo < highIndex) && (sortarray[lo] < mid))
  9.                                         ++lo;// 确定不大于分界元素值的最小索引
  10.                                 while ((hi > lowIndex) && (sortarray[hi] > mid))
  11.                                         --hi;// 确定大于分界元素值的最大索引
  12.                                 if (lo <= hi) {// 如果最小与最大索引没有重叠
  13.                                         swap(sortarray, lo, hi);// 交换两个索引的元素
  14.                                         ++lo;// 递增最小索引
  15.                                         --hi;// 递减最大索引
  16.                                 }
  17.                         }
  18.                         if (lowIndex < hi)// 递归排序没有未分解元素
  19.                                 quickSort(sortarray, lowIndex, hi);
  20.                         if (lo < highIndex)// 递归排序没有未分解元素
  21.                                 quickSort(sortarray, lo, highIndex);
  22.                 }
  23.         }
  24.         public static void swap(int[] arr,int index_1,int index_2)
  25.         {
  26.                 int temp=arr[index_1];
  27.                 arr[index_1]=arr[index_2];
  28.                 arr[index_2]=temp;
  29.         }
复制代码


0 个回复

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