直接插入排序
排序思想：假設(shè)第i個(gè)記錄前面的順序表有序娇跟，將待排記錄插入到合適位置夸政，并將之后的記錄后移。
void InsertSort(Sqlist &L){
for(int i=2;i<=L.length;i++){
if(LT(L.r[i],L.r[i-1]){
L.r[0]=L.r[i];
for(j=i-1;LT(L.r[0],L.r[j]);j--){
L.r[j]=L.r[j-1];
}
L.r[j]=L.r[0];
}
}
Java實(shí)現(xiàn)：
private void insertSort(int[] array) {
int len=array.length;
for (int i = 0; i < len-1; i++) {
for (int j = i + 1; j >0; j--) {
if (array[j] < array[j - 1]) {
int tmp = array[j - 1];
array[j - 1] = array[j];
array[j] = tmp;
}
}
}
println(array);
}
希爾排序
排序思想：先將整個(gè)待排記錄序列分割成為若干個(gè)子序列分別進(jìn)行直接插入排序脏毯，待整個(gè)序列“基本有序”再對全體進(jìn)行一次直接插入排序疚颊。
void ShellInsert(Sqlist &L,int k){
for(int i=k+1;i<=L.length;i++){
if(LT(L.r[i],L.r[i-1]){
L.r[0]=L.r[i];
for(j=i-k;LT(L.r[0],L.r[j]);j-=k){
L.r[j]=L.r[j-1];
}
L.r[j]=L.r[0];
}
}
void ShellSort(Sqlist &L,int dlta[],int t){
for(int k=0;k<t;k++){
ShellSort(L,dlta[k]);
}//for
}
Java實(shí)現(xiàn)：
private int dlta[] = {4,3,2,1};
private void shellSort(int[] array){
int dl=dlta.length;
for (int i = 0; i < dl; i++) {
shellInner(array,dlta[i]);
println(array);
}
println(array);
}
private void shellInner(int[] array,int step){
int len=array.length;
for (int i = 0; i < len-step; i += step) {
for (int j = i + step; j > 0; j -= step) {
if (array[j] < array[j - step]) {
int tmp=array[j];
array[j]=array[j-step];
array[j-step]=tmp;
}
}
}
}
