业精于勤荒于嬉
插入排序包括:直接插入排序、折半插入排序、希尔排序(缩小增量排序)
一、直接插入排序
1. 算法思想
直接插入排序2. 算法实现
void insertSort(int R[], int n){
int j;
int temp;
for(int i = 1; i < n; ++i){
// i 标示带排序关键字下标,从第二个开始排,因为第一个默认有序
temp = R[i]; // 将当前待插入关键字暂存下来
j = i - 1; // j 默认是当前待插入关键字前面的关键字
while(j >= 0 && temp < R[j]){
R[j+1] = R[j];
--j;
} // 寻找待插入关键字的插入位置,如果j和j之前的关键字比待插入关键字,则依次向后移动
// 将当前待插入关键字放入找到的位置,最后依次while循环使得j多减了1,
// 所以待插入位置下标应该是 j+1
R[j+1] = temp;
}
}
二、折半插入排序
折半插入排序是对直接插入排序的一个优化,在排序过程的不断进行中,已排好序的元素会依次增多,后续的待元素在已排好序的序列中寻找其插入位置时,可通过折半查找减少比较次数(移动次数没有发生变化)。
1. 算法思想
算法思想同直接插入排序,折半插入排序比较次数与初始状态无关:O(nlog2n);直接插入排序比较次数与初态有关:O(n)~O(n2)
2. 算法实现
void binaryInsertSort(int R[], int n){
int i, j, k;
int temp;
int low, high;
for(i = 1; i < n; i++){
// i 标识待排序关键字下标,从第二个开始排,因为第一个默认有序
temp = R[i];
low = 0;
high = i - 1;
// 折半查找待插入的位置
while(low <= high){
k = (low+high)/2;
if(R[k] > R[i]){
high = k - 1;
}else {
low = k + 1;
}
}
//将k到i位置的元素依次后移
for(j = i; j > k + 1; j--){
R[j] = R[j-1];
}
R[k+1] = temp;
}
}
三、希尔排序
又叫缩小增量排序,希尔提出的(还有其他人提出的,思想相同)增量默认选取为序列长度n的一半⌊n/2⌋,再依次缩小增量为⌊n/4⌋...⌊n/2k⌋...,2,1,算法时间复杂度为O(n2)。当增量选取为1时,就是直接插入排序。
1. 算法思想
希尔排序2. 算法实现
void shellSort(int R[], int n)
{
int i, j, temp;
int k = n / 2;
while (k >= 1) {
for (i = k; i < n; i++) {
temp = R[i];
j = i - k;
while (R[j] < temp && j >= 0) {
R[j+k] = R[j];
j = j - k;
}
R[j+k] = temp;
}
k = k / 2;
}
网友评论