这里主要总结内排序不考虑外排序内排序在排序过程中若整个表都是放在内存中处理排序时不涉及数据的内、外存交换内排序算法的稳定性如果待排序的表中存在有多个关键字相同的记录经过排序后这些具有相同关键字的记录之间的相对次序保持不变则称这种排序方法是稳定的。反之若具有相同关键字的记录之间的相对次序发生变化则称这种排序方法是不稳定的。typedef int KeyType; //关键字类型 typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项 } RecType; //排序的记录类型定义一、插入排序基本思想每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列直到全部记录插入完成。1.1 直接插入排序基本思想将序列分为前面的有序区和后面的无序区每次从无序区中取出一个元素在有序区查找该元素应该在的位置并插入。初始时有序区只有一个元素R[0]i1~n-1共经过n-1趟排序//直接插入排序 void InsertSort(RecType R[], int n){ int i; //全序列遍历指针 int j; //有序区遍历指针 RecType temp; //方便实现插入操作 //从前往后遍历序列 for(i 1; i n; i){ //遇到第一个位置不对的元素进行直接插入排序 if(R[i].key R[i - 1].key){ //把R[i]取出 temp R[i]; //指针j从后往前遍历有序区找到R[i]的位置 j i - 1; while(j 0 R[j].key temp.key){ //当前遍历元素大于R[i]时该元素向后移动 R[j 1] R[j]; j--; } //最后在j 1的位置插入R[i] R[j 1] temp; } } }时间复杂度空间复杂度稳定性每次插入元素时总是从后往前先比较再移动不会出现相同元素的相对位置发生变化的情况是稳定的排序算法。1.2 折半插入排序基本思想同直接插入排序只是在查找元素位置时采用折半查找二分查找方法。折半查找在R[low..high]中查找 ≥R[i].keykR[i].key的最左边的位置时间复杂度void BinInsertSort(RecType R[], int n){ int i; //全局遍历指针 int j; //有序区遍历指针 int low; //二分查找左边界 int high; //二分查找右边界 int mid; //二分查找比较索引 RecType temp; //实现交换和插入 //从前往后遍历序列 for(i 1; i n; i){ //找到第一个位置不正确的元素 if(R[i - 1].key R[i].key){ temp R[i]; //开始二分查找 low 0; high i - 1; while(low high){ mid (low high) / 2; if(R[mid].key temp.key){ //更新右边界 high mid - 1; }else{ //更新左边界 low mid 1; } } //退出循环之后low high 1 for(j i - 1; j high 1; j--){ R[j 1] R[j]; } //插入temp R[high 1] temp; } } }1.3 希尔排序基本思想1. dn/22. 将排序序列分为d个组每隔d - 1个元素为一组在各组内进行直接插入排序3. 递减dd/2重复2 直到d1时间复杂度是不稳定的排序算法void ShellSort(RecType R[], int n){ int i; //全局遍历指针 int j; //有序区遍历指针 int d 2 / n; //分组间隔 RecType temp; //用于排序 //遍历序列 while(d 0){ //遍历每一组 for(int i d; i n; i){ //每一组内直接插入排序 temp R[i]; //有序区为当前元素的前一个元素 j i - d; while(j 0 temp.key R[j].key){ R[j d] R[j]; j - d; } R[j d] temp; } d / 2; } }二、交换排序2.1 冒泡排序基本思想反复遍历无序区依次比较相邻元素并交换顺序错误对使最大/最小元素逐渐冒泡到有序区时间复杂度void BubbleSort(RecType R[], int n){ int i; //全局遍历指针 int j; //无序区遍历指针 //从前向后遍历 for(i 0; i n; i){ //i1到n为无序区 for(j n - 1; j i; j--){ if(R[j].key R[j - 1].key){ swap(R[j], R[j - 1]); } } } }该算法还可以进一步改进当某一趟结束之后如果没有发生元素的交换则说明此时序列已经有序可以结束算法//改进 void BubbleSort(RecType R[], int n){ int i; //全局遍历指针 int j; //无序区遍历指针 bool exchange; //从前向后遍历 for(i 0; i n; i){ exchange false; //i1到n为无序区 for(j n - 1; j i; j--){ if(R[j].key R[j - 1].key){ swap(R[j], R[j - 1]); exchange true; } } if(!exchange){ return; } } }2.2 快速排序基本思想每趟使表的第1个记录基准放入适当位置归位将表一分为二对子表按递归方式继续这种划分。 直至划分的子表长为0或1递归出口。时间复杂度//一趟排序 int partition(RecType R[], int s, int t){ int i s; int j t; RecType temp R[i]; //以R[i]为基准 //两端交替向中间扫描直至i j为止 while(i j){ while(j i R[j].key temp.key){ j--; } //找到比基准小的R[j]放到R[i]处 R[i] R[j]; while(i j R[i].key temp.key){ i; } //找到比基准大的R[i]放到R[j]处 R[j] R[i]; } R[i] temp; return i; } //快速排序 void QuickSort(RecType R[], int s, int t){ int i; //记录每趟之后基准的位置 if(s t){ i partition(R, s, t); //递归处理左区间 QuickSort(R, s, i - 1); //递归处理右区间 QuickSort(R, i 1, j); } }三、选择排序3.1 简单选择排序跟冒泡排序的思路很像每次都是从无序区找出最大/最小的元素加入到有序区区别在于冒泡排序的元素是通过两两交换一个一个冒上去的而简单选择排序是直接找到该元素只进行一次交换时间复杂度void SelectSort(RecType R[], int n){ int i; //全局遍历指针 int j; //无序区遍历指针 int k; //无序区最小值指针 for(i 0; i n; i){ k i; for(j i 1; j n; j){ if(R[j].key R[k].key){ k j; } } if(k ! i){ swap(R[i], R[k]); } } }3.2 堆排序思路同简单选择排序区别在于简单选择排序是通过两两比较找到的交换元素而堆排序采用对方法找到该元素大根堆对应的完全二叉树中任意一个结点的关键字都大于或等于它的孩子结点的关键字。最小关键字的记录一定是某个叶子结点时间复杂度为不稳定的排序算法具体算法不详细介绍四、归并排序归并排序是多次将相邻两个或两个以上的有序表合并成一个新有序表的排序方法。二路归并排序是多次将相邻两个的有序表合并成一个新有序表的排序方法是最简单的归并排序。时间复杂度//一次二路归并将两个相邻的有序子序列归并为一个有序序列 void Merge(RecType R[], int low, int mid, int high){ RecType *R1; int i low, j mid 1, k 0; R1(RecType *)malloc((high-low1)*sizeof(RecType)); while(i mid j high){ if(R[i].key R[j].key){ //将第1段中的记录放入R1中 R1[k]R[i]; i; k; } else{ //将第2段中的记录放入R1中 R1[k] R[j]; j; k; } } //如果第1段有剩余全部复制到R1 while(i mid){ R1[k] R[i]; i; k; } //如果第2段有剩余全部复制到R1 while(j high){ R1[k] R[j]; j; k; } //将R1复制回R中 for(k 0, i low; i high; k, i){ R[i] R1[k]; } free(R1); } //一趟二路归并段长为length void MergePass(RecType R[], int length, int n){ int i; //归并长为length的两个相邻子区间 for(i 0; i2*length-1n; ii2*length-1){ Merge(R, i, ilength-1, i2*length-1); } //如果最后剩余一个子区间归并大区间和子区间 if(ilength-1n-1){ Merge(R, i, ilength-1, n-1); } } //完整的二路归并 void MergeSort(RecType R[], int n){ int length; for(length1; lengthn; length2*length){ MergePass(R, length, n); } }算法性能比较