一.排序算法 1.排序 从今天开始我们就要开始学习排序算法啦！ 排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便,通常希望计算机中的表是按关键字有序的。 2.稳定性 除了我们之前了解的时间复杂度和空间复杂度来判断一个算法的好坏之外，在排序算法这里我们引入一个新的判断标准——稳定性。 算法的稳定性。若待排序表中有两个元素R;和R，其对应的关键字相同即key~i~= key~j~,且在排序前R~i~在R~j~的前面， 若使用某一排序算法排序后，R~i~仍然在R~j~的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。 3.算法分类 这里需要注意的是我们上一篇博客在图的应用中的拓扑排序他并不是我们这里严格意义上的排序算法。 二.直接插入排序 1.操作步骤 要将元素L(i)插入已有序的子序列[1……i-1]，需要执行以下操作(为避免混淆，下面用L[ ]表示一个表，而用L()表示一个元素): 1)查找出L(i)在L[...i-1]中的插入位置k。 2)将L[.1i-1]中的所有元素依次后移-一个位置。 3)将L(i)复制到L(k)。 为了实现对L1..n]的排序,可以将L(2) ~L (n)依次插入前面已排好序的子序列，初始L[1]可以视为是一个已排好序的子序列。上述操作执行n- 1次就能得到一个有序的表。插入排序在实现上通常采用就地排序(空间复杂度为0(1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。 2.举例演示 假定初始序列为49, 38, 65, 97 ,76, 13, 27,49，初始时49可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如图所示，括号内是已排好序的子序列。 3.性能分析 空间效率:仅使用了常数个辅助单元，因而空间复杂度为0(1)。 时间效率:在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一一次而不用移动元素，因而时间复杂度为0(n)。在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反(逆序)， 总的比较次数达到最大，总的移动次数也达到最大，总的时间复杂度为0(2)。平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n^2^ /4。 4.代码实现 //直接插入排序 void InsertSort1(SqList &L){ Elemtype temp; int i,j; for(i=1;i=0 && temp.grade temp.grade) high = mid - 1; else low = mid + 1; } for(j=i-1; j>=high+1; --j){ L.data[j+1] = L.data[j]; } L.data[high+1] = temp; } } 四.希尔排序 1.排序过程 希尔排序的过程如下:先取一个小于n的步长d,把表中的全部记录分成d组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序;然后取第二个步长d2=1;dk=dk/2){ for(i=dk;i=0 && temp.grade #include #include #define MaxSize 50 //这里只是演示，我们假设这里最多存五十个学生信息 //定义学生结构 typedef struct { char name[200]; //姓名 int grade; //分数，这个是排序关键字 } Elemtype; //声明使用顺序表 typedef struct { /*这里给数据分配内存，可以有静态和动态两种方式，这里采用动态分配*/ Elemtype *data; //存放线性表中的元素是Elemtype所指代的学生结构体 int length; //存放线性表的长度 } SqList; //给这个顺序表起个名字，接下来给这个结构体定义方法 //初始化线性表 void InitList(SqList &L){ /*动态分配内存的初始化*/ L.data = (Elemtype*)malloc(MaxSize * sizeof(Elemtype)); //为顺序表分配空间 L.length = 0; //初始化长度为0 } //求表长函数 int Length(SqList &L){ return L.length; } //求某个数据元素值 bool GetElem(SqList &L, int i, Elemtype &e) { if (i < 1 || i > L.length) return false; //参数i错误时，返回false e = L.data[i - 1]; //取元素值 return true; } //输出线性表 void DispList(SqList &L) { if (L.length == 0) printf("线性表为空"); //扫描顺序表，输出各元素 for (int i = 0; i < L.length; i++) { printf("%s %d", L.data[i].name, L.data[i].grade); printf("\n"); } printf("\n"); } //插入数据元素 bool ListInsert(SqList &L, int i, Elemtype e) { /*在顺序表L的第i个位置上插入新元素e*/ int j; //参数i不正确时，返回false if (i < 1 || i > L.length + 1 || L.length == MaxSize) return false; i--; //将顺序表逻辑序号转化为物理序号 //参数i正确时，将data[i]及后面的元素后移一个位置 for (j = L.length; j > i; j--) { L.data[j] = L.data[j - 1]; } L.data[i] = e; //插入元素e L.length++; //顺序表长度加1 return true; /*平均时间复杂度为O(n)*/ } //直接插入排序 void InsertSort1(SqList &L){ Elemtype temp; int i,j; for(i=1;i=0 && temp.grade temp.grade) high = mid - 1; else low = mid + 1; } for(j=i-1; j>=high+1; --j){ L.data[j+1] = L.data[j]; } L.data[high+1] = temp; } } //希尔排序 void ShellSort(SqList &L){ int dk,i,j; Elemtype temp; for(dk=L.length/2;dk>=1;dk=dk/2){ for(i=dk;i=0 && temp.grade

本文链接：https://www.leiyu.cn/news/content/2431.html 复制本文链接 链接已复制