排序算法 - 数据结构 | CLee = CL&love = 厚积而薄发，博观而约取。

# 排序

几个口诀：

1. 考研复习痛苦啊，情绪不稳定（不稳定算法），** 快（快速）些（希尔）选（简单选择）一堆（堆）** 好友来聊天吧。

2. 时间复杂度计算：

快（快速）些（希尔）以 nlogn 的速度归 (归并) 队（堆）
基数排序：O (d (n+rd))
快速排序最坏的情况下（有序）：O（n²）
除此之外的其他算法都是 O (n²)

3. 空间复杂度的计算：

快：O（log2n）
归：O (n)
基数：O (rd)
其他均为 O (1)

# 折半插入

	// 折半插入
	// 要点：首先查找出每一次循环中，哪一个节点的位置需要变换
	// 然后，再将元素后挪，最后 A [height+1] = temp; 即可完成将待插入节点有序化。

	void BibleSort(int A[],int n){
	int i,j;
	int mid;
	int temp;
	int low,height;
	for(i = 1;i<n;i++){
	temp = A[i];
	low = 0;
	height = i-1;
	while(low<height){
	mid =(low+height)/2;

	if(A[mid]>A[i]){
	// 去左表查找待插入的点的位置
	height = mid-1;
	}else{
	low = mid+1;
	}
	}
	//j 仅用于将元素后移
	for(j = i-1;j>height;j--){
	A[j+1] = A[j];
	}
	A[height+1] = temp;
	}

	}

# 冒泡排序

	// 冒泡排序（本例实现增序排列）
	// 要点：
	// 1. 从最底部开始两两比较，若要求增序排列将较小值和较大值进行位置交换
	// 2. 边界性判定，当前序列已经有序时，可直接返回，故可利用 flag 来判断当前序列是否有序
	void BubbleSort(int A[],int n){
	int i,j,k;
	int temp;
	for(i = 0;i<n;i++){
	bool flag = false;// 方便当当前序列已经有序时，无需进行如下排序
	for(j = n-1;j>i;j--){
	if(A[j]<A[j-1]){
	temp = A[j-1];
	A[j-1] = A[j];
	A[j] = temp;
	flag = true;//flag 为 true 表示发生了交换
	}
	}
	}
	if(flag == false){
	return;// 当没有发生交换时，说明该表已经有序；
	}
	}

# 双向冒泡排序

	// 双向冒泡算法
	// 奇数趟的时候从前往后把关键字最大的数放在最后面
	// 偶数趟的时候从后往前把关键字最小的数放在前面
	/* 无论是单向的冒泡还是双向的冒泡都需要设置一个 flag 变量
	目的都是为了：优化算法，提升效率从第一个位置开始没有发生交换，
	说明后座都已经被对应实力的大数占完，不必再为大数找后座了
	*/



	void swap(int x,int y){
	int temp;
	temp = x;
	x = y;
	y = temp;
	}
	void DoubleBubbleSort(int A[],n){
	int low = 0,height = n-1;
	int i = 0,j = 0;
	bool flag = true;
	while(low<height&&flag){
	for(i = low;i<height;i++){
	if(A[i]>A[i+1]){
	swap(A[i],A[i+1]);
	flag = true;
	}
	}
	height--;// 因为将 flag 变换了之后需要重新设置后座终点
	for(j = height;j>low;j--){
	if(A[j]<A[j-1]){
	swap(A[j],A[j-1]);
	flag = true;
	}
	}
	low++;
	}
	}

# 简单选择排序

	// 简单选择排序
	// 主要思路：
	//1. 每次从当前节点的后续序列中选出一个最小关键字为止 min
	//2. 将当前节点的位置 i 和 min 进行 swap 交换，直到只剩下最后一个元素为止

	void EasySelect(int A[],int len){
	int i = 0;
	int min = 0;
	for(i = 0;i<len-1;i++){
	min = i;
	for(int j = i+1;j<len;j++){
	if(A[j]<A[min]){
	min = j;
	}
	}
	}

	if(min!=i){
	int temp = A[i];
	A[i] = A[min];
	A[min] = temp;
	}
	}

# 快速排序

	// 快速排序
	// 简而言之：
	//1、挖坑填数（划分策略）+ 分治

	// 主要思路：
	// 1、每次选取一个基准元素，先从后往前找出第一个比他小或等于他的数，然后挖出该数，覆盖基准元素，空出来该数所在的位置；
	// 2、再从前往后往前扫描，找出第一个大于基准元素的数，填补 1 中的空缺位置。
	// 3、循环往复执行，直到 low = heigh 为止时，把 baseElem 填补到当前的 A [i] 中


	void FastSort(int A[],int n,int low,int height){
	int i = low;
	int j = height
	int baseElem = A[low];
	while(low<height){
	// 找到第一个比 baseElem 小的元素
	while(baseElem>=A[j-1]){
	j--;
	}
	// 挖坑
	if(i<j){
	A[i] = A[j];// 因为 i=low，A [low] 也就相当于用 A [j] 覆盖基准节点，
	// 因为基准节点是变动的，所以这里我们采用的是 A [i] = A [j]
	j--;
	}
	while(baseElem<A[j-1]){
	i++;
	}
	// 填坑
	if(i<j){
	A[j] = A[i];// 这里就相当于填坑，填补刚刚因为覆盖基准元素而缺失的位置。
	}
	A[i] = baseElem;// 最后一步，i = j; 无需分治了，故直接将 “四处飘摇” 的 baseElem 赋给 A [i]
	}
	}

# 直接插入排序

	// 直接插入排序

	// 每趟将一个待排序的关键字按照其值的大小插入到
	// 已经排好序的部分有序序列的适当位置
	//
	// 49 38 65 97 76 13 27 49
	void InsertSort(int A[],int length){
	int i,j;
	int guard = 0;// 哨兵元素
	for(i = 1;i<=n;i++){
	if(A[i]<A[i-1]){
	guard = A[i];s
	for(j = i-1;guard<A[j];--j){
	A[j+1] = A[j];// 从前往后挪位
	}
	A[j+1] = guard;// 这里是 A [j+1] = temp; 原因在于，直接插入时，往后挪，
	// 一直挪到目标位置为止，而折半插入往后挪，仅仅是为了将无关节点向后挪，空出元素应该插入的位置
	// 而折半插入是 A [height+1] = temp
	}
	}
	}

# 归并排序

	// 归并排序
	// 要点：
	//1、先对左边进行递归排序，然后再对右边进行递归排序
	//2. 最后再将二者的数组进行合并


	void MergeSort(int low,int height,int A[]){
	if(low<height){
	int mid = (low+height)/2;
	MergeSort(low,mid,A[]);// 左边进行递归排序
	MergeSort(mid+1,height,A[]);// 右边
	Merge(low,mid,height,A[]);// 最后将左右两边的数组进行合并
	}
	}

	void Merge(int low,int height,int mid,int A[]){
	int B = (int )malloc(sizeof(int)*n+1);
	for(int k = low;i<height;i++){
	B[k] = A[k];// 这里其实相当于对数组 B 进行初始化
	}
	// 疑问点：为什么这里非得用 k 来代替 i 来 ++
	//i 为 low，j 为 mid+1，对这段范围内的数组进行排序，
	// 其目的主要是为了区分开 B 中的指针 i 与 A 中的指针 k，即使他们为同一物
	// 只不过所从事的领域不一样，i 在 B 中的左边进行遍历，j 在 B 的右边进行遍历，k 在 A 中进行遍历
	for(int i = low,int j = mid+1,k = i;j<height&&i<mid;k++){
	if(B[i]>B[j]){
	A[k] = B[j++];// 排序，将较小值放回在 A 中的正确位置
	}else{
	A[k] = B[i++];
	}
	}

	while(i<=mid){
	// 说明左边的表没有被遍历完，所以直接将左边的表加在 A 表之后即可
	A[k++] = B[i++];
	}

	while(j<=height){
	// 说明右边的表没有被遍历完，所以直接将左边的表加在 A 表之后即可
	A[k++] = B[j++];
	}
	}

# 希尔排序

	// 希尔排序算法（递增排序）
	// 简而言之：
	//1. 每一次都选一定数量的元素，每次序列的表头和表尾进行比较，选取较小的那个
	//(不是线性的比较，更像是滑动窗口中首位元素的比较)，每次的序列长度可选 (d/2) 向下取整
	//2. 然后逐次将每次的序列长度 ÷2 向下取整，重复 1 中操作


	void ShellSort(int A[],int n){
	int i,j;
	int d = n/2;
	int temp;
	for(d = n/2;d>=1;d = d/2){
	// 步长变化
	for(i = d;i<n;i++){
	temp = A[i];
	j = i-d;
	// 当表尾元素 temp 大于表头元素 A [j] 时，无需进行交换，采用滑动窗口进行正常移动，
	// 以便于需要交换时直接找到要插入的节点 j
	while(j>0&&temp<A[j]){
	A[j+d] = A[j];// 记录后移，相当于窗口滑动
	j = j-d;
	}
	A[j+d] = temp; // 加 d 的原因在于，这个滑动窗口不是从上到下，而是从下到上进行查找的
	// 当发现需要交换时，已经 - d 了，所有需要返回上一步，进行赋值。
	}
	}
	}

# 堆排序

# 小根堆

	// 将数组构造为小根堆

	void MinHeap(int Arr[],int len){
	for(int i = len/2;i>0;i--){
	createHeap(Arr,i,len);// 逐层进行构建小根堆
	}
	}

	void createHeap(int Arr[],int k,int len){
	//k 代表的是根节点
	A[k] = A[0];// 初始化根节点
	for(int i = i*2;i<len;i++){
	if(i<len&&A[i]>A[i+1]){
	// 需要注意的是无论是大根堆还是小根堆，都要用 i++;
	i = i++;// 选择左右子树中最小的那个下标
	}
	if(A[0]<A[i]){
	// 当根节点比所有元素都小的时候，无需比较说明已经形成了小根堆
	break;
	}else{
	A[k] = A[i];
	k = i;
	}
	}
	A[k] = A[0];
	// 将元素放置在他最后该去的位置
	}

	void HeapSort(int Arr[],int len){
	// 将堆化后的数组进行堆排序
	BuildMaxHeap(Arr,len);
	for(int i = len;i>1;i--){
	// 输出栈顶元素，和栈底元素进行交换
	// 为什么要这样？
	//
	swap(A[i],A[1],Arr)// 将根节点 A [1] 和尾部节点 A [i] 进行交换
	createHeap(Arr,1,i-1);
	}
	}
	// 将栈顶和栈底元素进行交换是为了将大的元素始终放在位于根节点的位置
	void swap(int i,int j,int Arr[]){
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
	}

# 大根堆

	// 将数组调整为大根堆

	// 首先明白两个要点
	// 1. 当孩子节点为 2i 时，其父亲节点为 i
	// 2. 对堆排序的遍历，主要是采用节点除 2 的形式来找到下一层的左右孩子
	void MaxHeap(int Arr[],int len){
	// 纠正：从 len/2 开始，反复调整堆，因为堆是二叉数，需要比较的不是 len 次，而是 len/2 次
	for(int i = len/2;i>0;i--){
	createHeap(Arr,i,len);
	}
	}

	void createHeap(int Arr[],int k,int len){
	//k 是代表着根节点的下标
	A[k] = A[0];
	for(int i = i*2;i<len;i++){
	//i 代表着的是孩子们所在的下标（可以说左孩子也可以说右孩子）
	if(i<len&&A[i+1]>A[i]){
	// 选出 A [k] 根节点的左右节点中最大的那个数作为左孩子，并记录他的下标为 i
	i++;
	}
	if(A[0]>A[i]){
	// 说明根节点已经比任何子元素都要大了，则无需比较
	break;
	}else{
	// 否则，进行下层的遍历，更换下一层的根节点值为上层查找中权值最大的点
	A[k] = A[i];
	k = i;// 同时将根节点下标也进行更改
	}
	}
	// 这里是易错点，主要是将最后一个元素放回他该去的位置，只不过刚刚好这里他该区的位置为 k
	A[k] = A[0]
	}

	void HeapSort(int Arr[],int len){
	// 将堆化后的数组进行堆排序
	BuildMaxHeap(Arr,len);
	for(int i = len;i>1;i--){
	// 输出栈顶元素，和栈底元素进行交换
	// 为什么要这样？
	//
	swap(A[i],A[1],Arr)// 将根节点 A [1] 和尾部节点 A [i] 进行交换
	createHeap(Arr,1,i-1);
	}
	}
	// 将栈顶和栈底元素进行交换是为了将大的元素始终放在位于根节点的位置
	void swap(int i,int j,int Arr[]){
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
	}

# 应用

	// 采用快速排序将数组中所有奇数放在所有偶数的前面

	void OddFrontEven(int A[],int len){
	int i = 0;
	int j = len-1;
	while(i<j){
	while(i<j&&A[i]%2 !=0){
	i++;
	// 从前往后查找出第一个偶数
	}
	while(i<j&&A[j]%2 ==0){
	j--;
	// 从后往前查找出第一个奇数
	}
	if(i<j){
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
	}
	i++;
	j--;// 更新上界和下界
	}
	}





	我的方法不知道对不对<\|>，先把答案的写出把
	// void OddFrontEven(int A[],int n,int low,int height){
	// int i = low;
	// int j = height;
	// while(low<height){
	// // 先从后往前查找奇数
	// while(A[j]%2 != 0){
	// j--;
	// }
	// if(i<j){
	// A[i] = A[j];
	// j--;
	// }
	// // 再从前往后查找偶数
	// while(A[i]%2 == 0){
	// i++;
	// }
	// if(i<j){
	// A[j] = A[i];
	// i++;
	// }
	// }
	// }

# 简答题

1. 快速排序的基本思想以及他不适合用于什么场合

答：快速排序算法是基于分治策略的排序算法。

该方法的基本思想是：

先从数列中取出一个数作为基准数，记为 x。
分区过程，将不小于 x 的数全放到它的右边，不大于 x 的数全放到它的左边。（这样 key 的位置左边的没有大于 key 的，右边的没有小于 key 的，只需对左右区间排序即可）
再对左右区间重复第二步，直到各区间只有一个数
在关键字已经基本有序的情况下，快速排序法不能体现出其优越性

排序算法

# 排序

# 折半插入

# 冒泡排序

# 双向冒泡排序

# 简单选择排序

# 快速排序

# 直接插入排序

# 归并排序

# 希尔排序

# 堆排序

# 小根堆

# 大根堆

# 应用

# 简答题

图的算法

数组矩阵