对一序列对象根据某个关键字进行排序。
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。 非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
11.png
12.png
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机
内执行时所需存储空间的度量，它也是数据规模n的函数。
冒泡排序 是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
void BubbleSort2(SqList *L){
int i,j;
//flag用作标记
Status flag = TRUE;
//i从[1,L->length) 遍历;
//如果flag为False退出循环. 表示已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态;
for (i = 1; i < L->length && flag; i++) {
//flag 每次都初始化为FALSE
flag = FALSE;
for (j = L->length-1; j>=i; j--) {
if(L->r[j] > L->r[j+1]){
//交换L->r[j]和L->r[j+1]值;
swap(L, j, j+1);
//如果有任何数据的交换动作,则将flag改为true;
flag=TRUE;
}
}
}
}
选择排序 是表现最稳定的排序算法之一 ，因为无论什么数据进去都是O(n2)的时间复杂度 ，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序(Selection-sort) 是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
void SelectSort(SqList *L){
int i,j,min;
for (i = 1; i < L->length; i++) {
//① 将当前下标假设为最小值的下标
min = i;
//② 循环比较i之后的所有数据
for (j = i+1; j <= L->length; j++) {
//③ 如果有小于当前最小值的关键字,将此关键字的下标赋值给min
if (L->r[min] > L->r[j]) {
min = j;
}
}
//④ 如果min不等于i,说明找到了最小值,则交换2个位置下的关键字
if(i!=min)
swap(L, i, min);
}
}
插入排序（Insertion-Sort） 的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
void InsertSort(SqList *L){
int i,j;
//L->r[0] 哨兵 可以把temp改为L->r[0]
int temp=0;
//假设排序的序列集是{0,5,4,3,6,2};
//i从2开始的意思是我们假设5已经放好了. 后面的牌(4,3,6,2)是插入到它的左侧或者右侧
for(i=2;i<=L->length;i++)
{
//需将L->r[i]插入有序子表
if (L->r[i]<L->r[i-1])
{
//设置哨兵 可以把temp改为L->r[0]
temp = L->r[i];
for(j=i-1;L->r[j]>temp;j--)
//记录后移
L->r[j+1]=L->r[j];
//插入到正确位置 可以把temp改为L->r[0]
L->r[j+1]=temp;
}
}
}
希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
>希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
void shellSort(SqList *L){
int i,j;
int increment = L->length;
//0,9,1,5,8,3,7,4,6,2
//① 当increment 为1时,表示希尔排序结束
do{
//② 增量序列
increment = increment/3+1;
//③ i的待插入序列数据 [increment+1 , length]
for (i = increment+1; i <= L->length; i++) {
//④ 如果r[i] 小于它的序列组元素则进行插入排序,例如3和9. 3比9小,所以需要将3与9的位置交换
if (L->r[i] < L->r[i-increment]) {
//⑤ 将需要插入的L->r[i]暂时存储在L->r[0].和插入排序的temp 是一个概念;
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[0]插入到L->r[j+increment]的位置上;
L->r[j+increment] = L->r[0];
}
}
}while (increment > 1);
}
堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
void HeapSort(SqList *L){
int i;
//1.将现在待排序的序列构建成一个大顶堆;
//将L构建成一个大顶堆;
//i为什么是从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
for(i=L->length/2; i>0;i--){
HeapAjust(L, i, L->length);
}
//2.逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
for(i = L->length; i > 1; i--){
//① 将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
swap(L, 1, i);
//② 将L->r[1...i-1]重新调整成大顶堆;
HeapAjust(L, 1, i-1);
}
}
//大顶堆调整函数;
/*
条件: 在L.r[s...m] 记录中除了下标s对应的关键字L.r[s]不符合大顶堆定义,其他均满足;
结果: 调整L.r[s]的关键字,使得L->r[s...m]这个范围内符合大顶堆定义.
*/
void HeapAjust(SqList *L,int s,int m){
int temp,j;
//① 将L->r[s] 存储到temp ,方便后面的交换过程;
temp = L->r[s];
//② j 为什么从2*s 开始进行循环,以及它的递增条件为什么是j*2
//因为这是颗完全二叉树,而s也是非叶子根结点. 所以它的左孩子一定是2*s,而右孩子则是2s+1;(二叉树性质5)
for (j = 2 * s; j <=m; j*=2) {
//③ 判断j是否是最后一个结点, 并且找到左右孩子中最大的结点;
//如果左孩子小于右孩子,那么j++; 否则不自增1. 因为它本身就比右孩子大;
if(j < m && L->r[j] < L->r[j+1])
++j;
//④ 比较当前的temp 是不是比较左右孩子大; 如果大则表示我们已经构建成大顶堆了;
if(temp >= L->r[j])
break;
//⑤ 将L->[j] 的值赋值给非叶子根结点
L->r[s] = L->r[j];
//⑥ 将s指向j; 因为此时L.r[4] = 60, L.r[8]=60. 那我们需要记录这8的索引信息.等退出循环时,能够把temp值30 覆盖到L.r[8] = 30. 这样才实现了30与60的交换;
s = j;
}
//⑦ 将L->r[s] = temp. 其实就是把L.r[8] = L.r[4] 进行交换;
L->r[s] = temp;
}
网友评论