黑马程序员技术交流社区

标题: 排序问题。 [打印本页]
作者: 杨习平    时间: 2012-8-19 00:53
标题: 排序问题。
排序都有哪几种方法？请列举。用JAVA实现一个快速排序。自己不懂快速是怎么样的一种思路和运行流程。高手救助，急。。
作者: 马林康    时间: 2012-8-19 00:57
本帖最后由 马林康 于 2012-8-19 01:00 编辑

常用排序算法
http://www.cnblogs.com/wangfupeng1988/archive/2011/12/26/2302216.html
快速排序采用了分治法的思路~自己百度慢慢理解吧 呵呵
作者: 高正新    时间: 2012-8-19 10:44
快速排序，用到的思想是递归。
先随机选取一个元素（一般选第一个元素），作为中间元素。
然后开始、结尾的元素分别和中间元素比较，小的排前面，大的排后面。直到元素比较完。
这样一来，元素就分为前半部分和后半部分。
再用同样的方法，分别对前半部分、后半部分进行比较，即选取中间值，再和头尾的元素进行比较。
。。。
就这样，不断的比下去，直至头尾都比较完。
作者: 王宝龙    时间: 2012-8-19 13:00
排序主要有
插入排序
希尔排序
选择排序
堆排序
冒泡排序
归并排序
快速排序
你可以找一本数据结构看一看。
1、设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中取a【low】作为标准，调整数组a中的各个元素位置，使排在标准元素前面元素的关键字均小于标准元素的关键字，排在标准元素后面元素关键字均大于或者等于标准元素的关键字。这样一个过程结束后，一方面将标准元素放在未排好序的数组中该标准元素该在的位置，另一方面将数组中的元素以标准元素为中心分成了两个数组，位于标准元素左边子数组中元素的关键字均小于标准元素的关键字，位于标准元素右边子数组中元素的关键字均大于或者等于标准元素关键字。对于这两个子数组中的元素分别在进行方法类同的递归快速排序。递归算法的结束条件是high<=low，即上界小于或者等于下界下标。
举例如下：
  1. class Quick//定义一个排序类
  2. {
  3.         public static void Sort(int[] a,int low,int high)
  4.         {
  5.                 int i = low;
  6.                 int j = high;
  7.                 int temp=a[low];//取第一个元素为标准数据元素
  8.                
  9.                 while(i<j)
  10.                 {
  11.                         while(i<j&&temp<=a[j])//在数组右端扫描
  12.                                 j--;
  13.                         if(i<j)
  14.                         {
  15.                                 a[i]=a[j];
  16.                                 i++;
  17.                         }
  18.                         while(i<j&&a[i]<temp)//在数组左端扫描
  19.                                 i++;
  20.                         if(i<j)
  21.                         {
  22.                                 a[j]=a[i];
  23.                                 j--;
  24.                         }
  25.                        
  26.                 }
  27.                 a[i]=temp;
  28.                
  29.                 if(low<i)Sort(a,low,i-1);
  30.                 if(i<high)Sort(a,j+1,high);
  31.         }
  32. }
  33. public class Test3
  34. {
  35.         public static void main(String[] arge)
  36.         {
  37.                 int i;
  38.                 int [] a = {8,5,3,4,7,9,0,1,2,6};//定义一个数组
  39.                 for(i=0;i<a.length;i++)
  40.                 {
  41.                                 System.out.printf("%3d",a[i]);//输出数组
  42.                        
  43.                 }
  44.                 System.out.println();
  45.                 Quick.Sort(a,0,9);//调用排序类的方法
  46.                 for(i=0;i<a.length;i++)
  47.                 {
  48.                                 System.out.printf("%3d",a[i]);//输出排完序的数组
  49.                        
  50.                 }
  51.                 System.out.println();
  52.                
  53.         }
  54.        
  55. }
复制代码




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