内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
内排序可以分为：插入排序、交换排序、选择排序和归并排序。
#define MAXSIZE 10
typedef struct {
int r[MAXSIZE + 1]; //用于存储要排序数组，r[0]用作哨兵或临时变量
int length;
}SqList;
//交换L中数组r的下标为i和j的值
void swap(SqList *L, int i, int j) {
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
冒泡排序
冒泡排序是一种交换排序，基本思想是两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。
时间复杂度为O(n2)
void BubbleSort(SqList *L) {
bool flag = TRUE;
for (int i = 1; i < L->length && flag; i++) {
flag = false;
for (int j = L->length - 1; j >= i; j--) {
if (L->r[j] > L->r[j + 1]) {
swap(L, j, j + 1);
flag = true;
}
}
}
}
简单选择排序
简单选择排序通过n - i次关键字间的比较，从n - i + 1个记录中选出关键字最小的记录，并和第i（1<= i <= n）个记录交换之。
时间复杂度为O(n2)
void SelectSort(SqList *L) {
int min;
for (int i = 1; i < L->length; i++) {
min = i;
for (int j = i + 1; j <= L->length; j++) {
if (L->r[min] > L->r[j]) {
min = j;
}
}
if (i != min) {
swap(L, i, min);
}
}
}
直接插入排序
直接插入排序是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。
时间复杂度为O(n2)
void InsertSort(SqList *L) {
int j;
for (int i = 2; i <= L->length; i++) {
if (L->r[i] < L->r[i - 1]) {
L->r[0] = L->r[i];
for (j = i - 1; L->r[j] > L->r[0]; j--) {
L->r[j + 1] = L->r[j];
}
L->r[j + 1] = L->r[0];
}
}
}
希尔排序
希尔排序将相距某个增量的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
void ShellSort(SqList *L) {
int j;
int increment = L->length;
do {
increment = increment / 3 + 1;
for (int i = increment + 1; i <= L->length; i++) {
if (L->r[i] < L->r[i - increment]) {
L->r[0] = L->r[i];
for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment) {
L->r[j + increment] = L->r[j];
}
L->r[j + increment] = L->r[0];
}
}
} while (increment > 1);
}
堆排序
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
堆排序就是将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的莫为元素交换，此时末位元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。
时间复杂度为O(n㏒n)。
void HeapAdjust(SqList *L, int s, int m) {
int temp = L->r[s];
for (int j = 2 * s; j <= m; j *= 2) {
if (j < m && L->r[j] < L->r[j + 1]) {
++j;
}
if (temp >= L->r[j]) { break; }
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp;
}
void HeapSort(SqList *L) {
for (int i = L->length / 2; i > 0; i--) { //把L中的r构建成一个大顶堆
HeapAdjust(L, i, L->length);
}
for (int i = L->length; i > 1; i--) {
swap(L, 1, i); //将顶堆记录和当前未经排序子序列的最后一个记录交换
HeapAdjust(L, 1, i - 1); //将L->r[1..i - 1]重新调整为大顶堆
}
}
归并排序
归并排序原理是，假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n / 2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列，再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
时间复杂度为O(n㏒n)。
void Merge(int SR[], int TR[], int i, int m, int n) {
int j, k, l;
for (j = m + 1, k = i; i <= m && j <= n; k++) {
if (SR[i] < SR[j]) {
TR[k] = SR[i++];
} else {
TR[k] = SR[j++];
}
}
if (i <= m) {
for (l = 0; l <= m - i; l++) {
TR[k + 1] = SR[i + 1];
}
}
if (j <= n) {
for (l = 0; l <= n - j; l++) {
TR[k + 1] = SR[j + 1];
}
}
}
void MSort(int SR[], int TR1[], int s, int t) {
int m, TR2[MAXSIZE];
if (s == t) {
TR1[s] = SR[s];
} else {
m = (s + t) / 2; //将SR[s..t]平分为SR[s..m]和SR[m + 1..t]
MSort(SR, TR2, s, m); //递归将SR[s..m]归并为有序的TR[s..m]
MSort(SR, TR2, m + 1, t); //递归将SR[m + 1..t]归并为有序的TR[m + 1..t]
Merge(TR2, TR1, s, m, t); //将TR2[s..m]和TR2[m + 1..t]归并到TR1[s..t]
}
}
void MergeSort(SqList *L) {
MSort(L->r, L->r, 1, L->length);
}
非递归归并排序
void MergePass(int SR[], int TR[], int s, int n) {
int i = 1;
while (i <= n - 2 * s + 1) {
Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;
}
if (i < n - s + 1) {
Merge(SR, TR, i, i + s - 1, n);
} else {
for (int j = 0; j <= n; j++) {
TR[j] = SR[j];
}
}
}
void MergeSort(SqList *L) {
int *TR = (int *)malloc(L->length * sizeof(int));
int k = 1;
while (k < L->length) {
MergePass(L->r, TR, k, L->length);
k = 2 * k;
MergePass(TR, L->r, k, L->length);
k = 2 * k;
}
}
使用归并排序时，尽量考虑用非递归方法。
快速排序
快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
时间复杂度为O(n㏒n)
int Partition(SqList *L, int low, int high) {
int pivotkey;
pivotkey = L->r[low]; //用子表的第一个记录作枢轴记录
while (low < high) { //从表的两端交替向中间扫描
while (low < high && L->r[high] >= pivotkey) {
high--;
}
swap(L, low, high); //将比枢轴记录小的记录交换到低端
while (low < high && L->r[low] <= pivotkey) {
low++;
}
swap(L, low, high); //将比枢轴记录大的记录交换到高端
}
return low; //返回枢轴所在位置
}
void QSort(SqList *L, int low, int high) {
int pivot;
if (low < high) {
pivot = Partition(L, low, high); //将L->r[low..high]一分为二
QSort(L, low, pivot - 1); //对低子表递归排序
QSort(L, pivot + 1, high); //对高地表递归排序
}
}
void QuickSort(SqList *L) {
QSort(L, 1, L->length);
}
快速排序优化
#define MAX_LENGTH_INSERT_SORT 7
int Partition(SqList *L, int low, int high) {
int pivotkey;
int m = low + (high - low) / 2;
if (L->r[low] > L->r[high]) {
swap(L, low, high);
}
if (L->r[m] > L->r[high]) {
swap(L, high, m);
}
if (L->r[m] > L->r[low]) {
swap(L, m, low);
}
pivotkey = L->r[low]; bb
L->r[0] = pivotkey;
while (low < high) {
while (low < high && L->r[high] >= pivotkey) {
high--;
}
L->r[low] = L->r[high];
while (low < high && L->r[low] <= pivotkey) {
low++;
}
L->r[high] = L->r[low];
L->r[low] = L->r[0];
}
return low;
}
void QSort(SqList *L, int low, int high) {
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT) {
while (low < high) {
pivot = Partition(L, low, high);
QSort(L, low, pivot - 1);
low = pivot + 1;
}
} else {
InsertSort(L);
}
}
网友评论