< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CsnPzbzKx9StyrzK/b7dus212tK7tM7RodTxtcTU9sG/IGQgPSA1oaOxvrTOxcXQ8rXEveG5+8jnz8LNvKO6PC9wPgo8cD4KPGltZyBzcmM9"https://www.cppentry.com/upload_files/article/76/1_bgryl__.gif" alt="\">
上图是第一次排序的结果，本次选择增量为 d=2。 本次排序的结果如下图：
当d=1 是进行最后一次排序，本次排序相当于冒泡排序的某一次循环。最终结果如下：
在实际使用过程中，带排序的数据肯定不是只有十个，但是上述是希尔排序的思想。其实希尔排序只是插入排序的一种优化。
package shellsort;
public class shellsort {
public static void main(String[] args)
{
int[] a = {500,77,66,99,2,7,4,6,100,34};
int[] b;
b = shell(a);
for(int i =0; i
=0) && (array[j]>temp); j-=gap)
{
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
}while( gap > 1 );
return array;
}
}
快速排序 思想：从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴其关键字设为k1，然后将其余关键字小于k1的记录移到前面去，而将关键字大于k1的记录移到后面，结果将待排序序列分成了两个子表最后将关键字为k1的记录查到其分界线的位置处.
算法步骤：假设待划分序列为r[left],r[left+1],.......r[right],具体实现上述划分过程时，可以设两个指针i和j，他们的初值分别为left,right.首先将基准记录r[left]移至变量x中，是r[left]，即r[i]相当于空单元，然后反复进行如下两个扫描过程，直到i和j相遇
（1）j从右向左扫描，直到r[j].key
当i和j相遇时，r[i](或r[j])相当与空单元，且r[i]左边所有记录的关键字均不大于基准记录的关键字，而r[i]右边所有记录的关键字均不小于基准记录的关键字，最后将基准记录移至r[i]中，就完成了一次划分过程。最后对子表进行递归调用排序函数进行排序。
Java示例代码如下：
package quicksort;
public class Quick {
public static void main(String[] args)
{
int[] a = {500,77,66,99,2,7,4,6,100,34,1000,888,777,666,555,333,222,111,87,45,69,12,45,};
QuickSort(a,a.length);
for(int i =0; i
= pv) )
{
high--;
}
swap(array, low, high);
while( (low < high) && (array[low] <= pv) )
{
low++;
}
swap(array, low, high);
}
return low;
}
public static void QSort(int[] array, int low, int high)
{
if( low < high )
{
int pivot = partition(array, low, high);
QSort(array, low, pivot-1);
QSort(array, pivot+1, high);
}
}
public static void QuickSort(int[] array, int len) // O(n*logn)
{
QSort(array, 0, len-1);
}
}
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并操作
归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；
算法描述
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
Java示例代码如下：
package MergeSortClass;
public class MergeSortClass {
private int[] SortOut;
public void printSortedOutput()
{
for (int i = 0; i < this.SortOut.length; i++)
{
System.out.print(this.SortOut[i] + " ");
}
}
public static void main(String[] args)
{
int[] in = { 2, 5, 3, 8, 6, 7, 1, 4, 0, 9 };
MergeSortClass msTest = new MergeSortClass(in);
msTest.printSortedOutput();
}
public MergeSortClass(int[] in)
{
this.SortOut=this.MergeSort(in);
}
private int[] MergeSort(int[] i_list)
{
if (i_list.length == 1) {
return i_list;
} else {
int[] listL = new int[i_list.length / 2];
int[] listR = new int[i_list.length - i_list.length / 2];
int Center = i_list.length / 2;
for (int i = 0; i < Center; i++) {
listL[i] = i_list[i];
}
for (int i = Center, j = 0; i < i_list.length; i++, j++) {
listR[j] = i_list[i];
}
int[] SortedListL=MergeSort(listL);
int[] SortedListR=MergeSort(listR);
int[] o_list = MergeTwoList(SortedListL, SortedListR);
return o_list;
}
}
private int[] MergeTwoList(int[] listL, int[] listR)
{
int i = 0, j = 0;
int[] o_list = new int[listL.length + listR.length];
int foot = 0;
while (i < listL.length && j < listR.length) {
if (listL[i] <= listR[j]) {
o_list[foot] = listL[i];
i++;
} else {
o_list[foot] = listR[j];
j++;
}
foot++;
}
if (i == listL.length) {
while (j < listR.length) {
o_list[foot++] = listR[j++];
}
} else { // j==listR.length
while (i < listL.length) {
o_list[foot++] = listL[i++];
}
}
return o_list;
}
}