直接插入排序
思想
插入排序(Insertion Sort)类似整理桥牌的过程:将右手拿到的牌(未排序)在左手已排序的牌中从后向前扫描,找出对应位置并且插入此牌。
在此过程中,要将已经排序的元素逐步向后挪,给待插入元素腾出空间。
实现
#include <stdio.h>
#define MAXSIZE 100
typedef struct
{
int a[MAXSIZE + 1]; //a[1]~a[MAXSIZE]存储元素
int length;
}Sqlist;
/*升序排列*/
void Insertion_Sort(Sqlist* L)
{
for (int i = 2; i <= L->length; i++)
{
int get = L->a[i];
int j = i - 1;
while (j > 0 && get < L->a[j])
{
L->a[j + 1] = L->a[j];
j--;
}
L->a[j + 1] = get;
}
}
int main(int argc, char** argv)
{
Sqlist L;
scanf("%d", &(L.length));
for (int i = 1; i <= L.length; i++)
scanf("%d", &(L.a[i]));
Insertion_Sort(&L);
for (int i = 1; i <= L.length; i++)
printf("%d ", L.a[i]);
printf("
");
return 0;
}
复杂度
最好情况:元素全部有序,(N-1)次比较、(0)次交换;复杂度(O(n))。
最坏情况:元素全部逆序,大约(frac{N^2}{2})次比较和(frac{N^2}{2})次交换,复杂度(O(n^2))。
平均情况下:大约(frac{N^2}{4})次比较和(frac{N^2}{4})次交换,复杂度(O(n^2))。
折半插入排序
直接插入排序前面的子序列是有序的,所以如果是顺序表,那么可以先折半查找出元素的待插入位置,再统一移动该位置之后的所有元素:
void insertionSortOptimized(int A[], int n)
{
//将A[i]插入到合适位置
for (int i = 1; i < n; i++)
{
int tmp = A[i];
int low = 0, high = i - 1;
while (low <= high)
{
int mid = (low + high) >> 1;
if (A[mid] > tmp)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
//统一后移元素
for (int j = i - 1; j >= low; j--)
{
A[j + 1] = A[j];
}
A[low] = tmp;
}
}
性能:折半插入排序将元素比较次数减少为(O(nlogn)),但是移动次数依然是(O(n^2)),故总的时间复杂度为(O(n^2))。
希尔排序
基本思想:将待排序表分为若干(A[i], A[i+d], A[i+2d]...)子表,(d)称为增量,对这些子表执行直接插入排序,当整个表中的元素“基本有序”时,对整个表来一次直接插入排序。
由于需要快速定位某个子表中的元素,所以只能用于顺序表。
void shellSort(vector<int>& nums) {
const int n = nums.size();
for (int d = n >> 1; d > 0; d >>= 1) // 增量选之前的一半
for (int i = d; i < n; ++i) // 将nums[i]插入有序子表
if (nums[i] < nums[i - d]) {
int tmp = nums[i];
int j;
// 查找插入位置
for (j = i - d; j >= 0 && tmp < nums[j]; j -= d)
nums[j + d] = nums[j]; // 后移
nums[j + d] = tmp;
}
}
性能:时间复杂度依赖于选取的增量序列,大约是(O(n^{1.3})),最坏是(O(n^2))。