Contents

1. 1. 一、插入排序
   1. 1.0.1. 1. 直接插入排序

2. 二、交换类排序

1. 2.0.1. 1. 冒泡排序
2. 2.0.2. 2. 快速排序
3. 2.0.3. 3. 选择排序
4. 2.0.4. 1. 简单选择排序

3. 四、归并排序

4. 五、分配类排序

1. 4.0.1. 1. 多关键字排序
2. 4.0.2. 2. 链式基数排序

一、插入排序

在一个有序列表内，对待排序的无序列表中记录进行逐个处理，每一步将一个待排序的记录与同组那些已经排好序的记录进行比较，然后有序插入到该有序序列表里，直到所有的待排记录全部插入为止。

实现一趟插入排序需要分三步

1. 在r[1..i-1]中查找r[i]的插入位置，
   r[ 1.j ].key < r[j].key < r[ j+1..i-1 ].key;
2. 将r[ j+1..i-1]中 的所有记录均后移个位置;
3. 将r[i] 插入(复制)到r[ j+1 ]的位置上。

1. 直接插入排序

void InsSort(RecordType r[], int length){
	int i,j;
	for(i=2;i<=length;i++){
		r[0] = r[i]; //将待插记录放入监视哨里
		j=i-1;
		while(r[0].key<r[i].key){  //寻找插入位置
			r[j+1]=r[j]
			j--
		}
		r[j+1]=r[0]  //将待插记录插入到已排序的序列中
	}
}

我觉得我需要一个pad（哈哈哈哈）

二、交换类排序

通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。
基本思想: 通过交换逆序元素进行排序的方法。

1. 冒泡排序

在扫描过程中顺次比较相邻的两个元素大小，若逆序就交换位置

void BubbleSort (RecordType r[],int length){
	n=length;change=1;
	for(i=1;i<=n-1 && change; i++){
		if(r[j].key>r[j+1].key){
			x=a[j];
			r[j]=r[j+1]
			r[j+1]=x
			change=1
		}
	}
}

2. 快速排序

快速排序是对冒泡排序的一种改进。
实现一次交换消除多个逆序

int QKpass(RecordType r[], int low, int height){
	r[0] = r[low]
	while(low<hight)
	{
		while(low<hight&&r[hight].key>=r[0].key)  --hight
		r[low] = r[hight]
		while(low<hight && r[low].key<=r[0].key) ++low
		r[hight]=r[low]
	}
	r[low]=r[0]
	return low
}

3. 选择排序

从记录得无序子序列中“选择”关键字最小或最大的记录， 并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。

①简单选择排序
②树型选择排序
③堆排序

1. 简单选择排序

vodi SelectSort(RecordType r[], int n){
	n = length;
	for(i=1;i<=n;i++){
		k=j
		for(j=i+1;j<=n;j++){
			if(r[j].key<r[k].key) k=j;
			if(k!=i){
				x=r[i];
				r[i]=r[k];
				r[k]=x
			}
		}
	}
}

   33 68 46 33 25 80 19 12 
1. 12 68 46 33 25 80 19 33
2. 12 19 46 33 25 80 68 33
3. 12 19 25 33 46 80 68 33
4. 12 19 25 33 33 80 68 46
5. 12 19 25 33 33 46 68 80
6. 12 19 25 33 33 46 68 80

四、归并排序

归并排序就是将两个或两个以上的有序序列合并成一个有序数列的过程

//递归形式的二路归并排序算法
void MSort(RecordList l, RecordList CopyL, int left, int right){
	int middle;
	if(left<right){
		middle = (left+right)/2;
		MSort(L,CopyL,left,middle);
		MSort(L,CopyL,middle+1,right);
		MSort(L,CopyL,right,middle);
	}
}

46 12 33 72 68 19 80 33//两个一份
12 46 33 72 19 68 33 80//四个一份
12 33 46 72 19 33 68 80//八个一份
12 19 33 33 46 68 72 80

五、分配类排序

1. 多关键字排序

• MSD 最高位优先 递归（洗扑克牌）
• LSD 最低位优先

2. 链式基数排序

使用就是LSD

（会持续更新）