2

第一届排序算法性能大赛(上万字激烈解说)

 2 years ago
source link: https://blog.csdn.net/qq_49217297/article/details/120640606
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

写在前面
最近学到了一些重要的排序，并且取巧地测了一下各种排序算法在不同的算法实现、优化以及递归和非递归下的运行速度，想着写篇文章记录学习成果，同时分享给大家。
本文一共提及了以下几种常用到的排序，其他排序使用场景较少，便没有提及。

e515e44f00eb44e6981c8aaac84442be.png 并且本文的全部代码实现均为通俗易懂的c语言，希望能够得到大家的认可和支持，如果觉得本文不错的话，欢迎三连哦。好了，接下来就是文章本章了。

必备排序常识

稳定性：在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
时间复杂度：一个排序算法在执行过程中所耗费的时间量级的度量。
空间复杂度：一个排序算法在运行过程中临时占用存储空间大小的度量。

注意:在使用的时候尽量按照排序方式的英文书写，便于阅读。

第一组参赛选手：插入排序

原理：把待排序的数据按照关键码的大小，按照安排徐规则，将当前数据插入到已经排序好的数据中，使其称为一个新的排序好的数据，直到所有数据插完为止。
实际中我们玩扑克牌时，就用了插入排序的思想。

462af3c6759a48ff885798da724759b8.png

1.直接插入排序

排序原理：
当插入第i个元素时，前面的i-1个元素已经时有序的，此时用第i个元素的值和前面i-1个元素进行比较，直到找到插入位置，插入即可，原来位置的元素顺序后移。
过程展示：

bfd7681204c04a7bad4b8b8854345609.gif

代码实现：

// 插入排序
void InsertSort(int* a, int n)
{
	for (int tail = 0;tail < n - 1 ;tail++)
	{
		int temp = tail;//记录有序序列的最后一个元素的下标
		int x = a[tail + 1];
		while (temp >= 0)
		{
			if (a[temp] > x)//说明还有数大于x，继续把前面数组的往后移
			{
				a[temp + 1] = a[temp];
				temp--;
			}
			else//如果前面的值小于x，说明不需要往前进行比较了
			{
				break;
			}
		}
		a[temp + 1] = x;//排到所有小于x的数的后面一位
	}
}

特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高，因为当有序的情况下会直接跳出该次循环
  2. 时间复杂度：O(N) ~ O(N^2)。最好的情况是刚好和算法的顺序一致的情况，只遍历一遍；最坏的情况为刚好有序的但是和算法的顺序刚好相反，此时时间复杂度为n * (n-1) * ··· *2 * 1为等差数列，按公式计算得为O(N^2)。所以在数据大部分有序的情况下使用插入排序还是不错的。
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

2.希尔排序

排序原理：

希尔排序法(Shell Sort)又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

过程展示：

0192769cc55346fba9d49e4014f25f39.png

代码实现：

// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)//外层循环不断进行预排序
	{
		gap =gap / 3 + 1;//取排序的间隔，+1是为了确保一定有1，有一才能正确排出正确的顺序
		//gap /= 2;//取除2的商也可以，也满足最后的数有1
		for (int tail = 0;tail < n - gap ;tail ++)//整体思想和插入排序差不多，但是间隔却不一样
		{
			int temp = tail;
			int x = a[tail + gap];
			while (temp >= 0)
			{
				if (a[temp] > x)
				{
					a[temp + gap] = a[temp];
					temp -= gap;
				}
				else
				{
					break;
				}
					
			}
			a[temp + gap] = x;
		}
	}
}

特性总结：

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序，不要小看这些预排序，可以让插入排序的性能有很大的提升。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。后面可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度：O(n*logn)~O(n^2），当间隔gap取得好的条件下可以达到最好情况，最不理想的情况是当gap == 1的时候，也就是直接插入排序。
  4. 稳定性：不稳定。当相同的值被分到不同的组中在进行排序，不同的组中数值大小不确定，此时就不能保证这些数还能保持先后顺序。

3.性能比拼时刻

测试代码：

利用时间生成的随机数进行的粗劣测试，看个热闹，哈哈。
如果大家使用这段代码一定要在release版本下进行测试哦，因为release版本进行了优化，能够更加客观地测试出速度。

void TestOP()
{
	srand(time(0));
	const int N = 100000;//取十万个随机值数据进行排序比较
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();//生成随机数
		//a1[i] = i;//生成有序数
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSortNonR(a5, 0, N - 1);
	QuickSort(a4, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	//BubbleSort(a4, N);
	int end7 = clock();

	printf("InsertSort:%d ms\n", end1 - begin1);
	printf("ShellSort:%d ms\n", end2 - begin2);
	printf("SelectSort:%d ms\n", end3 - begin3);
	printf("HeapSort:%d ms\n", end4 - begin4);
	printf("BubbleSort:%d ms\n", end7 - begin7);
	printf("QuickSort:%d ms\n", end5 - begin5);
	printf("MergeSort:%d ms\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

十万个随机数据的测试结果：

ba309eaa7fbd46c3aceb76e26f4f3506.png

可见此时得益于希尔排序优秀的时间复杂度，快了插入排序将近200倍。希尔排序循环大概进行的次数为：O(n*logn)约等于170万。
而直接插入排序接近最坏的情况，O(n^2)后的计算结果为100亿次。由此可见两种排序在这种情况下根
本不是一个数量级的。

一百万个有序数据的测试结果：

343844dc15ed4bf4ae123237cb6f9894.png

但是在数据大量并且有序的情况下，直接插入排序的时间复杂度接近于O(n)，在一百万个数据的条件下耗时大大减少，所以如果在数据大量且接近有序的条件下直接插入排序也是不错的。
虽然希尔排序的本质是插入排序，但是由于需要预排序，耗时肯定会比直接插入排序多。

所以最后胜出的选手是希尔排序

第二组参赛选手：选择排序

原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

1.直接选择排序

排序原理：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续排在已排序元素后，直到未排序元素个数为0。

过程展示：

0748d4b6f7c349f5a8712702b83bef87.gif

代码实现：

void Swap(int* a, int* b)//交换函数
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//选择排序，一次只选择一个数
void SelectSort(int* a, int n)
{
	for (int i = 0;i < n;i++)
	{
		int temp = i;//保存未排序的元素下标
		for (int j = i; j < n;j++)
		{
			if (a[temp] > a[j])//有元素大于中间值
			{
				temp = j;//更新下标
			}
		}
		if (temp != i)//有元素小于小于未排序的头元素，交换两者位置
			Swap(a + i, a + temp);
	}
}

// 选择排序优化版本，一次循环可以选出最大和最小的值
void SelectSortOp(int* a, int n)
{
	int end = n - 1;//未排序元素尾位置
	for (int slow = 0;slow < end;slow++)
	{
		int min = slow;//保存最小值的下标
		int max = slow;//保存最大值的下标
		for (int fast = slow + 1;fast < end + 1 ;fast++)
		{
			if (a[fast] < a[min])
			{
				min = fast;
			}
			if (a[fast] > a[max])
			{
				max = fast;
			}
		}
		if(min != slow)//有小于的元素,交换两者的位置
		Swap(&a[min], &a[slow]);
		if (max == slow)//最大值就是未排序元素首元素,前面发生了值交换,更新下标
			max = min;
		Swap(&a[max], &a[end]);
		end--;
	}
}

特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(n^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定。交换值的同时可能将其他相同值的位置改变了。
    例： 4 9 5 5 8 5 6 9 -> 4 9 5 9 8 5 6 5
    此时就有相同值的位置顺序改变了

2.堆排序

排序原理：

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

堆是用数组表示的完全二叉树。要学习堆排序，首先要学习堆的向下调整算法，因为要用堆排序先得建堆，而建堆需要执行多次堆的向下调整算法。

堆的向下调整算法（使用前提）：
 若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
 若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

10e95baa4c264213b2c00ea432446bde.png

向下调整算法的基本思想（以建大堆为例）：
 1.从根结点处开始，选出左右孩子中值较大的孩子。
 2.让大的孩子与其父亲进行比较。
若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。

0c37dbfda17c4d248da476b8bf08b721.png

使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(n+1)（n为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logn)。
此时需要找出最后一个有叶子结点的父结点，n为结点的总个数，(n - 2) / 2就是满足条件的下标，并以该结点从下往上依次向下调整。最后就可以建成一个大堆。
在这里插入图片描述

代码实现：

void Swap(int* a, int* b)//交换函数
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//向下调整函数，保证满足条件左右子树是小堆或者是大堆
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = root * 2 + 1;
	while (child < n)
	{
		if (child + 1<n && a[child + 1] < a[child])//默认是左孩子
		{
			child += 1;//让下标为数值较大的孩子
		}
		//改变上下两个if条件控制为大堆或小堆,同时控制升序和降序
		if (a[child] < a[parent])
		{
			Swap(a + parent, a + child);//交换父结点和较大的孩子
			parent = child;
			child = parent * 2 + 1;//更新父子结点,继续向下调整
		}
		else
		{
			break;
		}
	}
}
// 堆排序
void HeapSort(int* a, int n)
{
	//找到最后一个有叶子结点的父结点，并以该结点从下往上依次向下调整
	for (int i = (n - 2) / 2; i >= 0;--i)//建堆
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	for (;end > 0;end--)//逐个取出根结点,再次建堆
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
	}
}

整个排序过程：

911570efebe24088a546f64467a027f7.gif

特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(n*logn)
33dc93db097748c6882bd0a76611ed43.png

前面提到向下建堆的时间复杂度为O(logn)，相乘后的时间度就为O(n*logn)。

  1. 空间复杂度：O(1)
  2. 稳定性：不稳定。因为向下调整的时候可能将相同的值位置顺序改变。
    例：
5c1d768dd4ba41a38887f640fc42d1c9.png

3.性能比拼时刻

十万个随机数据的测试结果：

11b03eafeb26488c944b0dd85888f714.png

因为堆排序的时间复杂度为固定的O(n*logn)，而选择排序的时间复杂度为固定的O(n^2)，所以在算法上得到大大提升，看图快了将近1000倍。

十万个有序数据的测试结果：

5fe0186d41864a6c82ba6099e0a26114.png 因为两个排序算法的时间复杂度是固定的，就算是有序的数据也吴差别。

所以最后胜出的选手是堆排序

第三组参赛选手：交换排序

原理：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1.冒泡排序

排序原理：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

过程展示：

19ef4fc44101449f9aeb2770bae8fc1a.gif

代码实现：

//冒泡排序
void BubbleSort(int a[], int n)
{
	for (int i = n;i >= 0;i--)//循环层数
	{
		int flag = 1;//判断是否有序的标志位
		for (int j = 0 ;j < i - 1;j++)//比较次数
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 0;
			}
		}
		if (flag)//没发生交换,说明数组有序,终止循环
			break;
	}
}

特性总结：

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(n^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

2.快速排序(重量级选手)

排序原理：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

对于如何按照基准值将待排序列分为两子序列，常见的方式有：
 1. 挖坑法
 2. 前后指针法(Hoare版本)
 3. 快慢指针法

递归实现：

挖坑法

排序原理：

挖坑法的单趟排序的基本步骤如下：
 1、选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。
 2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走，否则会无法正确排出顺序）。
 3、在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）

以上就是挖坑法的单趟排序，经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key，但是此时key的左边和右边的数据还是乱序的。
然后将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，最终数据就是有序的。

过程展示：

f7bfb4e94566467689afb2164dd32b59.gif

代码实现：

//快速排序挖坑法
int PartSort1(int* a, int left, int right)
{
	int start = left;
	int end = right;
	//取一个数值,将比他小的数放左边,比他大的放右边
	int key = a[start];
	while (start < end)//前后下标还没相遇时一直循环
	{
		int pivot = start;//坑位下标
		while (start < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];//将右边比key小的值放在坑位中
		pivot = end;//更新坑位下标
		while (start < end && a[start] <= key)
		{
			start++;
		}
		a[pivot] = a[start];//将左边比key小\大的值放在坑位中
		pivot = start;//更新坑位下标
	}
	a[start] = key;//把key放在两下标相遇的地方
	return start;//返回key的下标
}

//快速排序递归实现
void QuickSort(int* a,int left, int right)
{
	if (left >= right)//当两边相遇或只有一个数据时,就返回
	{
		return;
	}
	int index = PartSort1(a, left, right);//得到中间数值的位置

	QuickSort(a, left, index - 1);//递归左边
	QuickSort(a, index + 1, right);//递归右边
}

注意：
此时快速排序有一个较大的缺陷，因为这里默认选择的是最左边的值作key，如果该数据有序且是升序，那么key是所有数据中值最小的，那么排序的只有key的右边值，每次只能排出一个值，此时的时间复杂度为O(n^2)。为了避免这种特殊情况的出现，所以还得写一个函数取一个适当的值作key。

代码如下：

int GetMidIndex(int* a, int left, int right)
{
	int mid = (right + left) >> 1;
	if (a[mid] > a[left])
	{
		if (a[left] > a[right])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

// 快速排序挖坑优化版本
int PartSort1(int* a, int left, int right)
{
	int start = left;
	int end = right;
	int mid = GetMidIndex(a, left, right);//三数取中
	Swap(&a[mid], &a[start]);//将该数默认放在最左边,好分析写过程
	//取一个数值,将比他小的数放左边,比他大的放右边
	int key = a[start];
	while (start < end)//前后下标还没相遇时一直循环
	{
		int pivot = start;//坑位下标
		while (start < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];//将右边比key小的值放在坑位中
		pivot = end;//更新坑位下标
		while (start < end && a[start] <= key)
		{
			start++;
		}
		a[pivot] = a[start];//将左边比key小\大的值放在坑位中
		pivot = start;//更新坑位下标
	}
	a[start] = key;//把key放在两下标相遇的地方
	return start;//返回key的下标
}

前后指针法(Hoare版本)

排序原理：

Hoare版本的单趟排序的基本步骤如下：
 1、选出一个key，一般是最左边或是最右边的。
 2、定义一个L和一个R，L从左向右走，R从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为key，则需要L先走）。
 3、在走的过程中，若R遇到小于key的数，则停下，L开始走，直到L遇到一个大于key的数时，将L和R的内容交换，R再次开始走，如此进行下去，直到L和R最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后我们在将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的。

过程展示：

964867f32e604eadb29701fbeda99e47.gif

代码实现：

// 快速排序前后指针法
int PartSort2(int* a, int left, int right)
{
	int start = left;
	int end = right;
	int mid = GetMidIndex(a, left, right);//三数取中
	Swap(&a[mid], &a[start]);//将该数默认放在最左边,好分析写过程
	int key = left;
	while (start < end)
	{
		//从右向左找比key小的值,找到后就停下
		while (start < end && a[start] <= a[key])
			start++;
		//从左往右找比key大的值,找到后就停下
		while (start < end && a[end] >= a[key])
			end--;
		//交换两值
		Swap(&a[start], &a[end]);
	}
	//执行完循环后,将key和指针相遇的地方交换
	Swap(&a[start], &a[key]);
	return start;//返回前后指针相遇的地方
}

快慢指针法

排序原理：

前后指针法的单趟排序的基本步骤如下：
 1、选出一个key，一般是最左边或是最右边的。
 2、起始时，prev指针指向序列开头，cur指针指向prev+1。
 3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换即可。

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

过程展示：

26632bfe026745118edd2073fac1f698.gif

代码实现：

// 快速排序快慢指针法
int PartSort3(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);//三数取中
	Swap(&a[mid], &a[left]);//将该数默认放在最左边
	int key = left;
	int fast = key + 1;//初始化快指针
	int slow = key;//慢指针
	while (fast <= right)
	{
		//如果有值小于key并且快慢指针不指向同一块地方就交换值
		if (a[fast] < a[key] && ++slow != fast)
		{
			Swap(&a[slow], &a[fast]);
		}
		fast++;
	}
	Swap(&a[key], &a[slow]);
	return slow;
}

至此快速排序的三种算法展示完毕

建议大家使用挖坑法和前后指针法。

优化递归算法

考虑到递归实现排序算法，当递归深度太深时，会非常消耗栈桢。比如让递归深度为20层时，递归调用函数次数为2^20 - 1= 1048575,高达一百万次。
而最后几层的栈桢消耗最为巨大,第20层调用函数为2^19 = 524288,第19层为2^18 = 262144，第18层为2^17 = 131072。
所以为了减少栈桢的消耗，我们可以使递归到较深的时候调用其他的排序帮助快速排序实现最后的排序。可以大大减少递归消耗栈桢，提升排序速度。

代码实现：

//递归优化版本
void QuickSort(int* a,int left, int right)
{
	if (left >= right)//当两边相遇或只有一个数据时,就返回
	{
		return;
	}

	int index = PartSort1(a, left, right);//得到中间数值的位置

	if (index - left > 100)//当每组只剩100个数未排序时
	{
		QuickSort(a, left, index - 1);//递归左边
	}
	else
	{
		InsertSort(a + left, index-left);
	}
	if (right - index > 100)
	{
		QuickSort(a, index + 1, right);//递归右边
	}
	else
	{
		InsertSort(a + index+ 1, right - index);
	}
}

非递归实现：

因为在递归的过程中未排序的数据左右下标会睡着递归不断缩小，直到满足递归出口，完成对数据的排序。

如果非递归实现，需要在循环中保存数据的下标，模拟递归的实现。

所以选择用栈保存左右下标，在循环中将数据分成多部分进行排序，当某一部分排好序后再将左右下标出栈，直到栈里没有数据，说明此时排序就完成了。

但是c语言库没有栈，需要自己实现一个栈的结构，这里只给大家看一下函数调用接口，了解下实现的思想。

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	Stack stack;
	StackInit(&stack);//栈初始化
	StackPush(&stack, left);//模拟递归将左右下标入栈
	StackPush(&stack, right);
	while (!StackIsEmpty(&stack))//判断栈是否为空,不为空说明还需要进行排序
	{
		int end = StackTop(&stack);//取栈的头元素
		StackPop(&stack);//出栈
		int start = StackTop(&stack);
		StackPop(&stack);

		int index = PartSort1(a, start, end);//得到标志位的下标
		if (index + 1 < end)//判断是否只剩一个元素
		{
			StackPush(&stack, index + 1);
			StackPush(&stack, end);
		}
		if (start<index - 1)
		{
			StackPush(&stack, start);
			StackPush(&stack, index - 1);
		}
	}
	StackDestory(&stack);//销毁栈
}

特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(n*logn)
7b0c476abd284062870ad444bc73ae03.png
  1. 空间复杂度：O(logn)
  2. 稳定性：不稳定。当有相等的值时，不好控制，只能往左边或右边放，但是前后顺序就不确定了。

3.性能比拼时刻

此前排序的三个算法：挖坑法，前后指针法，快慢指针法的性能是差不多的，在这里是用的挖坑法进行的测试。

十万个数据：

冒泡和快排测试结果：

dad3a0aa5047462388700d948a81a3f1.png

冒泡排序的时间复杂度为固定的O(n^2)，而且每循环一次都可能多次调用交换函数，导致耗时较长。快速排序的时间复杂度为O(n*logn)，所以在性能上快速排序快得特别多。

在无三数取中下的测试结果：

a71cba366e244027a39f900f44b5875b.png

可以看出此时在有序的情况下，快速排序的优势就已经没有了，时间复杂度为O(n^2)，接下来看有三数取中的性能。

在有三数取中下的测试结果：

f51984a6bef94f5aa879f8cf79367208.png 在有三数取中的条件下，快速排序已经超过无序的消耗时间，所以说在有序的情况下三数取中对快速排序的性能还是有很大提升的。

一百万个数据：

递归较深时进行优化：
这里的优化结果是，在每组数据还剩100个数据时，用插入排序进行排序。

bfca85d02fd14980a8c4bbeb41633544.png 可以看出优化过后性能还是有所提升。

递归和非递归的性能测试：

3dd14558b8f9409fac26ba0de04c7a24.png 递归和非递归的性能上没有什么差别，但是非递归能够节约栈桢空间。

第四组参赛选手：归并排序

排序原理：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

过程展示：

2d40b98ae752459f9c0bc6f5ae108774.pngecb3bb8973b64bbaab8235986f00a64c.gif

递归实现：

在排序的过程中，只依靠原数组进行排序显然是不现实的，所以说需要申请一块等大的辅助数组帮助排序，每次都将排好的一部分值写回原数组中，最后一次写入时数组就已经排好顺序了。

代码实现：

//归并排序，递归实现
void _MergeSort(int* a, int left, int right,int* temp)
{
	//分解
	if (left >= right)//递归出口,当只剩一个值时返回
		return;
	int mid = (left + right) >> 1;//取中间值
	_MergeSort(a, left, mid,temp);//左区间递归分治
	_MergeSort(a, mid + 1, right,temp);//右区间递归分治

	//合并
	int start1 = left;
	int start2 = mid + 1;
	int i = left;
	//如果有一块空间排完序就停止
	while (start1<=mid && start2<= right)
	{
		if (a[start1] > a[start2])//将小的值记录在辅助空间中
		{
			temp[i++] = a[start2++];
		}
		else
		{
			temp[i++] = a[start1++];
		}
	}
	while (start1 <= mid)//将剩下未排序的值保存在辅助数组中
	{
		temp[i++] = a[start1++];
	}
	while (start2 <= right)
	{
		temp[i++] = a[start2++];
	}
	//将辅助空间中拍好的值放入原数组中
	for (i = left;i <= right;i++)
	{
		a[i] = temp[i];
	}
}

void MergeSort(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);//额外的辅助空间
	_MergeSort(a, 0, n - 1, temp);
	free(temp);
}

非递归实现：

非递归实现排序时，就不能依靠递归帮助实现分治了。这里需要自己设置控制间隔，合理控制循环，从小到大将其排好顺序写入原数组。非递归也是需要额外的空间来帮助排序的。

不过，在非递归实现算法时，需要自己考虑边界控制。例如当gap == 4的时候，按理来说是两个四个元素的数组进行排序，但是当元素只有7个或9个的时候，就要对边界进行控制了。如果是左区间有值，而右半区间不存在，就可以跳过留给后面，当循环进行到后面的时候就会进行排序；或者右半区间算多了的情况，就要对区间进行修正。

代码实现：

void MergeSortNonR(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);//辅助空间
	int gap = 1;//归并的间隔控制
	//循环模拟递归合并
	while (gap < n)
	{
		for (int i = 0;i < n;i += 2 * gap)
		{
			//左右区间控制
			int start1 = i, end1 = i + gap - 1;
			int start2 = i + gap, end2 = i + 2 * gap - 1;
			int cur = i;
			// 归并过程中右半区间可能就不存在,就跳过循环，留给下一次排序
			if (start2 >= n)
			{
				break;
			}
			// 归并过程中右半区间算多了, 修正一下
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (start1 <= end1 && start2 <= end2)
			{
				if (a[start1] > a[start2])
				{
					temp[cur++] = a[start2++];
				}
				else
				{
					temp[cur++] = a[start1++];
				}
			}
			while (start1 <= end1)
			{
				temp[cur++] = a[start1++];
			}
			while (start2 <= end2)
			{
				temp[cur++] = a[start2++];
			}
			//将排好的部分写入原数组中
			for (int j = i;j <= end2;j++)
			{
				a[j] = temp[j];
			}
		}
	gap *= 2;
	}
	free(temp);
}

特性总结：

  1. 归并的缺点在于需要O(n)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(n*logn)
  3. 空间复杂度：O(n)
  4. 稳定性：稳定

用归并排序实现外排序：

首先，我先说明一下什么是内排序，什么是外排序：
 内排序：数据量相对少一些，可以放到内存中进行排序。
 外排序：数据量较大，内存中放不下，数据只能放到磁盘文件中，需要排序。

上面介绍的其他排序算法均是在内存中进行的，对于数据量庞大的序列，上面介绍的排序算法都束手无策，而归并排序却能胜任这种海量数据的排序。

假设现在有10亿个整数（4GB）存放在文件A中，需要我们进行排序，而内存一次只能提供512MB空间，归并排序解决该问题的基本思路如下：
 1、每次从文件A中读取八分之一，即512MB到内存中进行排序（内排序），并将排序结果写入到一个文件中，然后再读取八分之一，重复这个过程。那么最终会生成8个各自有序的小文件（A1~A8）。
 2、对生成的8个小文件进行一一合并，最终8个文件被合成为4个，然后再一一合并，就变成2个文件了，最后再进行一次合并，就变成1个有序文件了。

注意：这里将两个文件进行一一合并，并不是先将两个文件读入内存然后进行合并，因为内存装不下。这里的一一合并是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将较小的数据写入到一个新文件中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另一个文件中去，那么此时这个文件又是一个有序的文件了。

862b834820634c6ba6ecfdbac293ab79.png 或者这样进行排序： 98c5da738cce4347a913fe1f451790ec.png

参赛选手总介绍：

7a07eb0d9f234137acc937b6d3b08dfc.png

最后一轮的选手是

十万个数据：

685c8a6d9aa24f8489e080a9d4b9d503.png

一百万个数据：

a476f449241441c5bc7005489cfccc4a.png

可以看出最后优胜的选手就是快速排序，成功拿下大赛的冠军。

完结撒花。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK