首页 > 代码库 > 希尔排序和快速排序
希尔排序和快速排序
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。
如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。
D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，
每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。
当增量减到1时，整个要排序的数被分成一组，排序完成
public class TestXe {
public static int[] a = { 10, 32, 1, 9, 5, 8, 88, 12, 0, 4, 3, 66 }; // 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); // 选择排序
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
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; // 计算下次分割的间隔长度
}
}
}
--------------------------------------------------------------
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。①以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。 ②把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归）③重复第①、②步，直到左区处理完毕。
public class QuickSort {
/**
* 快速排序，对整数型数组o进行
*/
public static void quiteSort(int[] o, int low, int hight) {
if (low < hight) {
int povitePosition = adjust(o, low, hight);
quiteSort(o, low, povitePosition - 1);
quiteSort(o, povitePosition + 1, hight);
}
}
/**
* 进行调整
*/
private static int adjust(int[] o, int low, int hight) {// 选定枢轴为low所对应的值
int pivote = o[low];
while (low < hight) {
while (hight > low && compare(pivote, o[hight]) <= 0) {// 高位找到比povite大，则符合要求，继续寻找
hight--;
}
o[low] = o[hight];
while (low < hight && compare(pivote, o[low]) >= 0) { // 低位开始找到比povite小，符合要求，继续寻找
low++;
}
o[hight] = o[low];
}
o[low] = pivote;
return low;
}
/**
* @param num1 减数
* @param num2 被减数
*/
private static int compare(int num1, int num2) {
return num1 - num2;
}
public static void main(String[] args) {
int[] i = { 26, 53, 48, 15, 13, 46, 32, 18, 16 };
quiteSort(i, 0, i.length - 1);
for (int ii : i) {
System.out.print(ii + " ");
}
}
}