排序是数据处理过程中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作：比较和移动。比较值关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置。事实上，移动可以通过改变记录的存储方式来避免。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2.辅助空间

评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

3.算法的复杂性

这里指的是算法本身的复杂度，而不是算法的时间复杂度，显然算法过于复杂也会影响排序的性能。

根据排序过程中借助的主要操作，我们把内排序分为：插入排序，交换排序，选择排序，和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至他们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多并不是为了实现中的编程排序算法，而是通过学习来提高我们编写的算法的能力，以便于解决更多的复杂和灵活的应用性问题。

4.排序用到的结构体和函数


const int MaxSize = 10;
typedef struct List
{
	int r[MaxSize];
	int length=MaxSize;
}List,*sqList;

另外，由于排序最常用的是两元素交换函数，直接写成函数。


void swap (sqList *L ,int i ,int j)
{
  int tmp = L->r[i];
  L->r[i]=L->r[j];
  L->r[j]=tmp;
}

冒泡排序

排序原理

冒泡排序（BUbble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。

代码

代码1


void Bubble_sort_0(sqList L)
{
	int i, j;
	for (i = 0; i < L->length-1; i++)
	{
		for (j = i + 1; j <= L->length-1; j++)
		{
			if (L->r[i] > L->r[j])
			{
				Swap(L, i, j);
			}
		}
	}
}

这段代码严格意义上讲，不是标准的冒泡排序，因为不满足冒泡排序的原理，它应该是最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。如图，假设我们待排序的关键字序列
是{9,1,5,8,3,7,4,6,2}，当i=1时，9与1交换后，在第一位置的1与后面的关键字比较都小，因此它就是最小值。当i=2 时，第二位置先后由9换成5,换成3,换成2,完成了第二小的数字交换。后面的数字变换类似。

代码2（正宗的冒泡排序）


void Bubble_sort_1(sqList L)
{
	int i, j;
	for (i = 0; i < L->length-1 ; i++)//注意：j是从后往前循环
	{
		for (j = L->length - 1 - 1; j >= 0; j--)
		{
			if (L->r[j] > L->r[j + 1])
			{
				Swap(L, j, j+1);
			}
		}
	}
}

依然假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}，当i=1时，变量j由8反向循环到1,逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第1的位置。如图，当i=1、j=8 时，我们发现6>2,因此交换了它们的位置，j=7时，4>2，所以交换....直到j=2时，因为1<2，所以不交换。j=1时，9>1, 交换，最终得到最小值1放置第一的位置。事实上，在不断循环的过程中，除了将关键字1放到第一的位置，我们还将关键字2从第九位置提到了第三的位置，显然这一算法比前面的要有进步，在上十万条数据的排序过程中，这种差异会体现出来。图中较小的数字如同气泡般慢慢浮到上面，因此就将此算法命名为冒泡算法。

代码3（冒泡排序的优化）


void Bubble_sort_3(sqList L)
{
	int i, j;
	bool flag = true;
	for (i = 0; i < L->length - 1&&flag; i++)
	{
		flag = false;
		for (j = L->length - 1 - 1; j >= 0; j--)
		{
			if (L->r[j] > L->r[j + 1])
			{
				Swap(L, j, j + 1);
				flag = true;
			}
		}
	}
}

这样的冒泡程序是否还可以优化呢?答案是肯定的。试想一下，如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i=1时，交换了2和1,此时序列已经有序，但是算法仍然不依不饶地将i=2到9以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了。

所以我们增加标记变量flag避免有序的情况下无意义的循环；

冒泡排序复杂度分析

时间复杂度：

最好的情况：排序的表本身就是有序的，那么比较次数，推断出 n-1;

最坏的情况：逆序的情况下O(n^2);

空间复杂度：

O(1)
稳定性：

稳定的:（不存在跳跃交换）

简单选择排序

冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢?这就是选择排序法的初步思想。

排序原理

选择排序的基本思想是每一趟在n-i+ 1(i=1,2...,n - 1)个记录中选取关键字最小的记录作为有序序列的第i个记录。我们这里先介绍的是简单选择排序法。

代码


void SelectSort(sqList L)
{
	int i, j ,min;
	for (i = 0; i < L->length - 1; i++)
	{
		min = i;
		for (j = i + 1; j <= L->length - 1; j++)
		{
			if (L->r[min] > L->r[j])
				min = j;
		}
		if (i != min) Swap(L, i, min);
	}
}

代码应该说不难理解，针对待排序的关键字序列是{9,1,5,8,3,7,4,6,2},对i从1循环到8。代码运行如图：

简单排序复杂度分析

时间复杂度：

无论最好最坏的情况，比较次数一样多。O(n^2)。

空间复杂度：

O(1)

稳定性：

稳定；

直接插入排序

排序原理

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。

代码

代码1


void  InertSort(sqList L)
{
	int i, j;
	for (i = 2; i < L->length; ++i)
	{
		if (L->r[i] < L->r[i - 1])
		{
			L->r[0] = L->r[i];
			for (j = i - 1; L->r[j] > L->r[0]; --j)
			{
				L->r[j + 1] = L->r[j];
			}
			L->r[j + 1] = L->r[0]; 
		}
	}
}

该方法牺牲数组第一个元素，使得0下标为哨兵。

1、直接看红线右边假设第一个位置有序从第二个位置开始比较排序所以下标从2开始。

代码2


void InsertSort(sqList L)
{
	int count = 0;
	int tmp;
	int j;//将j的生存周期提高，保证break后的的代码arr[j+1] = tmp;有效
	for (int i = 1; i < L->length; i++)//每次从待排序队列中取的值
	{
		tmp = L->r[i];//用tmp保存待插入的值
		for (j = i - 1; j >= 0; j--)//从右向左找不比tmp大的值
		{
			if (L->r[j] > tmp)//如果比tmp大  则向右放一格
			{
				L->r[j + 1] = L->r[j];
				count++;
			}
			else//如果不比tmp大
			{
				break;
			}
		}
		L->r[j + 1] = tmp;
	}
}

直接插入排序复杂度分析

时间复杂度

O(n^2)

空间复杂度

最好的情况

排序的本身就是有序的，那么比较的次数就是每次L->r[i]>L->r[r-1]也就是n-1次所以时间复杂度：o(n);

最坏的情况：

待排序表是逆序的情况下

$\sum_{i=2}^{n}i=2+3+\cdot \cdot \cdot +n=\frac{(n+2)(n-1)}{2}$ 次，而记录的移动次数最大值是： $\sum_{i=2}^{n}(i+1))=\frac{(n+4)(n-1)}{2}$ 次；如果是随机的，根据概率相同原则，平均比较移动次数是 $\frac{n^2}{4}$ 次，因此。可以得出时间复杂度为：O(n^2)

稳定性

稳定

希尔排序

直接插入排序，应该说，它的效率在某些时候是很高的，比如，我们的记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于，两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。不过别急，有条件当然是好，条件不存在，我们创造条件也是可以去做的。于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以增加效率。
如何让待排序的记录个数较少呢?很容易想到的就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。这不对呀，比如我们现在有序列是{9,1,5,8,3,7,4,6,2}，现在将它分成三组，{9,1,5}, {8,3,7}, {4,6,2}，哪怕将它们各自排序排好了，变成{1,5,9}，{3,7,8}, {2,4,6}, 再合并它{1,5,9,3,7,8,2,4,6},此时，这个序列还是杂乱无序，谈不上基本有序，要排序还是重来一遍直接插入有序，这样做有用吗?需要强调一下，所谓的基本有序,就是小的关键字基本在前面，大的基本在后面，不大不小
的基本在中间，像{2,1,3,6,4,7,5,8,9}这样可以称为基本有序了。但像{1,5,9,3,7 ,8,2,4,6}这样的9在第三位，2在倒数第三位就谈不上基本有序。

排序原理

将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

代码


void ShellSort(sqList L)
{
	int i, j;
	int tmp = 0;
	int increment = L->length;
	do
	{
		increment= increment/ 3 + 1;
		for (i = increment; i < L->length; ++i)
		{
			if (L->r[i] < L->r[i - increment])
			{
				tmp = L->r[i];
				for (j = i - increment; j >=0 && tmp < L->r[j]; j -= increment)
				{
					L->r[j + increment] = L->r[j];
				}
				L->r[j + increment] = tmp;
			}
		}
	} while (increment> 1);
}

希尔排序复杂度分析

通过这段代码的剖析，相信大家有些明白，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。
这里“增量"的选取就非常关键了。是用increment=increment/3+1;的方式选取增量的，可究竟应该选取什么样的增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。不过大量的研究表明，当增量序列为dlta[k] $2^{t-k+1}-1$ (0≤k≤t≤ Log2(n+1)])时，可以获得不错的效率.

时间复杂度

在O( $n^{1.3}$ )到O( $n^{1.5}$ )之间，书上定义为： $n^{1.5}$

空间复杂度

O(1)

稳定性

存在跳跃交换因此不稳定

堆排序

了解堆排序之前先搞清楚两点；

1、什么是大顶堆什么是小顶堆？

堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如图所示：

2、大（小）顶堆各个元素之间有什么关系？

以大顶堆为例：

如果i=1, 则结点i是二叉树的根，无双亲;如果i>1，则其双亲是结点Li/2」。那么对于有n个结点的二
叉树而言，它的i值自然就是小于等于[n/2」了。性质5的第二、三条，也是在说明下标i与2i和2i+1的双亲子女关系。从图可以看出每个根都会比自己的左右孩子大，并且每个根节点和左孩子的之间都有关系：s=i*2+1每个根节点和右孩子之间的关系为s=i*2+2

排序原理

堆排序( Heap Sort )就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1 个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

代码


void HeapAdjust(sqList L, int s, int m)
{
	int tmp, j;
	tmp = L->r[s];
	for (j = s * 2 + 1; j <m; j = s * 2 + 1)
	{
		if (j < m && L->r[j] < L->r[j + 1])
			++j;
		if (tmp >= L->r[j]) break;
		L->r[s] = L->r[j];
		s = j;
	}
	L->r[s] = tmp;
}
void HeapSort(sqList L)
{
	int i;
	for (i = (L->length-1-1) / 2; i >=0; i--)
	{
		HeapAdjust(L, i, L->length);
	}
	for (i = L->length - 1; i >=0; i--)
	{
		Swap(L, 0, i);
		HeapAdjust(L, 0, i - 1);
	}
}

带排序队列

第一次大顶堆调整结束

后依次类推

堆排序复杂度分析

时间复杂度

它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为0(n)。
在正式排序时，第i次取堆顶记录重建堆需要用0(logi)的时间(完全二叉树的某个结点到根结点的距离为[log2i]+1),并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为0[nlogn]。
所以总体来说，堆排序的时间复杂度为0(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为0(nlogn)。

空间复杂度

O(1)

稳定性

不稳定（存在跳跃交换）

归并排序（递归和非递归）

排序原理

归并排序(Merging Sort) 就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1,然后两两归并,得到[n/2] ([x]表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并....如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

代码

代码1（递归）


void Merge(int SR[], int TR[], int i, int m, int n)
{
	int j,k,l;
	for (j = m + 1, k = i; i <=m && j <= n; k++)
	{
		if (SR[i] < SR[j]) TR[k] = SR[i++];
		else TR[k] = SR[j++];
	}
	if (i <= m)
	{
		for (l = 0; l <=m - i; ++l)
			TR[k + l] = SR[i + l];
	}
	if (j <= n)
	{
		for (l = 0; l <= n - j; ++l)
			TR[k + l] = SR[j + l];
	}
}
void MSort(int SR[], int TR1[], int s, int t)
{
	int m;
	int TR2[MaxSize];
	if (s == t) TR1[s] = SR[s];
	else
	{
		m = (s + t) / 2;
		MSort(SR, TR2, s, m);
		MSort(SR, TR2, m + 1, t);
		Merge(TR2, TR1, s, m, t);
	}
}
void MergeSort(sqList L)
{
	MSort(L->r, L->r, 0, L->length - 1);//为了调用方便
}

代码2（非递归）


void Merge(int SR[], int TR[], int i, int m, int n)
{
	int j,k,l;
	for (j = m + 1, k = i; i <=m && j <= n; k++)
	{
		if (SR[i] < SR[j]) TR[k] = SR[i++];
		else TR[k] = SR[j++];
	}
	if (i <= m)
	{
		for (l = 0; l <=m - i; ++l)
			TR[k + l] = SR[i + l];
	}
	if (j <= n)
	{
		for (l = 0; l <= n - j; ++l)
			TR[k + l] = SR[j + l];
	}
}
void MergePass(int SR[], int TR[], int s, int n)//0 9 
{
	int i = 0;
	int j;
	while (i <= n - 2 * s + 1)
	{
		Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
		i = i + 2 * s;
	}
	if (i < n - s + 1)
		Merge(SR, TR, i, i + s - 1, n);
	else
	{
		for (j = i; j <= n; j++)
		{
			TR[j] = SR[j];
		}
	}
 
}
void MergeSort2(sqList L)
{
	int* TR = (int*)malloc(L->length * sizeof(int));
	int k = 1;
	while (k < L->length)
	{
		MergePass(L->r, TR, k, L->length-1);
		k = 2 * k;
		MergePass(TR, L->r, k, L->length-1);
		k = 2 * k;
	}
}

归并排序复杂度分析

时间复杂度

递归算法：一趟归并需要将 SR[1]~ SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]~TR1[n]中,这需要将待排序序列中的所有记录扫描一遍，因此耗费0[n]时间,而由完全二叉树的深度可知，整个归并排序需要进行[log2n]次，因此，总的时间复杂度为0(nlogn), 而且这是归并排序算法中最好、最坏、平均的时间性能。

空间复杂度

递归算法：由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结
果以及递归时深度为lbg2n的栈空间，因此空间复杂度为0(n+logn)。

非递归算法：非递归的迭代方法，避免了递归时深度为log2n 的栈空间，空间只是用到申请归并
临时用的TR数组，因此空间复杂度为0(n)，并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。

稳定性

对代码进行仔细研究，发现Merge函数中有if (SR[i]<SR[j])语句，这就说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。也就是说，归并排序是一种比较占用内存，但却效率高且稳定的算法。

基数（桶）排序

排序原理

根据数据的基数（如10进制基数为10）建桶（10进制基数为10建立0~9十个桶）基数排序（Radix Sort）是桶排序的扩展.

代码


static int Get_figure(int a[], int len)
{
	int tmp = 0;
	for (int i = 0; i < len; i++)
	{
		if (a[i] > tmp)
		{
			tmp = a[i];
		}
	}
	int count = 0;
	while (tmp != 0)
	{
		count++;
		tmp /= 10;
	}
	return count;
}
static int Get_Num(int n, int fin)
{
	for (int i = 0; i < fin; i++)
	{
		n /= 10;
	}
	return n % 10;
}
static void Radix(int* arr, int len, int fin) 
{
	int bucket[10][20] = { 0 };//十个桶  每个桶初始容量20个
	int num[10] = { 0 };
	for (int i = 0; i < len; i++)
	{
		int index = Get_Num(arr[i], fin);
		bucket[index][num[index]] = arr[i];
		num[index]++;
	}
	int k = 0;
	for (int i = 0; i <= 9; i++)
	{
		for (int j = 0; j < num[i]; j++)
		{
			arr[k++] = bucket[i][j];
		}
	}
}
void RadixSort(sqList L) 
{
	int count = Get_figure(L->r,L->length);
	for (int i = 0; i < count; i++)
	{
		Radix(L->r, L->length, i);
	}
}

第一次个位数比较依次放入桶中依次取出存入原数组

取出后依次存入原来数组

第二次以十位数比较依次存入桶中

取出后依次存入原来数组

第三次以百位数比较依次存入桶中

取出后依次存入原来数组

基数排序复杂度分析

时间复杂度

基数排序时间复杂度为 ${\color{Red} O(dn)}$ ，但常数项较大，同时其不是原址排序，因此不快于基于比较的排序算法（如快速排序、堆排序等）。

空间复杂度

${\color{Red} }O(n)$

稳定性

稳定

快速排序

希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。

排序原理

快速排序(Quick Sort) 的基本思想是:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

代码（基本）


int Partition(sqList L, int low, int high)
{
	int pivotkey;
	pivotkey = L->r[low];
	while (low < high)
	{
		while (low < high && L->r[high] >= pivotkey)
			high--;
		Swap(L, low, high);
		while (low < high && L->r[low] <= pivotkey)
			low++;
		Swap(L, low, high);
	}
	return low;
}
void QSort(sqList L, int low, int high)
{
	int pivot;
	if (low < high)
	{
		pivot = Partition(L, low, high);
		QSort(L, low, pivot - 1);
		QSort(L, pivot + 1, high);
	}
}
void QuickSort(sqList L)
{
	QSort(L, 0, L->length-1);
}

第一步 low=0；high=L->lenght-1=9 ；pivotkey=L.r[0]=100;如图：

第二步，进入while循环，首先判断L->r[high]>=pivotkey;成立；high--;hight=8;

第三步，再执行判断 L->[high]>=pivotkey;不成立；执行交换 Swap()，此时 L.r[0]=44;L.r[8]=100,如图：

第四步，执行判断L->[low]<=pivotkey;成立即low++;不成立交换Swap();执行完如图所示：

此时low=high=8循环退出，返回low的值（也可以是high）; 执行QSort函数的下面递归，也就是传入QSort(L, 0, 7);QSort(L, 9, 9);依次递归；直到完全有序；

**快速排序复杂度分析（*）**

时间复杂度

快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如图所示，它是{50,10,90,30,70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是 50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

在最优情况下:Partition 每次都划分得很均匀，如果排序n个关键字，其递归树的深度就[log2n]+1 (|x|表示不大于x的最大整数)，即仅需递归log2n次，需要时间为T (n)的话,第一Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T (n/2)的时间(注意是最好情况，所以平分两半)。于是不断地划分下去。在最优的情况下，快速排序算法的时间复杂度为0(nlogn)。

在最坏的情况下:待排序的序列为正序或者逆序，每次划分只得到一个比，上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为 $\sum_{i=1}^{n-1}(n-i)=n-1+n-2+....+1=\frac{n(n-1)}{2}$ ，最终其时间复杂度为O( $n^{2}$ )。

平均的情况:设枢轴的关键字应该在第k的位置(1≤k≤n), 那么;由数学归纳法可证明，其数量级为0(nlogn)。由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

空间复杂度

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n,其空间复杂度也就为0(logn),最坏情况，需要进行n-1递归调用，其空间复杂度为0(n)，平均情况，空间复杂度也为0(logn)。

稳定性

由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

快速排序优化

1.优化选取枢轴

问题：

比如说以数组{9,1,5,8,3,7,4,6,2}来说，由于代码pivotkey=L->r[low];可以看出，选取9，作为枢轴pivotkey来说，此时，经过一轮“pivot=Partition(L,0,9);”转换后值更换了9和2的位置，并且返回9给pivot，其实没有实质性的变化；

改进（三数去中法）：

原理：取三个关键字先进行排序，将中间作为枢轴，一般取左端，右端和中间三个数，也可一随机选取；


int mid = low + (high - low) / 2;//取中间元素下标
	if (L->r[low] > L->r[high])
		Swap(L, low,high);
	if (L->r[mid] > L->r[high])
		Swap(L, high, mid);
	if (L->r[mid] > L->r[low])
		Swap(L, mid, low);

2.优化小数组时的排序方案

综合思想就是：杀鸡焉用牛刀；原因是：快排用到了递归操作，在大量数据排序时，性能影响可以忽略；在数组只有几个数据是时，栈消耗大；那多少是合适的？有资料认为7比较合适，也有认为是50更合理，实际应用可以调整；

对于排序量不大的排序队列直接采用直接插入排序来优化就行；再改一下代码；


void QSort(sqList L, int low, int high)
{
	int pivot;
	const int MAX_SIZE = 7;
	if ((high - low) > MAX_SIZE)
	{
		if (low < high)
		{
			pivot = Partition(L, low, high);
			QSort(L, low, pivot - 1);
			QSort(L, pivot + 1, high);
		}
	}
	else
		INserSort(L);
}

3.优化不必要的交换


int Partition1(sqList L, int low, int high)
{
	int pivotkey;
	int mid = low + (high - low) / 2;//取中间元素下标
	if (L->r[low] > L->r[high])
		Swap(L, low, high);
	if (L->r[mid] > L->r[high])
		Swap(L, high, mid);
	if (L->r[mid] > L->r[low])
		Swap(L, mid, low);
	pivotkey = L->r[low];
	int tmp = pivotkey;//备份
	while (low < high)
	{
		while (low < high && L->r[high] >= pivotkey)
			high--;
		L->r[low] = L->r[high];//替换而不是交换
		//Swap(L, low, high);
		while (low < high && L->r[low] <= pivotkey)
			low++;
		L->r[high] = L->r[low];
		//Swap(L, low, high);//替换而不是交换
	}
	L->r[low] = tmp;
	return low;
}

注意代码我们事实将pivotkey 备份到tmp中，然后在之前是swap时，只作替换的工作，最终当low与high会合，即找到了枢轴的位置时，再将tmp的数值赋值回L.r[low]。因为这当中少了多次交换数据的操作，在性能上又得到了部分的提高。

4.优化递归操作


void QSort1(sqList L, int low, int high)
{
	int pivot;
	const int MAX_SIZE = 7;
	if ((high - low) > MAX_SIZE)
	{
		while(low < high)
		{
			pivot = Partition1(L, low, high);
			QSort1(L, low, pivot - 1);
			low = pivot + 1;
		}
	}	
	else
		INserSort(L);
}

当将if改成while后(见加粗代码部分),因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1 赋值给low, 再循环后，来一次Partition(L,low,high)，其效果等同于“QSort (L,pivot+1,high) ;”。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。

排序算法的总结

排序算法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O( $n^{2}$ )	$O(n )$	O( $n^{2}$ )	$O(1)$	稳定
简单选择排序	O( $n^{2}$ )	O( $n^{2}$ )	O( $n^{2}$ )	$O(1)$	稳定
直接插入排序	O( $n^{2}$ )	$O(n )$	O( $n^{2}$ )	$O(1)$	稳定
希尔排序	$O(nlogn)$ ~ $O(n^{2})$	$O(n^{1.3})$	O( $n^{2}$ )	$O(1)$	不稳定
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n )$	稳定
快速排序	$O(nlogn)$	$O(nlogn)$	O( $n^{2}$ )	$O(nlogn)$ ~ $O(n)$	不稳定
基数排序	$O(dn)$	$O(dn)$	$O(dn)$	$O(n )$	稳定

参考文献：

大话数据结构. 北京：清华大学出版社

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/163827