bGZo's Notes

7 min read

排序

Note

是一个升序序列， 是一个降序序列；

constexpr bool operator()(const T &lhs, const T &rhs) const
{
    return lhs > rhs; // assumes that the implementation uses a flat address space
}

计较类排序

交换排序

1. 冒泡排序

void bubbles(int p[], int m) {
  int i, j;
  for (i = 0; i < m; i++) {
	for (j = i + 1; j < m - 1; j++) {
	  if (p[i] < p[j]) swap(p[i], p[j]);
	}
  }
}

2. 快速排序

int* p;
void qsort(int l, int r) {
  int mid = p[(l + r) / 2];
  int i = l, j = r;
  do {
	while (p[i] < mid) i++;
	while (p[j] > mid) j--;
	if (i <= j) {
	  swap(p[i], p[j]);
	  i++;
	  j--;
	}
  } while (i <= j);//注意等号
  if (l < j) qsort(l, j);//递归搜索左半部分
  if (i < r) qsort(i, r);//递归搜索右半部分
}

插入排序

3. 简单插入排序

从第二个元素开始，依次比较大小，小的去前面，大的去后面，采用的方式是最低效的平移数组，针对于基本有序的数列很高效。

void InsertSort(int p[], int start, int end) {
  for (int i = start + 1; i < end; i++) {
int temp = p[i];//相当于一个容器，将无序数列的第一个元素取出
int j = i - 1;//作为有序数列的最后一个元素
while (j > 0 && temp < p[j]) {
  p[j + 1] = p[j];
  j--;
}
p[j + 1] = temp;
  }
}

4. 希尔排序 → 缩小增量

作为插入排序的改进版,，先分组进行排序使得数列基本有序，再用插入排序进行排序。

void Shellsort(int p[], int len) {
  for (int i = len / 2; i < len; i /= 2) {
		for (int j = i; j < len; j++) {
			int temp = i;
			while (temp - j >= 0 && p[temp] < p[temp - j]) {
				swap(p[temp], p[temp - j]);
				temp -= i;
			}
		}
  }
}

选择排序

5. 简单选择排序

void selections(int p[], int m) {
  int k, i, j;
  for (i = 0; i < m; i++) {
	k = i;
	for (j = i + 1; j < m - 1; j++) {
	  if (p[k] > p[j]) k = j;
	  //是p[k]而不是p[q]的原因：因为一找到比他大的就赋值，会导致最后交换的不是最大的数的后果。这样才会记录最大值。最后用于交换！！
	}
	if (k != i)swap(p[i], p[k]);
  }
}

6. 堆排序 (Heap) → 优先队列

利用堆这种数据结构所设计的一种排序算法. 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点.

#include <iostream>
#include <queue>
int main() {
  std:priority_queue<int>q;        //优先队列
  for (int i = 1; i <= 5; i++) q.push(i);
  for (int i = 0; i < 5; i++) {
	std:cout << q.top() << std:endl;
	q.pop();
  }
  return 0;
}

归并排序

7. 二路归并排序

运用递归化简到两两排序和二分归并

int a[10] = { 13 , 27 , 19 , 2 , 8 , 12 , 2 , 8 , 30 , 89 };
int b[10];
void Merge(int a[],int s,int m,int e,int tmp[]) {
  int pb = 0;
  int p1 = s, p2 = m + 1;
  while (p1 <= m && p2 <= e) {
if (a[p1] < a[p2]) tmp[pb++] = a[p1++];
else tmp[pb++] = a[p2++];
  }
  while (p1 <= m) tmp[pb++] = a[p1++];
  while (p2 <= e) tmp[pb++] = a[p2++];
  for (int i = 0; i < e - s + 1; i++) a[s+i] = tmp[i];
}
void MergeSort(int a[], int s, int e, int tmp[]) {
  if (s < e) {
int m = (s + e) / 2;//向下取整得到m=s或写作 m=s + (e - s) / 2;
MergeSort(a, s, m, tmp);
MergeSort(a, m + 1, e, tmp);
Merge(a, s, m, e, tmp);
  }
}
int main() {
  int size = sizeof(a) / sizeof(int);
  MergeSort(a, 0, size - 1, b);
  for (int i = 0; i < size; ++i)cout << a[i] << " ";
  return 0;
}

8. 多路归并排序

TODO

非比较类排序

TODO

9. 计数排序

TODO

10. 桶排序 (Bucket)

适用于待排序数据值域较大但分布比较均匀的情况

CPP stl 库的 Set 天然自带排序功能：

#include <iostream>
#include <set>
using namespace std;
set<int> s;
int a[105];
int main(){
	cin>>a[0];
	  //a[0] means the array size, to decrease paras of function calling
	for(int i=1;i<=a[0];i++){
	  cin>>a[i];
	  s.insert(a[i]);
	}
	cout<<s.size()<<endl;
	while(s.size()!=0){
		cout<<*s.begin()<<" ";
		s.erase(s.begin());
	}
	cout<<endl;
	return 0;
}
方法效果
begin()返回 set 容器的第一个元素的 地址
end()返回 set 容器的最后一个元素 地址
clear()删除 set 容器中的所有的元素
empty()判断 set 容器是否为空
max_size()返回 set 容器可能包含的元素最大个数
size()返回当前 set 容器中的元素个数
erase(it)删除迭代器指针 it 处元素
insert(a)插入某个元素

11. 基数排序

TODO

时空复杂度速记

NOTE

不稳定：希快选堆

延伸

证明

快速排序

Worst-case running time

表示完成一次交换需要的时间

Best-case running time

(Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis)

多路归并排序

  • 路归并排序， 个归并段
  • 复杂度

Sort with cpp

#include<algorithm>
#mark:  sorts(p,m) sort(p,p+m);
sorts(p,m);//此处只做参考，具体使用的时候再做打算
//sort ( start , end , cmp(compare) )
//start表示要排序数组的起始地址；
//end表示数组结束地址的下一位；
//cmp用于规定排序的方法，可不填，默认升序。

References

Graph View

Backlinks