所谓排序,是要整理表中的记录,使之按关键字递增(或递减)的有序排列。
内排序全称为内部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
待排序的顺序表中数据元素的类型定义如下(类似于被查找的顺序表元素类型):
typedef int KeyType; // 关键字的数据类型typedef struct{ KeyType key; InfoType data; // 其他数据, 可选} RecType;
插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。
两种插入排序方法:
直接插入排序方法中:每趟插入只排好一个数;n个数要进行n − 1趟插入排序才能全部排好。
//对R[0..n-1]按递增有序进行直接插入排序void insertSort(RecType R[], int n){ int i, j; RecType tmp; for (i = 1; i < n; i++) { tmp = R[i]; j = i - 1; // 从右向左在有序区R[0..i-1]找R[i]的插入位置 while (j >= 0 && tmp.key < R[j].key) { R[j + 1] = R[j]; // 将关键字大于R[i].key的记录后移 j--; } R[j + 1] = tmp; // 在j+1处插入R[i] }}
1391679-20180618165919523-196396537
交换排序的基本思想:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
两种交换排序方法: