企业官网建设流程全解析

这里主要总结内排序，不考虑外排序

内排序：在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换

内排序算法的稳定性：

• 如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。
• 反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

typedef int KeyType; //关键字类型 typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项 } RecType; //排序的记录类型定义

一、插入排序

基本思想：每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。

1.1 直接插入排序

基本思想：将序列分为前面的有序区和后面的无序区，每次从无序区中取出一个元素，在有序区查找该元素应该在的位置并插入。

初始时，有序区只有一个元素R[0]，i＝1~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].key（k=R[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. d=n/2

2. 将排序序列分为d个组（每隔d - 1个元素为一组），在各组内进行直接插入排序

3. 递减d=d/2，重复2 ，直到d=1

时间复杂度：，是不稳定的排序算法

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++){ //i+1到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; //i+1到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-low+1)*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; i+2*length-1<n; i=i+2*length-1){ Merge(R, i, i+length-1, i+2*length-1); } //如果最后剩余一个子区间，归并大区间和子区间 if(i+length-1<n-1){ Merge(R, i, i+length-1, n-1); } } //完整的二路归并 void MergeSort(RecType R[], int n){ int length; for(length=1; length<n; length=2*length){ MergePass(R, length, n); } }

算法性能比较