一.选择排序

选择排序的基本思想是:每一趟(如第i趟)在后面n-i+1 (i=1,2…,n-1) 个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。选择排序中的堆排序算法是历年考查的重点。

二.简单选择排序

1.算法思想

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想:假设排序表为[L…n]，第i趟排序即从Li.n]中选择关键字最小的元素与I(i)交换，每-趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

2.算法实现

//简单选择排序void selectsort(SqList &L){for(int i=0;i<L.length-1;i++){//一共进行n-1趟Elemtype min=L.data[i];//记录最小的元素位置int n=0;for(int j=i+1;j<L.length;j++){//从未排序部分开始遍历if(L.data[j].grade<min.grade) {min=L.data[j];n=j;}}if(min.grade!=L.data[i].grade){Elemtype temp=L.data[i];L.data[i]=L.data[n];L.data[n]=temp;}}}

3.效率分析

简单选择排序算法的性能分析如下:

  • 空间效率:仅使用常数个辅助单元，故空间效率为0(1)。，
  • 时间效率:从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过3(n- 1)次，最好的情况是移动0次，此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关，始终是n(n- 1)/2次，因此时间复杂度始终是0(n2 )。
  • 稳定性:在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如，表L= {2,2,1}，经过一趟排序后L={1,2,2}，最终排序序列也是L={1,2,2}，显然，2与2的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。

三.堆排序

1.算法思想

堆排序的思路很简单:首先将存放在L1…n]中的n个元素建成初始堆，由于堆本身的特点(以大顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩-一个元素为止。可见堆排序需要解决两个问题:①如何将无序序列构造成初始堆?②输出堆顶元素后，如何将剩余元素调整成新的堆?

堆排序的关键是构造初始堆。n个结点的完全二二叉树，最后一个结点是第Ln/2」个结点的孩子。对第Ln/2」个结点为根的子树筛选(对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换),使该子树成为堆。之后向前依次对各结点(Ln/2J-1~1)为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一-级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

2.调整示例

初始时调整L(4)子树，09 < 32，交换，交换后满足堆的定义;向前继续调整L(3)子树，78<左右孩子的较大者87，交换，交换后满足堆的定义;向前调整L(2)子树，17 <左右孩子的较大者45，交换后满足堆的定义;向前调整至根结点L(1)，53 <左右孩子的较大者87，交换，交换后破坏了L(3)子树的堆，采用上述方法对L(3)进行调整，53<左右孩子的较大者78，交换，至此该完全二叉树满足堆的定义。

3.C语言实现

void Heapsort(SqList &L){buildMaxheap(L);for(int i=L.length-1;i>0;i--){Elemtype temp=L.data[i];L.data[i]=L.data[0];L.data[0]=temp;HeadAdjust(L,0, i);}}

4.效率分析

堆排序算法的性能分析如下:

  • 空间效率:仅使用了常数个辅助单元，所以空间复杂度为0(1)。
  • 时间效率:建堆时间为O(n),之后有n-1次向下调整操作，每次调整的时间复杂度为O(h),故在最好、最坏和平均情况下，堆排序的时间复杂度为O(nlog2n)。
  • 稳定性:进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。例如,表L= {1, 2, 2},构造初始堆时可能将2交换到堆顶,此时L= {2, 1,2}，最终排序序列为L={1,2,2}，显然，2与2的相对次序已发生变化。

四.C语言实现完整示例

/*我们今天的主角插入排序是基于查找算法来的，所以我们还是利用线性表来进行模拟*//*为了便于我们后面演示希尔排序，所以我们采用顺序存储结构*/#include #include #include #define MaxSize 50//这里只是演示，我们假设这里最多存五十个学生信息//定义学生结构typedef struct {char name[200];//姓名intgrade; //分数，这个是排序关键字} 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错误时，返回falsee = 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不正确时，返回falseif (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;//插入元素eL.length++; //顺序表长度加1return true;/*平均时间复杂度为O(n)*/}//简单选择排序void selectsort(SqList &L){for(int i=0;i<L.length-1;i++){//一共进行n-1趟Elemtype min=L.data[i];//记录最小的元素位置int n=0;for(int j=i+1;j<L.length;j++){//从未排序部分开始遍历if(L.data[j].grade<min.grade) {min=L.data[j];n=j;}}if(min.grade!=L.data[i].grade){Elemtype temp=L.data[i];L.data[i]=L.data[n];L.data[n]=temp;}}}void HeadAdjust(SqList &L,int k, int len){Elemtype temp=L.data[k];for(int i=2*k+1;i<len;i=2*i+1){if(i<len-1 && L.data[i].grade<L.data[i+1].grade)i++;if(temp.grade>=L.data[i].grade)break;else{L.data[k]=L.data[i];k=i;}}L.data[k]=temp;}void buildMaxheap(SqList &L){for(int i=L.length/2-1;i>=0;i--)HeadAdjust(L, i, L.length);}void Heapsort(SqList &L){buildMaxheap(L);for(int i=L.length-1;i>0;i--){Elemtype temp=L.data[i];L.data[i]=L.data[0];L.data[0]=temp;HeadAdjust(L,0, i);}}int main(){SqList L;Elemtype stuents[10]={{"张三",649},{"李四",638},{"王五",665},{"赵六",697},{"冯七",676},{"读者",713},{"阿强",627},{"杨曦",649},{"老六",655},{"阿黄",604}};//这一部分忘了的请回顾我的相关博客printf("初始化顺序表并插入开始元素：\n");InitList(L); //这时是一个空表，接下来通过插入元素函数完成初始化for (int i = 0; i < 10; i++)ListInsert(L, i + 1, stuents[i]);DispList(L);/*printf("根据分数进行简单选择排序后结果为：\n");selectsort(L);DispList(L);//到这一步我们的简单选择排序没什么问题的 */printf("根据分数进行堆排序后结果为：\n");Heapsort(L);DispList(L);}

五.运行结果

1.简单选择排序

2.堆排序