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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© yangcy 中级黑马   /  2014-7-12 14:35  /  2172 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文


快速排序算法是对冒泡排序算法的一种改进,由于冒泡排序是对相邻的数据进行两两比较,元素的移动次数和比较次数都比较多,所以快速排序采用了从记录序列的两端向中间进行的方式,所以在元素的移动次数和比较次数上都减少了。
基本思想:首先选定一个轴值(也就是比较的基准),将待排序记录分割成独立的两部分,左侧记录的关键码都小于或是等于轴值,右侧的记录关键码都大于或等于轴值,然后再对这两部分分别重复上述的过程,直到整个序列有序为止。
其中,取轴值的问题,可以取首值、中值或尾值,或是大小居中的值,我一般取首值。
代码如下:


  1. import org.junit.Test;

  2. public class QuickSort {
  3.         @Test
  4.         public void test() {
  5.                 int[] arr = { 3, 6, 2, 4, 7, 1 };
  6.                 quickSort(arr, 0, arr.length - 1);
  7.                 for (int i = 0; i < arr.length; i++) {
  8.                         System.out.print(arr[i] + " ");
  9.                 }
  10.         }

  11.         public void quickSort(int[] arr, int first, int end) {
  12.                 if (first < end) {
  13.                         int i = partition(arr, first, end);
  14.                         quickSort(arr, first, i - 1);// 轴值左侧进行递归划分
  15.                         quickSort(arr, i + 1, end);// 轴值右侧进行递归划分
  16.                 }
  17.         }

  18.         // 一次划分
  19.         public int partition(int[] arr, int first, int end) {
  20.                 int i, j;
  21.                 i = first;// 取first为轴值
  22.                 j = end;
  23.                 while (i < j) {
  24.                         // 在轴值的右侧扫描
  25.                         while (i < j && arr[j] >= arr[i]) {
  26.                                 j--;
  27.                         }
  28.                         // 如果扫描到比轴值小的,则将两者调换位置
  29.                         if (i < j) {
  30.                                 swap(arr, i, j);
  31.                         }
  32.                         // 在轴值的左侧扫描
  33.                         while (i < j && arr[i] < arr[j]) {
  34.                                 i++;
  35.                         }
  36.                         // 如果扫描到比轴值大的,则将两者调换位置
  37.                         if (i < j) {
  38.                                 swap(arr, i, j);
  39.                         }
  40.                 }
  41.                 return i;// 返回轴值的下标
  42.         }

  43.         private void swap(int[] arr, int i, int j) {
  44.                 int temp = arr[i];
  45.                 arr[i] = arr[j];
  46.                 arr[j] = temp;
  47.         }
  48. }
复制代码


评分

参与人数 1技术分 +1 收起 理由
HM汪磊 + 1 赞一个!

查看全部评分

1 个回复

倒序浏览
NB啊 ,这个方法确实很好。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马