数据结构(C语言版)---排序

1、排序:重排表中元素。
2、根据数据元素是否完全在内存中,将排序算法分为内部排序和外部排序两类。
3、插入排序:将一个待排序记录按关键字大小插入到前面已排好的子序列中,直到全部记录插入完成。
1)直接插入排序
void insertsort(sqlist L)
{
int i, j;
for (i = 2; i <=L.length; ++i)
{
if (L.r[i].key < L.r[i - 1].key)
{
L.r[0] = L.r[i];
L.r[i] = L.r[i - 1];
for (j = i - 2; L.r[0].key < L.r[j].key; --j)
{
L.r[j + 1] = L.r[j];
}
L.r[j + 1] = L.r[0];
}
}
}
(1)空间复杂度为O(1);时间复杂度为O(n2)。
【数据结构(C语言版)---排序】(2)稳定性:插入元素时总是从后向前先比较后移动,不会出现相同元素相对位置发生变化,为稳定算法。
(3)适用性:适用于顺序存储和链式存储的线性表。
2)折半插入排序
void insertsort2(sqlist L)
{
int i, j, low, high, mid;
for (i = 2; i < L.length; i++)
{
L.r[0] = L.r[i];
low = 1;
high = i - 1;
while (low<=high)
{
mid = (low + high) / 2;
if (L.r[mid].key > L.r[0].key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (j = i - 1; j >= high + 1; --j)
{
L.r[j + 1] = L.r[j];
}
L.r[high + 1] = L.r[0];
}
}
(1)折半查找找出元素待插入的位置,统一地移动待插入位置之后的所有元素。
(2)时间复杂度为O(n2)。
(3)稳定性:为稳定算法。
3)希尔排序(缩小增量排序)
void insertsort3(sqlist L)
{
int i, j,k;
for (j = L.length / 2; j >= 1; j = j / 2)
{
for (i = j + 1; i <= L.length; ++i)
{
if (L.r[i].key < L.r[i - j].key)
{
L.r[0] = L.r[i];
for (k = i - j; k > 0 && L.r[0].key < L.r[k].key; k -= j)
{
L.r[k + j] = L.r[k];
}
L.r[k + j] = L.r[0];
}
}
}
}
(1)将待排序表分割成若干个子表,分别进行直接插入排序,当表中元素节本有序时,对整个表进行一次直接插入排序。
(2)空间复杂度为O(1);时间复杂度约为O(n1-2),最坏情况下时间复杂度为O(n2)。
(3)稳定性:不稳定。
(4)适用性:仅适用于顺序存储的线性表。
4、交换排序
1)冒泡排序
void bubblesort(sqlist L)
{
int i, j, temp;
bool flag; //发生交换的标志
for (i = 0; i < L.length-1; i++)
{
flag = false;
for (j = L.length - 1; j > i; j--)
{
if (L.r[j - 1].key > L.r[j].key)
{
temp = L.r[j - 1].key;
L.r[j - 1].key = L.r[j].key;
L.r[j].key = temp;
flag = true;
}
}
if (flag == false)
{
return;
}
}
}
(1)从后向前两两比较相邻元素的值,若为逆序则交换。
(2)空间复杂度为O(1);平均时间复杂度为O(n2),最坏情况下时间复杂度为O(n2)。
(3)稳定性:稳定。
(4)双向起泡排序。奇数趟时,从前向后比较相邻元素的关键字,逆序则交换;偶数趟时,从后向前比较相邻元素的关键字,逆序则交换。
void bubblesort2(sqlist L)
{
int low = 0, high = L.length;
bool flag = true;
int temp;
while (low{
flag = false;
for (int i = low; i < high; i++)
{
if (L.r[i].key > L.r[i + 1].key)
{
temp = L.r[i].key;
L.r[i].key = L.r[i+1].key;
L.r[i+1].key = temp;
flag = true;
}
}
high--;
for (int i = high; i >low; i--)
{
if (L.r[i].key < L.r[i - 1].key)
{
temp = L.r[i].key;
L.r[i].key = L.r[i - 1].key;
L.r[i - 1].key = temp;
flag = true;
}
}
low++;
}
}
2)快速排序
int partition(sqlist L, int low, int high)
{
int pivotkey;
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while (low{
while (low=pivotkey)
{
--high;
}
L.r[low] = L.r[high];
while (low < high&&L.r[low].key <= pivotkey)
{
++low;
}
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void quicksort(sqlist L,int low,int high)
{
if (low < high)
{
int pos = partition(L, low, high);
quicksort(L, low, pos - 1);
quicksort(L, pos + 1, high);
}
}
(1)最坏情况空间复杂度为O(n),平均空间复杂度为O(log2n);平均时间复杂度为O(nlog2n),最坏情况下时间复杂度为O(n2)。
(2)所有内部排序中平均性能最优的排序算法。
5、选择排序
每一趟在后面n-i+1个待排序元素中选取关键字最小的元素,作为有序序列的第i个元素,直到第n-1趟做完,待排序元素只剩一个。
1)简单选择排序
void selectsort(sqlist L)
{
int i, j, min,temp;
for (i = 0; i < L.length - 1; i++)
{
min = i;
for (j = i + 1; j < L.length; j++)
{
if (L.r[j].key < L.r[min].key)
{
min = j;
}
}
if (min != i)
{
temp = L.r[i].key;
L.r[i].key = L.r[min].key;
L.r[min].key = temp;
}
}
}
(1)空间复杂度为O(1);时间复杂度为O(n2)。
(2)稳定性:不稳定。
2)堆排序
void adjustdown(sqlist L,int k)//将元素向下调整
{
L.r[0].key = L.r[k].key;
for (int i = 2 * k; i <= L.length; i *= 2)
{
if (I < L.length&&L.r[i].key < L.r[i + 1].key)
{
i++;
}
if (L.r[0].key >= L.r[i].key)
{
break;
}
else
{
L.r[k].key = L.r[i].key;
k = i;
}
}
L.r[k].key = L.r[0].key;
}
时间复杂度与树高(h)有关,为O(h)。
void adjustup(sqlist L, int k)//将元素向上调整
{
L.r[0].key = L.r[k].key;
int i = k / 2;
while (i>0&& L.r[i].key < L.r[0].key)
{
L.r[k].key = L.r[i].key;
k = i;
i = k / 2;
}
L.r[k].key = L.r[0].key;
}
void buildmaxheap(sqlist L)//建立大根堆
{
for (int i = L.length / 2; i > 0; i--)
{
adjustdown(L, i);
}
}
在n个元素序列上建堆,时间复杂度为O(n)。
void heapsort(sqlist L)
{
buildmaxheap(L);
int temp;
for (int i = L.length; i > 1; i--)
{
temp = L.r[i].key;
L.r[i].key = L.r[1].key;
L.r[1].key = temp;
adjustdown(L, 1);
}
}
(1)一种树形选择排序,在排序过程中,将L视为一棵完全二叉树的顺序存储结构。
(2)最大堆:堆顶元素取最大值;最小堆:栈顶元素为最小值。
(2)空间复杂度为O(1);时间复杂度为O(nlog2n)。
(3)稳定性:不稳定。
6、归并排序
1)归并:将两个或两个以上的有序表组合成一个新的有序表。
2)2路归并排序
void merge(sqlist A, int low, int mid, int high)
{
sqlist B;
int i, j, k;
for (k = low; k <= high; k++)
{
B.r[k].key = A.r[k].key;
}
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
{
if (B.r[i].key <= B.r[j].key)
{
A.r[k].key <= B.r[i++].key;
}
else
{
A.r[k].key <= B.r[j++].key;
}
}
while (i<=mid)
{
A.r[k++].key <= B.r[i++].key;
}
while (j <= high)
{
A.r[k++].key <= B.r[j++].key;
}
}
void mergesort(sqlist L, int low, int high)
{
if (low < high)
{
int mid = (low + high) / 2;
mergesort(L, low, mid);
mergesort(L, mid + 1, high);
merge(L, low, mid, high);
}
}
(1)假定带排序表含有n个记录,则将其视为n个有序的子表,每个子表长度为1,然后两两归并,得到n/2个长度为2或1的有序表,再两两归并,直到合并成一个长度为n的有序表为止。
(2)空间复杂度为O(n);时间复杂度为O(nlog2n)。
(3)稳定性:稳定。
7、基数排序
(1)分类:最高位优先(MSD)、最低位优先(LSD)。
(2)一趟排序需要辅助存储空间为r,空间复杂度为O(r);基数排序需要进行d趟分配和收集,一趟分配需要O(n),一趟收集需要O(r),故基数排序时间复杂度为O(d(n+r)),与序列的初始状态无关。
(3)稳定性:稳定。
8、内部排序的比较

算法种类 时间复杂度 空间复杂度 是否稳定
最好情况 平均情况 最坏情况
直接插入排序 O(n) O(n2) O(n2) O(1)
冒泡排序 O(n) O(n2) O(n2) O(1)
简单选择排序 O(n2) O(n2) O(n2) O(1)
希尔排序 O(1)
快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1)
2路归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r)
折半插入排序 O(n2) O(n2) O(n2) O(1)
9、排序小结
1)n较小,采用直接插入排序或简单选择排序。
2)初始状态基本有序,采用直接插入排序或冒泡排序。
3)n较大,采用快速排序、堆排序、归并排序。
4)n较大,关键字位数较少,且可分解,采用基数排序。
10、外部排序通常采用归并排序方法。
1)外部排序所需总时间=内部排序所需时间+外存信息读写时间+内部归并所需时间
2)多路平衡归并
(1)败者树:完全二叉树且不含叶子,可采用顺序存储结构。
3)置换-选择排序:在整个排序过程中,选择最小(或最大)关键字和输入、输出交叉或平行进行。
4)最佳归并树

    推荐阅读