排序Sort(代码与笔记)

插入排序：

void InsertionSort(int *source,int N)//升序
{
	int j, p,tmp;
	for (p = 1; p < N; p++)
	{
		tmp = source[p];
		for (j = p; j > 0 && source[j - 1] > tmp; j--)
			source[j] = source[j - 1];
		source[j] = tmp;
	}
}
void ShellSort(int *Source,int *Incrementlist,int N1)
{
	int i, j, tmp,increment,s;
	for (s = 0;; s++)
	{
		if (Incrementlist[s] > N1)
			break;
	}
	s--;
	for (increment = Incrementlist[s]; s>=0 ;s--)
	{
		for (i = increment; i < N1; i++)
		{
			tmp = Source[i];
			for (j = i; j >= increment; j -= increment)
				if (tmp < Source[j - increment])
					Source[j] = Source[j - increment];
				else
					break;
			Source[j] = tmp;
		}
	}
}
	//Hibbard:Dk=2^k-1    {1,3,7,15......}
	//Sedgewick:{1,5,19,41,109......}

堆排序：

void PercDown(int *Source,int i,int N)
{
	int Child,Tmp;
	for (Tmp = Source[i]; 2 * i + 1 < N; i = Child)
	{
		Child = 2 *i +1;
		if (Child != N - 1 && Source[Child + 1] > Source[Child])
			Child++;
		if (Tmp < Source[Child])
			Source[i] = Source[Child];
		else
			break;
	}
	Source[i] = Tmp;
}
void HeapSort(int *Source,int N)
{
	int i;
	for (i = N / 2; i >= 0; i--)
		PercDown(Source, i, N);
	for (i = N - 1; i > 0; i--)
	{
		Swap(&Source[0],&Source[i]);
		PercDown(Source, 0, i);
	}
}
void Swap(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

归并排序：

void MSort(int *A,int *TmpArray,int Left,int Right)
{
	int Center;
	if (Left < Right)
	{
		Center = (Left + Right) / 2;
		MSort(A, TmpArray, Left, Center);
		MSort(A, TmpArray, Center + 1, Right);
		Merge(A, TmpArray, Left, Center + 1, Right);
	}
}
void Mergesort(int *A,int N)
{
	int* TmpArray;
	try
	{
		TmpArray = new int[N];
		MSort(A, TmpArray, 0, N - 1);
		delete TmpArray;
	}
	catch (const bad_alloc& e)
	{
		exit;
	}
}
void Merge(int A[],int TmpArray[],int Lpos,int Rpos,int RightEnd)
{
	int i, LeftEnd, NumElements, TmpPos;
	LeftEnd = Rpos - 1;
	TmpPos = Lpos;
	NumElements = RightEnd - Lpos + 1;
	while (Lpos<=LeftEnd&&Rpos<=RightEnd)
		if (A[Lpos] <= A[Rpos])
			TmpArray[TmpPos++] = A[Lpos++];
		else
			TmpArray[TmpPos++] = A[Rpos++];
	while (Lpos <= LeftEnd)
			TmpArray[TmpPos++] = A[Lpos++];
	while (Rpos <= RightEnd)
			TmpArray[TmpPos++] = A[Rpos++];
	for (i = 0; i < NumElements; i++, RightEnd--)
			A[RightEnd] = TmpArray[RightEnd];
}

图解参考：https://www.cnblogs.com/chengxiao/p/6194356.html

快速排序：

#define Cutoff 2//规定操作的左右范围长度
void Quicksort(int *Source,int N)//驱动例程
{ Qsort(Source, 0, N - 1); }
int Median3(int *A,int Left,int Right)
{
	int Center = (Left + Right) / 2;
	if (A[Left] > A[Center])
		Swap(&A[Left], &A[Center]);
	if (A[Left] > A[Right])
		Swap(&A[Left], &A[Right]);
	if (A[Center] > A[Right])
		Swap(&A[Center],&A[Right]);
	Swap(&A[Center], &A[Right - 1]);
	return A[Right - 1];
}
//获取中位数(首位，中位，末位)
void Qsort(int *A,int Left,int Right)//实际例程
{
	int i, j, Pivot;
	if (Left + Cutoff <= Right)
	{
		Pivot = Median3(A, Left, Right);
		i = Left; j = Right - 1;
		for (;;)
		{
			while (A[++i] < Pivot){}
			while (A[--j] > Pivot){}
			if (i < j)
				Swap(&A[i], &A[j]);
			else
				break;
		}
		Swap(&A[i], &A[Right - 1]);
		Qsort(A, Left, i - 1);
		Qsort(A, i + 1, Right);
	}
	else
		InsertionSort(A + Left, Right - Left + 1);
}
void Qselect(int A[],int k,int Left,int Right)
{
	int i, j, Pivot;
	if (Left + Cutoff <= Right)
	{
		Pivot = Median3(A, Left, Right);
		i = Left; j = Right - 1;
		for (;;)
		{
			while (A[++i] < Pivot) {}
			while (A[--j] > Pivot) {}
			if (i < j)
				Swap(&A[i], &A[j]);
			else
				break;
		}
		Swap(&A[i], &A[Right - 1]);
		if(k<=i)
			Qselect(A, k, Left, i - 1);
		else if(k>i+1)
			Qselect(A, k, i + 1, Right);
	}
	else
		InsertionSort(A + Left, Right - Left + 1);
}
int QuickSelect(int* Source, int k,int N)
{
	Qselect(Source, k, 0, N - 1);
	return Source[k-1];
}

     快速排序的图解请移步其他大佬，这里主要是梳理一遍其排序过程，对一些晦涩的地方做出些许标记。

    ①首先从驱动例程进入。Left和Right分别标记为数组的左右端点。声明必要的常量。

   （注：Cutoff常量能够决定“左右端点的间距”。之所以要这样做，是因为递归算法在大量数据的排序过程中虽然很方便，但从汇编的角度却不可避免的需要不停地入栈出栈，对于一些小规模数据的排序来说，这是一种浪费。所以当排序的数据量低于Cutoff的时候，选用另外一种更加简单的非递归算法要比原先的递归算法来得更加效率）

    ②Pivot取 首/中/末 位的中位数，并将i标记位Left(左端点)，j标记为Right-1(最大索引数)

    (注：Pivot的取值实际上是越接近全数组的中位数越好，因为这样可以尽可能的将数组拆分为同样大小的另外两个数组，从结论上来说，如果每一次都能等分，那么递归的次数是最少的，因此也是最快的。但在实际中，选取中位数是困难的一件事，所以只能大致取一个靠近中位数的来替代它。且还需要避免一些最糟糕的情况，比方说全数组的元素都相同，那么数组的分割将会毫无意义，又或者数组已经排好了序之类的。经过衡量，对于那些随机的投放元素的数组，这种取法能够尽可能的靠近中位数。)

    (注：已经另外一个需要注意的是，Median3函数将选出的Pivot放在了A[Right-1]的位置，这样做能避免之后出现关键字与Pivot相同的时候进行的额外的操作)

    ③进入循环，直到 i 标记越过或是与 j 标记重叠。期间，在第一个while循环中，当 A[i]>Pivot的时候将会停下，同理的，j标记也是一样。最后将两个元素进行交换。

    ④直到 i 标记与 j 标记重叠或越过后，将现在 i 标记所指的单元与Pivot交换。那么，现在 i 标记的左边的所有值都将小于Pivot，右边所有值都将大于Pivot。

    ⑤对 i 标记 左边的所有值进行同样的排序操作，结束后再对右边同理进行排序。

    (注：最终必然会依靠插入排序对剩下的元素进行排序，请不要忘记这一点来观察图解)

快速选择：

(以选出数组中第 k 大/小 的数为例)

    从快速排序中派生出的算法。基本上同上面一样，但速度还能更快，因为它不需要对整个数组进行排序。

    上述的第⑤步，只需要先判断我们选取的值是在Pivot左边还是Pivot的右边，然后排序所在的那一侧，就能顺利的选出目标。这样会减少很多操作，所有速度能更快。

桶排序：

    对于任何一种需要比较的排序算法，其最优的时间下界也在NlogN处，但如果已知了一部分的信息，甚至能将这个时间优化为近乎线性，这便是桶排序的一种想法。对于已知的数据量上下界，为其建立好一个个桶，每遇到一个元素，就将其放进相应的桶里，最后来统计桶中的球的数量。但即便这样还是有些抽象，建议看一些大佬们画的图解。

    以及有的时候，我们的数据块并不是整数，而是一个个非常大的节点。它们无法全都装到内存里面去，所有如果仍然执行交换操作，将会浪费非常多的时间在这里。一种简单的操作方法是，为这些数据建立一个指针数组，数组的第一格存放的指针指向最小的数据块，第二格，第三格......

    这样，在需要排序的时候，我们实际只需要排序指针的位置，而不需要移动数据本来的位置。从而能减少很多时间。

    如下代码是我自己写的桶排序与外部排序的结合，通过链表的方式实现。

全代码：

typedef struct Queue* Position;
typedef struct Node* pNode;
struct Node
{
	int Key;
	pNode Next;
};
struct Queue
{
	pNode Data;
};
Position BucketSort(Node *A,int Size,int MaxNumber)
{
	Position P;
	P = new Queue[MaxNumber];
	pNode tmp;
	for (int i = 0; i < MaxNumber; i++)
		P[i].Data = NULL;
	for (int i = 0; i < Size; i++)
	{
		tmp = P[A[i].Key].Data;
		while (tmp->Next)
			tmp = tmp->Next;
		tmp->Next = &A[i];
		tmp->Next->Next = NULL;
	}
	return P;
}

    不是很复杂，主要是针对[0,MaxNumber）区间的一系列能够依靠整数关键字来排序。

基数排序：(算是桶排序的变种)

    原理并不复杂。最低位的次序关系将会在其高位的排序中保留下来。

    基础的这种算法只能用于排序整数。并且如果算法设计的不是很好，MSD(最高位优先)很可能不稳定。以下代码位LSD(最低位优先)。

int MaxGet(int *Source,int N)
{
	int tmp=0;
	for (int i = 0; i < N; i++)
	{
		if (Source[i] > tmp)
			tmp = Source[i];
	}
	return tmp;
}
int BitGet(int A)
{
	int d = 0;
	while (A > 0)
	{
		A /= 10;
		d++;
	}
	return d;
}
void RadixSort(int *Source,int N)//Least Significant Digit
{
	int MaxNumber = MaxGet(Source,N);
	int Bit = BitGet(MaxNumber);
	int* tmplist = new int[N];
	int* Count = new int[10];
	int k = 0,radix = 1;
	for (int i = 0; i <= Bit; i++)
	{
		for (int j = 0; i < 10; j++)
			Count[j] = 0;
		for (int j = 0; j < N; j++)
		{
			k = (Source[j]/radix) % 10;
			Count[k]++;
		}
		for (int j = 1; j < 10; j++)
			Count[j] = Count[j - 1] + Count[j];
		for (int j = N-1; j >=0; j++)
		{
			k = (Source[j]/radix) % 10;
			tmplist[Count[k] - 1] = Source[j];
			Count[k]--;
		}
		for (int j = 0; j < N; j++)

			Source[j] = tmplist[j];
		radix *= 10;
	}
	delete[]tmplist;
	delete[]Count;
}

    ①首先获取整个数组中最高的数位(比如最大有1000，那Bit就应该为4)

    ②建立临时数组tmplist和计数器Count。声明变量。

    ③进入循环。Count初始化，并统计最低位为 k 的数的个数。

    ④将Count中保存的个数转换为对应的tmplist中的索引编号

    (比方说，Count[0]=2,Count[1]=3。那最低位为0的数就应该摆在tmplist[0~1],而最低位为1的数则在tmplist[2~4]。将计算好的Count[j]-1就是低位相同的数的最高储存索引(比如说tmplist[0~5],那它就会把6存在Count里))。

    ⑤将每一个数全都按照低位的大小排入tmplist，并将tmplist数据复制到Source中(如果不吝啬代码的长度，可以改为两个数组的交替使用，可以在一定程度上再提高一点效率)。

    ⑥再按照第二位重复如上操作，直到最高位也结束排序。最后将tmplist和Count的空间都释放掉