数据结构（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）最佳归并树