黑马程序员技术交流社区

标题: 快速排序算法 [打印本页]
作者: straw    时间: 2013-7-15 07:45
标题: 快速排序算法
本帖最后由 straw 于 2013-7-15 11:46 编辑

* 快熟排序
1  快速排序  取中间作为断点 将左边比中间大的放到右边去
2  将右边比中间小的放到左边来
3  一次排序后记住原中间取值的位置作为新断点  分别递归走遍和右边的重新排序
谁有写过这个算法的?麻烦贴出来下啊...
作者: 周之浩    时间: 2013-7-15 08:27
这是我写的一个快速排序的算法，如果不明白时，可以给我发邮件1553026118@qq.com
  1. package com.itheima;

  3. import java.util.Arrays;

  5. /**
  6. * 排序方法主要有：快速排序，冒泡排序，插入排序（直接，折半，二路），选择排序
  7. * 本例实现快速排序
  8. * @author Administrator
  9. *
  10. */
  11. public class Test2 {
  12.     public static void main(String[] args) {
  13.             int arr[] ={51,32,62,96,87,17,28};//定义数组
  14.         new Test2().quickSort(arr, 0,arr.length-1);
  15.         System.out.println(Arrays.toString(arr));
  16.         }
  17.    
  18.     /**
  19.      * 实现数组内两个数值交换
  20.      * @param a对应的数组
  21.      * @param i数组的下标
  22.      * @param j数组的下标
  23.      */
  24.     public void change(int a[], int i, int j)
  25.     {
  26.             if(i==j)
  27.             {
  28.                     return;
  29.             }
  30.             int tmp = a[i];//实现交换
  31.             a[i] =a[j];
  32.             a[j] = tmp;
  33.     }
  34.    
  35.     /**
  36.      *
  37.      * @param arr 带排序的数组
  38.      * @param low
  39.      * @param height
  40.      * @return i
  41.      */
  42.     public int partition(int arr[],int low,int height)
  43.     {
  44.               //当前位置为第一个元素所在位置
  45.         int p_pos = low;
  46.         //采用第一个元素为轴
  47.         int pivot = arr[p_pos];
  48.          
  49.         for (int i = low + 1; i <= height; i++) {

  51.             if (arr[i] < pivot) {            
  52.                
  53.                 p_pos++;

  55.                 change(arr, p_pos, i);  

  57.             }

  59.         }

  61.         change(arr, low, p_pos);

  63.         return p_pos;

  65.     }
  66.     /**
  67.      * 实现快速排序
  68.      * @param arr
  69.      * @param low
  70.      * @param high
  71.      */
  72.     public void quickSort(int arr[], int low, int high)
  73.     {
  74.             if(low < high)
  75.             {
  76.                     int pivot = partition(arr, low, high);
  77.                     //System.out.println(pivot);
  78.                     quickSort(arr, low, pivot-1);
  79.                     quickSort(arr, pivot+1, high);
  80.             }
  81.     }
  82.    
  83. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2