排序的基本知识
- 定义：排序就是将原本无序的序列重新排列成有序的序列。
排序的稳定性
- 如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
插入类排序
直接插入排序
- 直接插入排序：首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。
- 时间复杂度为O(n)
- 直接插入排序是稳定性是稳定的。
折半插入排序
- 折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。
- 折半插入排序的时间复杂度为O(n^2)
- 稳定性：和直接插入排序稳定性相同，是稳定的。
希尔排序
希尔排序的基本思想：希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序。
- ①先以增量5来分割序列，也就是下标为0,5,10,15...的关键字分成一组，下标为1,6,11,16..分成一组,然后对这些组分别进行直接插入排序，这就完成了一轮希尔排序。
- ②缩小增量(d1=n/2，di+1= [di/2]，比如10个数据序列，第一次增量d1=10/2=5,第二次增量d2= [d1/2]= [5/2]=2,并且最后一个增量等于1),所以第二轮以增量为2进行类似的排序过程。
- ③接下来的第三轮，第四轮...都是类似的过程，直到最后一轮以增量为1。此时就是前面所说的直接插入排序。
- 概要:
- 时间复杂度：... 希尔排序的时间复杂度约为O(n^1.3) 在最坏情况下希尔排序的时间复杂度为O(n^2)
- 空间复杂度：希尔排序的空间复杂度为O(1)
- 稳定性：不稳定，由于不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序， 可能就会造成相对顺序变化。
- 单链表插入排序
题目: 单链表的插入排序（升序）。
struct Node {
int data;
struct Node * next;
};
void InsertLinked(Node** sorted, Node* tmp) {
Node* cur;
// 当前插入节点是最小的值
if(*sorted == NULL || tmp->data <= (*sorted)->data) {
tmp->next = *sorted;
*sorted = tmp;
}
else { // 找到插入的位置
cur = *sorted;
while(cur->next != NULL && tmp->data > cur->next->data) {
cur = cur->next;
}
tmp->next = cur->next;
cur->next = tmp;
}
}
void InsertSort(Node** head) {
// 有序链表
Node *sorted = NULL;
Node * cur = *head;
while(cur != NULL) {
Node *next = cur->next;
// 将cur插入到sorted中，这是一个有序的链表
InsertLinked(&sorted, cur);
cur = next;
}
*head = sorted;
}
交换类排序
冒泡排序
- 假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，……，这样最多做n-1趟冒泡就能把所有元素排好序。
- 空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为O(1)
- 时间复杂度
- 稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。
快速排序
- 快速排序是一种基于分治法的排序方法。
每一趟快排选择序列中任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。
* 1
* 2
* 时间复杂度：最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。
最坏情况下时间复杂度为O(n^2)，待排序序列越有序，算法效率越低。
* 空间复杂度：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。
最好情况下为 ⌈log2(n+1)⌉(每次partition都很均匀)递归树的深度O(logn)
最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；
* 稳定性：快速排序是不稳定的，是因为存在交换关键字。选择类排序
简单选择排序
- 空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)
- 时间复杂度：
关键操作在于交换元素操作，整个算法由双重循环组成，外层循环从0到n-2一共n-2+1=n-1次，
对于第i层外层循环，内层循环执行n-1-(i+1)+1=n-i-1次。
当i=0,内层循环执行n-1次，当i=n-2,内层循环执行1次，所以是一个等差数列求和,一共为(1+n-1)(n-1)/2=n(n-1)/2 ,所以时间复杂度为O(n^2)
* 稳定性：不稳定 原因就在于交换部分会打破相对顺序堆排序
什么是堆？
堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。
* 如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。 * 如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。
什么是堆排序？
我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。
* *- 时间复杂度：
堆排序的总时间可以分为①建堆部分+②n-1次向下调整堆
堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)
- 堆排序不稳定
- 实现多路归并排序
题目: 实现常用的多路归并排序(使用最大堆，或者优先队列)
// vec中每一个vector都是有序的
vector<int> MultMerge(vector<vector<int> > vec, vector<int> &result) {
int n = vec.size();
priority_queue<int, vector<int>, greater<int> > q;
vector<vector<int>::iterator> vec_it;
for(int i = 0; i < n; i ++) {
vector<int>::iterator it = vec[i].begin();
vec_it.push_back(it);
}
for(int i = 0; i < n; i ++) {
if(q.size() < k && vec_it[i] != vec[i].end()) {
q.push(*(vec_it[i]));
}
}
while(q.size()) {
int cand = q.top();
q.pop();
result.push_back(cand);
int index = 0;
for(int i = 0; i < n; i ++) {
if(vec_it[i] != vec[i].end() && cand == *(vec_it[i])) {
index = i;
vec_it[index] ++;
break;
}
}
if(vec_it[index] != vec[index].end()) {
q.push(*(vec_it[index]));
}
}
return result;
}归并排序
假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 ⌈n/2⌉个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。
例如：49 38 65 97 76 13 27
- ①首先将整个序列的每个关键字看成一个单独的有序的子序列
- ②两两归并，49和38归并成{38 49} ，65和97归并成{65 97}，76和13归并成{13 76}，27没有归并对象
- ③两两归并，{38 49}和{65 97}归并成{38 49 65 97}，{13,76}和27归并成{13 27 76}
- ④两两归并，{38 49 65 97}和{13 27 76}归并成{13 27 38 49 65 76 97}
- 时间复杂度：O(nlog2n)
- 空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)
- 稳定性：稳定
- 单链表归并排序
题目: 单链表的归并排序。
void MergeSort(Node **head_ref) {
Node *head = *head_ref;
Node *left;
Node *right;
// 判断是否是null
if(head == NULL || head->next == NULL) {
return;
}
// 链表分成两个部分，left 和 right
split(head, &left, &right);
MergeSort(left);
MergeSort(right);
*head_ref = Merge(left, right);
}
// 左右各一半，
void split(Node *head, Node **left, Node **right) {
//1. 先计算长度n，分别选择前一半和后一半。
//2. 使用快慢指针，各取一半
int n = 0;
Node *cur = head;
while(cur != NULL) {
n ++;
}
*left = head;
int k = n / 2;
cur = head;
Node *p = NULL;
while(k--) {
p = cur;
cur = cur->next;
}
p->next = NULL;
*right = cur;
}
Node* Merge(Node *left, Node *right) {
// merge right to left
Node *head = NULL;
head->data = -1;
Node *p = head;
while(left != NULL && right != NULL) {
if(left->data <= right->data) {
p->next = left;
left = left->next;
}
else {
p->next = right;
right = right->next;
}
p = p->next;
}
if(left != NULL) {
p->next = left;
}
if(right != NULL) {
p->next = right;
}
return head->next;
}基数排序
- 基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。
例子：53, 3, 542, 748, 14, 214, 154, 63, 616
- 补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616
- 桶实际是一个队列，先进先出(从桶的上面进，下面出)
- 关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10
- 空间复杂度：需要开辟关键字基的个数个队列，所以空间复杂度为O(r)
- 时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次"分配"需要将n个关键字放进各个队列中，一次"收集"需要将r个桶都收集一遍。所以一次"分配"和一次"收集"时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。
- 稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。
外部排序
- 需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。
如何得到初始的归并段
- 置换选择排序：解决排序段放入内存的问题
如何减少多个归并段的归并次数
- 最佳归并树：最少的归并次数（I/O次数）
如何每次m路归并快速得到最小的关键字
- 败者树：减少比较次数
- 概要: 内存容量无法容纳大量数据
