插入排序

把当前遍历到的元素前的元素序列是排好序的,把当前元素放到前边的序列中进行排序。

直接插入排序

不带哨兵

void InsertSort(int A[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
if(A[i]<A[i-1])
{
temp=A[i];
for(j=i-1;j>=0 && A[j]>temp;--j)
A[j+1]=A[j];
A[j+1]=temp;
}
}

带哨兵

数组第一个元素为哨兵记录当前要排序的元素也充当了temp的作用

折半插入排序

有个疑问带哨兵变量的直接插入排序循环中为什么不需要判断j>0

希尔排序

• for(i=d+1;i<=n,++i)第一趟遍历指向第一个子表中的第二个元素A[d+1]
• 按照直接插入排序的规则比较当前指向的元素和其前面一个元素之间的大小关系if(A[i] < A[i-d])
• 判断子表元素是否有序,如果有序就直接开始下一轮循环i++
• 如果不是有序的则使用带哨兵的直接插入排序的方法进行排序
  

交换排序

冒泡排序

第一趟排序使关键字最小的一个元素排到最前面王道视频中是从后向前遍历的并且保持的是升序序列。
只有A[j-1]>A[j]时才会交换保证了算法的稳定性。

快速排序

选择题整理总结

1.在排序过程中每趟都能确定一个元素在其最终位置有冒泡排序、简单选择排序、堆排序、快速排序前三者能形成全局有序的子序列后者能确定枢轴元素的最终位置。
2.基于插入、交换、选择的三种排序方法中通常简单方法是稳定的但是简单选择排序是例外复杂的方法都是不稳定的。
3.插入排序的核心将待插入元素插入前面的有序字表

• 确定的当前记录在前面有序子表中的位置直接插入排序采用顺序查找法
• 折半插入排序采用折半查找法

排序的趟数n-1
元素的移动次数取决于初始序列两者相同
使用的辅助空间数量O(1)
折半插入排序的比较次数和初始序列无关为O(nlogn)
直接插入排序的比较次数和初始序列有关为O(n)~O(n^2)

4.对于n个不同元素利用冒泡法从小到大排序在从大到小情况下元素交换次数最多
对于一个逆序的序列进行冒泡排序需要进行比较n(n-1)/2次
5.D

看条件想到基数排序假设对一些两位数排序个位是k1十位是k2则不符合基数排序。基数排序先排个位时是小的在后
所以应该是个位是k2十位是k1先k2再k1对k1应该使用稳定的排序算法。k1直接插入排序是稳定的选D
6.CC

7.选择排序在排序过程中比较次数与序列的初始状态无关为 (n-1)n/2次
8.归并排序在一趟结束后不一定能选出一个元素放在其最终位置上
9.归并排序在排序过程中的比较次数的数量级与序列的初始状态无关
10.对N个元素进行k路归并排序排序的趟数m=cell(logk(N))
11.很重要的表

12.在元素基本有序的情况下使用插入排序排序过程中元素比较次数最少
13.C

14.基数排序的元素移动次数与关键字的初始排列顺序无关
15.D

堆排序和希尔排序都用到了顺序存储的随机访问的特性链式存储不支持
16.A