黑马程序员技术交流社区

标题: 关于快速排序 [打印本页]

---

作者: 张卫刚    时间: 2013-3-3 22:35
标题: 关于快速排序


      我对用java写快速排序有点迷茫？请各位大大给点建意？最好详细点,如果要写真的快速度排序我现在还没把握写出来，所以对此题不知道以什么样的方式作答。

---

作者: 王智威    时间: 2013-3-3 22:59
我估计你在做基础测试题吧。
其实你看看数据结构的书说的拿些，冒泡啊，选择什么都统称快速排序。
我这里有个真正的快排程序。理论我就不说了，你应该有书看。你可以看看
class Demo  {
   public int getMiddle(Integer[] list, int low, int high) {  
          int tmp = list[low];    //数组的第一个作为中轴  
          while (low < high) {  
              while (low < high && list[high] > tmp) {  
                  high--;  
              }  
              list[low] = list[high];   //比中轴小的记录移到低端  
              while (low < high && list[low] < tmp) {  
                  low++;  
              }  
              list[high] = list[low];   //比中轴大的记录移到高端  
          }  
          list[low] = tmp;              //中轴记录到尾  
          return low;                   //返回中轴的位置  
      }
   
   public void _quickSort(Integer[] list, int low, int high) {  
          if (low < high) {  
              int middle = getMiddle(list, low, high);  //将list数组进行一分为二  
              _quickSort(list, low, middle - 1);        //对低字表进行递归排序  
              _quickSort(list, middle + 1, high);       //对高字表进行递归排序  
          }  
      }  
   public void quick(Integer[] str) {  
          if (str.length > 0) {    //查看数组是否为空  
              _quickSort(str, 0, str.length - 1);  
   }  
}
   public static void main(String[] args) {   
           Integer[] list={34,3,53,2,23,7,14,10};  
           Demo qs=new Demo();  
           qs.quick(list);  
           for(int i=0;i<list.length;i++){  
               System.out.print(list+" ");  
           }  
           System.out.println();  
      }
  }

---

作者: 明锦添    时间: 2013-3-4 22:13
package cn.itcast.sort;

import java.util.Arrays;

public class MaoPaoTest {

/**
  * 常用算法代码
  */
public static void main(String[] args) {
  int a[] = { 1, 0, 23, 43, 2, 1, 43, 54, 23, 654, 2, 5 };

  // 采用冒泡法
  // sortByMaoPao(a);
  // System.out.println("排序后的数组为：");
  // for(int x=0;x<a.length;x++){
  // System.out.print(a[x]+"  ");
  // }

  // 选择法排序
  // selectSort(a);
  // System.out.println("排序后的数组为：");
  // for (int x = 0; x < a.length; x++) {
  // System.out.print(a[x] + "  ");
  // }

  // 直接用数组排序
  // Arrays.sort(a);
  // System.out.println("排序后的数组为：");
  // for (int x = 0; x < a.length; x++) {
  // System.out.print(a[x] + "  ");
  // }
  
  
  //插入排序
  insertSort(a);
  for(int i:a){
   System.out.print(i+"  ");
  }
}

private static void insertSort(int[] a) {
  int temp=0;
        for(int i=0;i<a.length;i++){
         for(int j=i;j>0;j--){
          if (a[j] < a[j-1]) {
     temp = a[j];
     a[j] = a[j-1];
     a[j-1] = temp;
    }
         }
        }
}

private static void selectSort(int[] a) {
  int temp = 0;
  for (int i = 0; i < a.length; i++) {
   int lowindex = i;
   for (int j = a.length - 1; j >= i; j--) {
    if (a[j] < a[lowindex]) {
     temp = a[j];
     a[j] = a[lowindex];
     a[lowindex] = temp;
    }
   }
  }
}

private static void sortByMaoPao(int[] a) {
  int temp = 0;
  for (int i = 0; i < a.length; i++) {
   for (int j = 0; j < a.length - i - 1; j++) {
    if (a[j] > a[j + 1]) {
     temp = a[j];
     a[j] = a[j + 1];
     a[j + 1] = temp;
    }
   }
  }
}

}
注：上面测试通过

---

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

黑马程序员IT技术论坛 X3.2