数据结构—八大排序

一、直接插入排序
 
基本思想:我们平时玩扑克牌时,摸牌阶段的排序就用到了插入排序的思想
 
1、当插入第n个元素时,前面的n-1个数已经有序
 
2、用这第n个数与前面的n-1个数比较,找到要插入的位置,将其插入(原来位置上的数不会被覆盖,因为提前保存了)
 
3、原来位置上的数据,依次后移
 
 具体实现:
 
①单趟的实现(将x插入到 [0,end] 的有序区间)
 
即一般情况下的插入,我们随机列举了一些数字,待插入的数字分为两种情况
 
(1)待插入的数字是在前面有序数字的中间数,直接比较将x赋值给end+1位置
 
(2)x是最小的一个数,end就会到达-1的位置,最后直接将x赋值给end+1位置
 
 ②整个数组排序的实现 
 
我们一开始并不知道数组是不是有序的,所以我们控制下标,end从0开始,将end+1位置的值始终保存到x中,循环进行单趟排序即可,最后结束时end=n-2,n-1位置的数字保存到x中
 
 总体代码:
 
void InsertSort(int* a, int n)
 
{
 
assert(a);
 
for (int i = 0; i < n – 1; ++i)
 
{
 
int end = i;
 
int x=a[end+1];//将end后面的值保存到x里面了
 
//将x插入到[0,end]的有序区间
 
while (end >= 0)
 
{
 
if (a[end] > x)
 
{
 
a[end + 1] = a[end];  //往后挪动一位
 
–end;
 
}
 
else
 
{
 
break;
 
}
 
}
 
a[end + 1] = x;      //x放的位置都是end的后一个位置
 
}
 
}
 
直接插入排序总结:
 
①元素越接近有序,直接插入排序的效率越高 
 
②时间复杂度:O(N^2)
 
最坏的情况下,每次插入一个数字,前面的数字都要挪动一下,一共需要挪动1+2+3+……+n=n(n+1)/2 
 
③空间复杂度:O(1)
 
没有借助额外的空间,只用到常数个变量

如需转载,请注明文章出处和来源网址:http://www.divcss5.com/html/h64875.shtml

张贴在3