一些概念

排序算法的稳定性：经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变。

插入排序

直接插入排序

口语描述：前面一段排序好的序列，后面一段乱序的序列，每次从乱序的第一个往前移，移到在顺序序列中比它小的元素之后。

Note：适用情况，元素数目少，或者元素的初始序列基本有序

准确描述：n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中抽出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。

代码：

#define MAXSIZE 20
typedef int Keytype;	//定义关键字为整型

typedef struct{
	KeyType key;	//关键字项
	InfoType otherinfo;	//其他数据项
}RedType	//记录类型

typedef struct{
	RedType r[MAXSIZE+1];	//r[0]闲置或用作哨兵
	int length;				//顺序表长度
}SqList;					//顺序表类型

void InsertSort(SqList &L){
	for(int i=2;i<=L.length;++i){
		//如果没有这个if条件会怎么样？ 直接
		if(L.r[i].key<=L.r[i-1].key){	
			L.r[0] = L.r[i]; L.r[i] = L.r[i-1];
			for(j=i-2; L.r[0].key<L.r[j].key;j--)
				L.r[j+1] = L.r[j];
			L.r[j+1] = L.r[0];
		}
	}
}

折半插入排序

口语描述：在直接插入排序的基础上，寻找插入位置时使用二分查找，称为折半插入排序。

代码：

void InsertSort(SqList &L){
	for(int i=2;i<=L.length;++i){
		L.r[0] = L.r[i];
		L.r[i] = L.r[i-1];
		low = 1; high = i-1;
		while(low<=high){
			mid = (low + high) / 2;
			if(L.r[mid].key<L.r[0].key)
				low = mid + 1;
			else
				high = mid - 1;
		｝
		for(int j=i-1; j>=high+1;--j){
			L.r[j+1] = L.r[j];
		}
		L.r[high+1] = L.r[0];
		
	}
}

三个需要注意的点：

1、退出条件是 low <= high 不是 low < high
2、mid的取值在数很大的时候担心溢出应采用low+(high-low)/2这种写法
3、low与high的更新：应当是low = mid+1 high = mid-1 避免死循环

希尔排序

口语描述：选一个增量，相当于把一个序列分成了分成了增量个数个子序列，举个例子，比如132456，增量为2的话，就分成了，125， 346，然后再对子序列排序。当增量足够小时，再对全体元素进行一次插入排序。

Note：希尔排序是一种不稳定的排序算法

代码（以dlta[k]为增量的希尔排序）：

// 一趟希尔排序，和直接插入的排序就是每次往前走一个，变成了每次往前走dk个
// 最后元素后移的结束条件多了一个j>0，因为现在的L.r[0]仅起到暂存作用
// L.r[0]并不是此时并不是哨兵
void ShellInsert(SqList &L, int dk){ 
	for(i=dk+1;i<=L.length;i+=dk){
		if(L.r[i].key<L.r[i-dk].key){
			L.r[0] = L.r[i];
			for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
				L.r[j+dk] = L.r[j];
			L.r[j+dk] = L.r[0];
		}
	}
}

//总共进行t趟希尔排序，每次增量为dlta[]中的元素
//这里我觉得dlta[t-1]应该是等于1，因为最后要进行一次直接插入排序嘛
void ShellSort(SqList &L, int dlta[], int t){
	for(k=0;k<t;k++){
		ShellInsrt(L, dlta[k]);
	}
}

王道代码（每次增量为dk/2）：

void ShellInsert(SqList &L, int n){
	for(int dk=n/2;dk>=1;dk=dk/2){
		for(int i=dk+1;i<=L.length;i+=dk){
			if(L.r[i].key<L.r[i-dk].key){
				L.r[0] = L.r[i];
				for(int j=i-dk;j>0&&L.r[j].key>L.r[0].key;j-=dk){
					L.r[j+dk] = L.r[j];
				}
				L.r[j+dk] = L.r[0];
			}
		}
	}
}

交换排序

冒泡排序

口语描述：相邻两个比较，若为逆序则交换。两趟for循环。第一趟用于改变第二趟比较的长短，注意，我总是分不清冒泡排序和选择排序。

void BubbleSort(SqList &L){
	// 注意，这里的flag用的很灵性，如果比较一趟，发现序列有序
	// 就不需要再进行比较了，这样省去了很多趟的比较
	for(int i=1, change=True;i<=L.length&&change;++i){
		change = False;
		for(int j=1;j<=L.length-i+1;++j){
			if(L.r[j].key>L.r[j+1].key){
				L.r[0] = L.r[j];
				L.r[j] = L.r[j+1];
				L.r[j+1] =L.r[0];
				chage = True;
			}
		}
	}
}

快速排序

口语描述：

序列中取一个元素，以这个元素为基准，把序列分成两个子序列（一半比基准元素小，一半比基准元素大）
对两个子序列重复1
重复1,2，直到整个序列有序。

代码：

void QuickSort(SqList &L, int low, int high){
	if(low < high){
		int pivotpos = Partition(L, low, high);
		QuickSort(L, low, pivotpos-1);
		QuickSort(L, pivotpos+1, high);
	}
}

int Partition(SqList &L, int low, int high){
	L.r[0] = L.r[low];
	while(low<high){
		while(low<high&&L.r[high].key>=L.r[0].key) --high;
		L.r[low] = L.r[high];
		while(low<high&&L.r[low].key<=L.r[0].key) ++low;
		L.r[high] = L.r[low];
	}
	L.r[low] = L.r[0];
	return low;
}

选择排序

简单选择排序

口语描述：每次选一个最小的数和和前面的数交换。第i趟在n-i+1个记录中选取最小的记录作为有序序列中的第i个记录。

代码：

void SelectSort(SqList &L){
	for(int i=1; i<L.length; ++i){
		for(k=i+1,j=i;k<=L.length;k++)
			if(L.r[k].key<L.r[j].key) j = k;
		if(j!=i)  swap(L.r[i],L.r[j]);
	}
}

树形选择排序

口语描述：每一轮都将序列两两进行比较，小的进入下一轮，直到选出最小的

堆排序

口语描述：堆的定义：大顶堆： $\begin{cases} K_i \geq K_{2i} \\ K_i \geq K_{2i+1} \end{cases}$

小顶堆： $\begin{cases} K_i \leq K_{2i} \\ K_i \leq K_{2i+1} \end{cases}$

void HeapSort(HeapType &H){
	for(i=H.length/2;i>0;--i)
		HeapAdjust(H, i, H.length);
	for(i=H.length;i>1;--i){
		swap(H.r[1],H.r[i]);
		HeapAdjust(H, 1, i-1);
	}
}

void HeapAdjust(HeapType &H, int s, int m){
	rc = H.r[s];
	//为什么是j<=m?
	//j<m时，j没到叶子节点
	//j=m时，j在叶子节点上，要看叶子节点和目标节点是否满足堆定义
	for(j=2*s;j<=m;j*=2){
		//为什么j<m？
		//说明j还没到叶子节点
		if(j<m&&H.r[j].key>H.r[j+1].key) ++j;	
		if(rc.key<H.r[j].key) break;
		//s永远指向上一层的结点
		//j永远指向下一层的兄弟节点中较小的那一个
		//当j没到叶子节点时，且不满足堆定义
		//将两个兄弟之间较小的直接覆盖掉s
		H.r[s] = H.[j];
		//更新指针s
		s = j;
	}
	H.r[s] = rc;
}

归并排序

将n个无需序列看成n个由长度为1的有序子序列组成的序列，然后两两归并，得到n/2个长度为2或1的有序子序列，再两两归并，知道序列有序。

归并两个顺序表

void SqList_Merge(SqList &LA, SqList &LB, SqList &LC){
	int i=0, j=0, k = 0;
	ElemType *pA = LA.r, *pB = LB.r, *pC;
	LC.length = LA.length + LB.length;
	pC = LC.r = (ElemType*)realloc(r, LC.length*sizeof(ElemType*));
	while(pA<pA+LA.length&&pB<pB + LB.length){
		if(*pA < *PB){
			*pC++ = *pA++;
		}
		else{
			*pC++ = *pB++;
		}
	}
	while(pA<pA+LA.length) *pC++ = *pA++;
	while(pB<pB+LB.length) *pC++ = *pB++;
}

归并两个单链表

void LinkList_Merge(LinkList &LA, LinkList &LB){
	LNode *pA =  LA->next, *pB = LB->next;
	LNode *pC = LA;
	while(pA!=NULL&&pB!=NULL){
		if(pA->Val < pB->Val){
			pC->next = pA;
			pA = pA->next;
		}else{
			pC->next = pB
			pB = pB->next;
		}
	} 
	if(pA!=NULL) pC->next = PA;
	if(pB!=NULL) pC->next = PB;
}

基数排序

以比较三位数为例先比较个位，按顺序排列，再比较十位，按顺序排列，最后比较百位，按顺序排列。

	时间复杂度	空间复杂度	稳定性	适用情况
直接插入排序	$O(n^2)$	O(1)	稳定	n较小，初始序列基本有序
希尔排序	$O(n^{1.3})$	O(1)	不稳定
冒泡排序	$O(n^{2})$	O(1)	稳定	n较小，初始序列基本有序
快速排序	$O(n\log_2{n})$	$O(\log_2{n})$	不稳定	初始序列无序
简单选择排序	$O(n^{2})$	O(1)	不稳定	n较小
堆排序	$O(n\log_2{n})$	O(1)	不稳定	n较大，或只排前几位
2-路归并排序	$O(n\log_2{n})$	O(n)	稳定	n很大
链式基数排序	$O(d(n+rd))$	O(rd)	稳定	n大，关键字值小

Note：快速排序在最坏的情况下退化成冒泡排序，时间复杂度为$O(n^2)$，快速排序每次递归都会返回一个中间值的位置，必须使用栈。所以空间复杂度就是栈用的空间。

这个图有问题希尔排序平均时间复杂度为$O(n^{1.3})$ 快速排序空间复杂度为$O(logn)$

On this page