本帖最后由 乐宝myhoney 于 2014-2-5 21:38 编辑
1.快速排序的基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两 部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
2.效率最高的排序是希尔排序，其基本思想是：先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。3.希尔排序的具体实现：
public class Demo {
public static void main(String[] args) {
ShellSort shellSort = new ShellSort() ;
System.out.println("希尔排序已经完成");
}
}
/*
* 希尔排序的实现
*/
class ShellSort {
//shellSort构造函数
public ShellSort() {
//定义一个整型数组，里面有十个整数
int arr[] = { 1, 26, 9, 66, 77, 274, 123, 82, 13, 58 };
/* 定义一个双精度型的变量d1，用来存放数组的长度，为什么是双精度型的呢，因为后面我要用这个d1，这个d1是在不断地变化，
* 而且是在不断的变化，第一次是这个数组的长度除以2娶向上的整数。然后以此类推，每次都是除以2。其实这个d1就是前面所提
* 到的增量。数组根据这个增量分成好几个组。
*/
double d1 = arr.length;
//定一个整型的临时变量，用来存放两个数中临时比较的数。
int temp = 0;
while (true) {
//定义一个增量，增量向上取整，而且这个增量每次都在变化。这个就是上面的d1，这就是为什么d1必须要取double的原因。
d1 = Math.ceil(d1 / 2);
// 然后把这个d1强制转换成int类型。用于底下的和整型的数相加，否则会出现类型转换不一致问题。
int d = (int) d1;
//这一层循环是把当前这个增量里面的每一组数据比较一边
for (int x = 0; x < d; x++) {
//这一层循环式比较已经确定了的那几个数 ，比如以d等于2，那么这里比较的数据就是第一个和第三个还有第五个，一次类推
for (int i = x + d; i < arr.length; i += d) {
//让j等于每一组里面的第一个数
int j = i - d;
//当前要比较的数的后面一个数放到临时变量里面
temp = arr[j];
//比较当前的数和后面的数
for (; j >= 0 && temp < arr[j]; j -= d) {
//如果后面的数小于前面的数，则把它们交换
arr[j + d] = arr[j];
}
arr[j + d] = temp;
}
}
if (d == 1)//如果最后增量变为1就结束了，因为1就是只有相邻的两个比，这两个都已经是排好序的了，所以就不用比了，说明排序好了
break;
}
//打印出这个已经排好序的数组。
System.out.print(“[”);
for (int i = 0; i < arr.length; i++)
{
if(i!=arr.length-1)
System.out.print(arr+",");
else
System.out.println(arr+"]");
}
}
}
| 
收藏
淘帖
踩
