数据结构排序算总结I.docVIP

数据结构排序算法总结I考研复习到数据结构排序这章了，这章的内容比较经典，都是一些很好的算法，将来很可能会用得到，总结一下，加深一下印象。 ????????????? 文章篇幅有点大，请点击查看更多，下面是跳转链接： ?????????????? 一、插入排序????? 1）直接插入排序????? 2）折半插入排序????? 3）希尔排序 ?????????????? 二、交换排序????? 1）冒泡排序??????????? 2）快速排序????? ?????????????? 三、选择排序????? 1）简单选择排序????? 2）堆排序????? ??????????????? 四、归并排序????? ?????????????? 五、基数排序???? ??????? 一、插入排序 ????????????? 1）直接插入排序???? 算法演示 ??????????????时间复杂度：平均情况—O(n2)???? 最坏情况—O(n2)???? 辅助空间：O(1)????? 稳定性：稳定 复制到剪贴板折叠C 代码 void InsertSort(SqList L) {?? ?? ??// 对顺序表L作直接插入排序。 ?? ??int i,j; ?? ??for (i=2; i=L.length; ++i) ?? ????if (LT(L.r[i].key, L.r[i-1].key)) { ?? ??????// 时，需将L.r[i]插入有序子表 ?? ?????? L.r[0] = L.r[i];?????????????????// 复制为哨兵 ?? ??????for (j=i-1;?? LT(L.r[0].key, L.r[j].key);?? --j) ?? ???????? L.r[j+1] = L.r[j];?????????????// 记录后移 ?? ?????? L.r[j+1] = L.r[0];???????????????// 插入到正确位置 ?? ???? } ?? } // InsertSort ?? ????????????? 2）折半插入排序 ?????????????? 时间复杂度：平均情况—O(n2)?????稳定性：稳定 复制到剪贴板折叠C 代码 void BInsertSort(SqList L) {?? ?? ??// 对顺序表L作折半插入排序。 ?? ??int i,j,high,low,m; ?? ??for (i=2; i=L.length; ++i) { ?? ???? L.r[0] = L.r[i];???????// 将L.r[i]暂存到L.r[0] ?? ???? low = 1;??? high = i-1; ?? ????while (low=high) {????// 在r[low..high]中折半查找有序插入的位置 ?? ?????? m = (low+high)/2;????????????????????????????// 折半 ?? ??????if (LT(L.r[0].key, L.r[m].key)) high = m-1;??// 插入点在低半区 ?? ??????else?? low = m+1;?????????????????????????????// 插入点在高半区 ?? ???? } ?? ????for (j=i-1; j=high+1; --j) L.r[j+1] = L.r[j];??// 记录后移 ?? ???? L.r[high+1] = L.r[0];???????????????????????????// 插入 ?? ?? } ?? } // BInsertSort ?? ????????????? 3）希尔排序 算法演示 ?????????????? 时间复杂度：理想情况—O(nlog2n)????? 最坏情况—O(n2)???? 稳定性：不稳定 复制到剪贴板折叠C 代码 void ShellInsert(SqList L, int dk) {?? ?? ??// 对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改： ?? ??//????? 1. 前后记录位置的增量是dk，而不是1； ?? ??//????? 2. r[0]只是暂存单元，不是哨兵。当j=0时，插入位置已找到。 ?? ??int i,j; ?? ??for (i=dk+1; i=L.length; ++i) ?? ????if (LT(L.r[i].key, L.r[i-dk].key)) { // 需将L.r[i]插入有序增量子表 ?? ?????? L.r[0]