本帖最后由 乐宝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+"]");
}
}
}
|