黑马程序员技术交流社区

标题: 关于排序算法的问题 [打印本页]

作者: 吴兆焕 时间: 2012-5-17 13:42
标题: 关于排序算法的问题
我在百度百科看了一下，上面列出20多种排序算法。
除了比较简单的插入排序冒泡排序选择排序

我这里研究了三个算法归并排序快速排序希尔排序

关于希尔排序算法代码如下：

public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度

while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}

我想请教一下大家学习算法的技巧，还有就是能否提供比较好的归并排序快速排序希尔排序的代码，谢谢。

作者: 李文富 时间: 2012-5-17 14:41
嗯。有同感，算法我学的是c语言的，如果死记代码是行不通的，今天你记住了明天你可能就模糊了，但是我认为主要还是知道算法的效率，和选用的情形，选择合适的算法才是重要的。算法要求多练，抓住思想，多多练习，一定能熟练的。

作者: 王章亚 时间: 2012-5-17 14:52
这是java里面的快速排序
　设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
　　一趟快速排序的算法是：
　　1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
　　2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
　　3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J--），找到第一个小于key的值A[j]，A[j]与A[i]交换；
　　4）从I开始向后搜索，即由前开始向后搜索（I=I+1即I++），找到第一个大于key的A[i]，A[i]与A[j]交换；
　　5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。）
　　示例：待排序的数组A的值分别是：（初始关键数据：key=49）注意关键key永远不变，永远是和key进行比较，无论在什么位子，最后的目的就是把key放在中间，小的放前面大的放后面。
　　
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
49 38 65 97 76 13 27
　进行第一次交换后：27 38 65 97 76 13 49
　　( 按照算法的第三步从后面开始找）
　　进行第二次交换后：27 38 49 97 76 13 65
　　( 按照算法的第四步从前面开始找>key的值，65>49,两者交换，此时：I=3 )
　　进行第三次交换后：27 38 13 97 76 49 65
　　( 按照算法的第五步将又一次执行算法的第三步从后开始找
　　进行第四次交换后：27 38 13 49 76 97 65
　　( 按照算法的第四步从前面开始找大于key的值，97>49，两者交换，此时：I=4,J=6 )
　　此时再执行第三步的时候就发现I=J=5，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。

public class QuickSort {
　　public static void sort(Comparable[] data,int low,int high) {
　　// 枢纽元，一般以第一个元素为基准进行划分
　　int i = low;
　　int j = high;
　　if (low < high) {
　　// 从数组两端交替地向中间扫描
　　Comparable pivotKey = data[low];
　　// 进行扫描的指针i,j;i从左边开始，j从右边开始
　　while (i < j) {
　　while (i < j && data[j].compareTo(pivotKey) > 0) {
　　j--;
　　}// end while
　　if (i < j) {
　　// 比枢纽元素小的移动到左边
　　data[i] = data[j];
　　i++;
　　}// end if
　　while (i < j && data[i].compareTo(pivotKey) < 0) {
　　i++;
　　}// end while
　　if (i < j) {
　　// 比枢纽元素大的移动到右边
　　data[j] = data[i];
　　j--;
　　}// end if
　　}// end while
　　// 枢纽元素移动到正确位置
　　data[i] = pivotKey;
　　// 前半个子表递归排序
　　sort(data,low,i - 1);
　　// 后半个子表递归排序
　　sort(data,i + 1,high);
　　}// end if
　　}// end sort
　　public static void main(String[] args) {
　　// 在JDK1.5版本以上，基本数据类型可以自动装箱
　　// int,double等基本类型的包装类已实现了Comparable接口
　　Comparable[] c = { 4,9,23,1,45,27,5,2 };
　　sort(c,0,c.length - 1);
　　for (Comparable data : c) {
　　System.out.println(data);
　　}
　　}
　　}

作者: 吴兆焕 时间: 2012-5-17 14:53

李文富发表于 2012-5-17 14:41
嗯。有同感，算法我学的是c语言的，如果死记代码是行不通的，今天你记住了明天你可能就模糊了，但是我认为 ...

谢谢，有java排序代码吗？

作者: 吴兆焕 时间: 2012-5-17 14:57

王章亚发表于 2012-5-17 14:52
这是java里面的快速排序
　设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据） ...

谢谢，我先看看代码。

作者: 李文富 时间: 2012-5-17 15:02

吴兆焕发表于 2012-5-17 14:53
谢谢，有java排序代码吗？

嗯，java的排序代码我没有，c 排序的的在李春葆《数据结构》这本书有。我在学校学的这本。

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

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