三种简单排序方法

1、三种简单排序方法数 据 结 构排序1.1 简单选择排序简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。在每一趟扫描数据时，用一个整型变量跟踪当前最小数据的位置，然后，第i趟扫描只需将该位置的数据与第i个数据交换即可。这样扫描n-1次，处理数据的个数从n每次逐渐减1，每次扫描结束时才可能有一次交换数据的操作。 排序图7.1 简单选择排序排序简单选择排序分析简单选择排序在(n-1)趟扫描中共需进行n(n-1)/2次比较，最坏情况下的互换次数为(n-

2、1)，整个算法的时间复杂性为O(n2)。简单选择排序简单并且容易实现，适宜于n较小的情况。简单选择排序是不稳定的排序算法。排序简单选择排序算法void selectsort (sqlist r, int n) int i, j, min; for (i=1;i=n-1;i+) min=i; /*用min指出每一趟在无序区范围内的最小元素*/ 排序简单选择排序算法续 for (j=i+1;j=n-1;j+) if (rj.key rmin.key) min=j; r0 = ri; /* r0用于暂时存放元素*/ ri = rmin; rmin =r0; 排序1.2 冒泡排序冒泡排序是一种简单而且

3、容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。其基本思想是对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟（pass）。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。排序图7.2 冒泡排序过程排序需扫描的趟数视原始数据最初的排列次序的不同而不同，最坏的情况要进行（n-1）趟扫描，一般常常少于(n-1)趟即可完成。可以设置一个标志flag用来指示扫描中有没有进行数据交换，每趟扫描开始前将其置1。当这趟扫描至少出现一次互换时，将其置0。如某趟扫描后flag仍为1，说明此趟

4、扫描已无数据互换，则排序结束，不必再继续扫描了。排序冒泡排序算法void bubblesort(sqlist r, int n) int i,j,flag; for(i=1;i=n-1;i+) flag=1; for( j=i;j=n-1;j+) if (rj+1.key rj.key) 排序冒泡排序算法续 flag=0; r0=rj; /* r0用于暂时存放元素*/ rj=rj+1; rj+1=r0; if (flag=1) return; 排序冒泡排序算法分析冒泡排序算法的优点是比较容易理解，且当原始数据大体符合要求的次序时，运算速度较快。但它不是高效率的算法，在最坏的情况下，如果输入数据

5、的次序与排序要求的次序完全相反，冒泡排序需要进行n(n-1)/2次比较和n(n-1)3/2次移动，其数量级均为O(n2)。对于有相同关键字记录的情况，冒泡排序是稳定的。排序1.3 直接插入排序直接插入排序的基本思想是：从数组的第二个单元开始，依次从原始数据中取出数据，并将其插入到数组中该单元之前的已排好序的序列中合适的位置处。直接插入算法需要经过（n-1）趟插入过程。如果数据恰好应插入到序列的最后端，则不需移动数据，可节省时间，所以若原始数据大体有序，此算法可以有较快的运算速度。排序图7.3 简单插入排序排序简单插入排序算法void insertsort (sqlist r, int n) int i,j; for( i=2; i=n; i+) r0=ri; /* r0用于暂时存放待插入的元素*/ j= i-1; /* j为待比较元素下标，初始时指向待插入元素前一个单元*/ 排序简单插入排序算法续 while (r0.keyrj.key) rj+1=rj;