排序算法

排序算法 排序

You got a dream , yougotta protect it. People can`t do something themselves, they wanna tell you you can not do it, if you want somethong , go get it,Period

排序的基本概念与分类

假设含有n个记录的序列，其相应的关键字分别为，需确定一种排列，使其相对应的关键字曼珠关键字的某种关系。即，使得序列称为一个按关键字有序的序列，这种 *** 作便称为排序。

在排序问题中，通常将数据元素称为记录。

输入的是一个记录的集合，输出的也是一个记录集合

排序可以看作是线性表的一种 *** 作。

排序的依据是关键字之间的大小关系，则，对于同一个记录集合，针对不同的关键字进行排序，可以得到不同的序列。

关键字ki是记录r的主关键字，也可以是次关键字，甚至是若干数据据项的组合。

多个关键字的排序最终都可以转化为单个关键字的排序。

排序的稳定性

假设ki=kj,i!=j,且在排序前的序列中ri领先于rj,即i

反之，如果排序后rj领先于ri, 则称所用的排序方法是不稳定的

只要只有一组关键字实例发生类似情况，则可以认定此排序的方法是不稳定的

内排序与外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为内排序和外排序

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。

外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行

对于内排序来讲，排序算法性能主要受到三个方面的限制：

1. 时间性能：排序算法的时间开销是衡量其好坏的最重要的标志
   1. 内排序中，主要分为比较和移动两种 *** 作
   2. 比较，关键字之间的比较
   3. 移动，记录从一个位置移动到另一个位置上。实际上，移动可以通过改变记录的存储方式来予以避免
   4. 高效率的内排序算法应该具有尽可能少的关键字比较次数和尽可能少的记录移动次数
2. 辅助空间，执行算法所需要的辅助存储空间。
   1. 辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间
3. 算法复杂度，算法本身的复杂度

内排序分为，插入排序，交换排序、选择排序和归并排序

按照算法的复杂度，可分为

1. 简单排序
   • 冒泡排序
   • 简单选择排序
   • 直接插入排序
2. 改进算法
   • 希尔排序
   • 堆排序
   • 归并排序
   • 快速排序

排序用到的结构与函数

struct Snode//用于要排序数组个数最大值，可根据需要修改
{
	int r[MAXSIZE + 1];//用于存储要排序数组，r[0]用作哨兵或临时变量
	int length;//用于记录顺序表的长度
};

typedef struct Snode* Sqlist;
void swap(Sqlist l,int i,int j)
{
	int temp = l->r[i];
	l->r[i] = l->r[j];
	l->r[j] = temp;

}

冒泡排序

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

//对顺序表L做交换排序（冒泡排序初级版）
void bubblesort0(Sqlist l)
{
	int i, j;
	for (i = 1; i < l->length; i++)
	{
		for (j = i + 1; j <= l->length; j++)
		{
			if (l->r[i] > l->r[j])
			{
				swap01(l, i, j);
			}
		}
	}
}

void bubblesort(Sqlist l)
{
	int i, j;
	for (i = 0; i < l->length; i++)
	{
		for (j = l->length - 1; j >= i; j--)//j是从后往前循环的
		{
			if (l->r[j] > l->r[j + 1])//若前者大于后者，注意这里与上一算法的差异
			{
				swap01(l, j, j + 1);//交换l->r[j]与l->r[j+1]的值
			}
		}
	}
}

在冒泡排序中，较小的数字会如同气泡般慢慢浮到上面，因此该算法得名为冒牌排序。

//对顺序表l做改进的冒泡算法
int bubblesort2(Sqlist l)
{
	int i, j;
	int flag = true;//flag用来标记
	for (i = 1; i < l->length && flag; i++)//若flag为true则由数据交换，否则退出循环
	{
		flag = false;//初始化false
		for (j = l->length - 1; j >= i; j--)
		{
			if (l->r[j] > l->r[j + 1])
			{
				swap01(l, j, j + 1);//交换l->r[j]与l->r[j+1]的值
				flag = true;//如果有数据交换，则flag为true
			}
		}
	}
}

冒泡排序的时间复杂度为O(n^2)

简单排序

在冒泡排序中，其基本思想是不断在交换，通过交换完成最终的排序

选择排序，则是在排序中找到合适的关键字再做交换，并且只移动一次就完成相应关键字的定位工作

选择排序的基本思想就是每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列的第i个记录。

简单选择排序算法

简单选择排序算法，就是通过n-i个关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换

//简单选择排序
void selectsort(Sqlist l)
{
	int i, j, min;
	for (i = 1; i < l->length; i++)
	{
		min = i;//将当前下标定义为最小值下标
		for (j = i + 1; j <= l->length; j++)
		{
			if (l->r[min] > l->r[j])
			{
				min = j;//找到之后的最小值
			}
		}
		if (i != min)//如果min不等于i,说明找到最小值，交换
		{
			swap01(l, i, min);
		}

	}
}

简单选择排序的时间复杂度为O(n^2)，但其最大的特点是交换移动数据的子树相当少，因此在性能上还是要优于冒泡排序的

直接插入排序

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

//直接插入排序算法
void insertsort(Sqlist l)
{
	int i, j;
	for (i = 2; i <= l->length; i++)
	{
		if (l->r[i] < l->r[i - 1])//需要将l->r[i]插入有序子表
		{
			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];//插入正确的值
		}
	}
}

直接插入排序法的时间复杂度为O(n2)，但同样的O(n2)时间复杂度，直接插入法比冒泡和简单排序的性能要好一些

直接插入排序在处理记录本身就是基本有序的，和记录数比较少的时候具有较高的效率

希尔排序

首先，需要使得待排序的个数变少，即将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序，注意只是基本有序时，再对全体记录进行一次直接插入排序。

基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小基本在中间

分割待排序记录的目的是减少待排序记录的个数，并使得整个序列向基本有序发展。–》采用跳跃分割的策略：将相距某个增量的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

//希尔排序算法
void shellsort(Sqlist l)
{
	int i, j, k = 0;
	int increment = l->length;
	do
	{
		increment = increment / 3 + 1;//增量排序
		for (i = increment + 1; i <= l->length; i++)
		{
			if (l->r[i] < l->r[i - increment])//需要将L->r[i]插入有序增量子表
			{
				l->r[0] = l->r[i];//暂存在L->[0]
				for (j = i - increment; j > 0 && l->r[j]; j -= increment)
				{
					l->r[j + increment] = l->r[j];//记录后移，查找插入位置
				}
				l->r[j + increment] = l->r[0];//插入
			}
		}
	} while (increment > 1);
}

主要是跳跃排序的思想。以书本上的例子为例，一开始increment=4，按4个数据跳，后俩increment=2，按两个数据跳，再最后increment=1,按一个数据跳，相当于一开始进行粗筛，接下来慢慢进行细筛选

希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃的移动，使得排序的效率提高

但增量排序的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法

时间复杂度一般为O( n 3 2 n^ frac{3}{2} n23​)

堆排序

可以做到每次在选择到最小记录的同时，并根据比较结果对其他记录做出响应的调整，从而促使排序的总体效率提高.

堆排序，就是对简单排序进行的一种改进。

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

根节点一定是堆中所有结点最大（小）者。较大（小）的结点靠近根结点（并不绝对）

堆排序算法

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

即：一开始把排序数据构建成一个大顶堆，然后每次找到一个较大值进行一次排序交换时，要让剩余的数据仍旧满足大顶堆的结构，这就为后面继续排序带来了便捷和高效

• 如何由一个无序序列构建成一个堆
• 如何在输出堆顶元素后，调整剩余元素成为一个新的堆

整个排序过程分别为两个for循环，第一个循环要将完成的就是将现在的待排序序列构建成一个大顶堆。第二个循环要完成的就是逐步将每个最大值的根结点与末尾元素交换，并且再调整其为大顶堆

void swap(Sqlist L, int i, int j)
{
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}

//构建最大顶堆

void heapadjust(Sqlist l,int s, int m)
{
	//本函数调整l->r[s]的关键字，使得l->r[s..m]成为一个大顶堆
	int temp, j;
	temp = l->r[s];
	for (j = 2 * s; j <= m; j *= 2)//沿关键字较大的孩子结点向下筛选
	{
		if (j < m && l->r[j] < l->r[j + 1])
		{
			++j;//j为关键字中较大的记录的下标
		}
		if (temp >= l->r[j])
		{
			break;//rc应插入在位置s上
		}
		l->r[s] = l->r[j];
		s = j;
	}
	l->r[s] = temp;//插入
}

//对顺序表进行堆排序

void HeapSort(Sqlist l)
{
	int i;
	for (i = l->length / 2; i > 0; i--)
	{
		heapadjust(l, i, l->length);//把l中的r构建成一个大顶堆
	}
	for (i = l->length; i > 1; i++)
	{
		swap(l, 1, i);//将堆顶记录和当前未经排序子序列最后一记录交换
		heapadjust(l, 1, i - 1);//将l->r[1...i-1]重新调整为大顶堆
	}
}

完全二叉树的性质，若当前结点序号为s，则其做孩子的序号一定时2s，右孩子的序号一定时2s+1，它们的孩子当然也是以2的位数序号增加

堆排序的运行时间主要小号在初始构建堆和在重建堆时的反复筛选上。

在构建堆的过程中，完全二叉树从最下层最右边的非终端结点开始构建，构建堆的时间复杂度为O(n)

正式排序时，重建堆的时间复杂度为O（nlogn)

总体来说，堆排序的时间复杂度为O（nlogn）

但由于记录比较与交换时跳跃式进行的，因此堆排序也是一种不稳定的排序方法

而且，由于初始构建堆所需的比较次数较多，因此，它并不适合排序序列个数较少的情况。

归并排序

归并排序算法，将原本无序的数组序列，通过两两排序后再合并，最终获得了一个有序的数组。其像一个倒置的完全二叉树，效率高。

归并排序算法

归并，在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表

归并排序，就是利用归并的思想实现的排序方法。其原理是假设初始序列含有n个记录，则可可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到【n/2】个长度为2或1的有序子序列；再两两归并,…,如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序

//对输入的元素进行排序
//将有序的sr[i..m]和sr[m+1..n]归并成有序的tr[i..n]
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++)//将sr中记录由大到小地并入tr
	{
		if (sr[i] < sr[j])
		{
			tr[k] = sr[i++];
		}
		else
		{
			tr[k] = sr[j++];
		}
	}
	if (i <= m)
	{
		for (l = 0; l <= m - i; l++)//将剩余的sr[i..m]复制到tr
			tr[k + l] = sr[k + l];
	}
	if (j <= n)
	{
		for (l = 0; l <= n - j; l++)
		{
			tr[k + l] = sr[j + 1];//将剩余的sr[j..n]复制到tr
		}
	}
}


//实现将数组中的元素提取并排序
void Msort(int sr[], int tr1[], int s, int t)
{
	int m;
	int tr2[MAXSIZE + 1];
	if (s == t)
	{
		tr1[s] = sr[s];
	}
	else
	{
		m = (s + t) / 2;//将sr[s..t]平分为sr[s..m]和sr[m+1..t]
		Msort(sr, tr2, s, m);//递归将sr[s..m]归并为有序的tr2[s..m]
		Msort(sr, tr2, m + 1, t);//递归将sr[m+1..t]归并为有序的tr2[m+1..t]
		Merge(tr2, tr1, s, m, t);//将tr2[s..m]和tr2[m+1..t]归并到tr1[s..t],实现排序的功能
	}
}

//对顺序表进行归并排序
void mergesort(Sqlist l)
{
	Msort(l->r, l->r,1, l->length);
}

归并排序的总的时间复杂度为O（nlogn）,这是归并排序算法中最好，最欢，平均的时间性能

归并排序的空间复杂度为O(n+logn)

由于归并排序只需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法

但同时归并排序是一种比较占用内存，但效率高且稳定的算法。

利用迭代的方式实现归并排序

//将sr[]中相邻长度为s的子序列两两归并到tr[]
void mergepass(int sr[], int tr[], int s, int n)
{
	int i = 1;
	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];
		}
	}

}


//对顺序表l进行非递归排序
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);
		k = 2 * k;//子序列长度加倍
		mergepass(tr, l->r,k, l->length);
		k = 2 * k;//子序列长度加倍
	}
}

非递归的迭代方法，避免了递归时深度为 l o g 2 n log_{2}n log2​n的栈空间，空间只是用到申请归并临时用的tr数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有了一定的提升，应该说，使用递归排序时，尽量考虑用非递归方法

快速排序（very important）

快速排序是冒泡排序的升级，都属于交换排序。即通过不断比较和移动交换来实现排序的。凡是其实现过程，增大多了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数

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

//交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在的位置，此时在它之前（后）均不大（小）于它
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(lowr[low]<=pivotkey)
		{
			low++;
		}
		swap(l, low, high);//将比枢轴记录大的记录交换到高端
	}
	return low;//返回枢轴所在的位置
}


//对顺序表l中的子序列l->r[low..high]作快速排序
void qsort(Sqlist l, int low, int high)
{
	int pivot;
	if (low < high)
	{
		//partition()函数要做的就是，先选取当中的一个关键字，想尽办法将它放进一个位置，使得它左边的值都比它小，右边的值都比它大，这样的关键字成为枢轴
		//将l->r[low..high]一分为二，算枢轴值pivot
		pivot = Partition(l, low, high);
		qsort(l, low, pivot - 1);//对低子表进行递归排序
		qsort(l, pivot + 1, high);//对高子表进行递归排序
	}
}


//对顺序表L作快速排序
void quicksort(Sqlist l)
{
	qsort(l, 1, l->length);
}

快速排序的时间性能取决于快速排序递归的深度

在最优的情况下，快速排序算法的时间复杂度为O(nlogn),空间复杂度为O(logn)，在最坏的情况下，快速排序算法的时间复杂度使O(n2)，空间复杂度为O(n)，平均情况下，快速排序算法的时间复杂度为O(nlogn),空间复杂度为O(n)

但快速排序算法的比较和交换使跳跃进行的，因此快速排序是一种不稳定的排序方法。

快速排序优化 1.优化选取枢轴

传统的快速排序算法的往往选取L.r[1]作为枢轴，但排序速度的快慢取决与L.r[1]的关键字处在整个序列中的位置，L.r[1]太大或太小都会影响性能。

在显示中，待排序的序列极有可能是基本有序地，此时，总是固定选取第一个关键字作为首个枢轴变得极为不合理的做法。

随机选取枢轴方法：随机获得一个low与high之间的数rnd

三数取中法：即取三个关键字先进性排序，将中间数作为枢轴，一般取最左端，右端和中间三个数。

	int pivotkey;

	int m = low + (high - low) / 2;//计算数组中间的元素的下标
	if (l->r[low] > l->r[high])//交换左端与右端数据，保证左端较小
		swap(l, low, high);
	if (l->r[m] > l->r[high])//交换中间与右端数据，保证中间较小
		swap(l, high, m);
	if (l->r[m] < l->r[low])//交换中间与左端数据，保证左端较小
		swap(l, m, low);

	pivotkey = l->r[low];//用子表的第一个记录作枢轴记录

九数取中法：先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从者三个中数当中再取出一个中数作为枢轴

2.优化不表的交换

//交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在的位置，此时在它之前（后）均不大（小）于它
int Partition(Sqlist l, int low, int high)
{
	int pivotkey;

	int m = low + (high - low) / 2;//计算数组中间的元素的下标
	if (l->r[low] > l->r[high])//交换左端与右端数据，保证左端较小
		swap(l, low, high);
	if (l->r[m] > l->r[high])//交换中间与右端数据，保证中间较小
		swap(l, high, m);
	if (l->r[m] < l->r[low])//交换中间与左端数据，保证左端较小
		swap(l, m, low);

	pivotkey = l->r[low];//用子表的第一个记录作枢轴记录
	l->r[0] = pivotkey;//将枢轴关键字备份到L->r[0]中
	while (low < high)//从表的两端交替地向中间扫描
	{
		while (low < high && l->r[high] >= pivotkey)
		{
			high--;
		}
		//swap(l, low, high);//将比枢轴记录小的记录交换到低端
		l->r[low] = l->r[high];//采用替换而不是交换的方式进行 *** 作
		while(lowr[low]<=pivotkey)
		{
			low++;
		}
		//swap(l, low, high);//将比枢轴记录大的记录交换到高端
		l->r[high] = l->r[low];//采用替换而不是交换的方式进行 *** 作
	}
	l->r[low] = l->r[0];//将枢轴数值替换会l.r[low]
	return low;//返回枢轴所在的位置
}

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

#define MAX_LENGTH 7
//用于快速排序时判断是否选用插入排序阈值

void qsort1(Sqlist l, int low, int high)
{
	int pivot;
	if ((high - low) > MAX_LENGTH)
	{
		pivot = Partition(l, low, high);
		qsort(l, low, pivot - 1);//对低子表进行递归排序
		qsort(l, pivot + 1, high);//对高子表进行递归排序
	}
	else
	{
		insertsort(l);
	}
}

4.优化递归 *** 作

void qsort2(Sqlist l, int low, int high)
{
	int pivot;
	if ((high - low) > MAX_LENGTH)
	{
		while (low < high)
		{
			pivot = Partition(l, low, high);
			qsort2(l, low, pivot - 1);
			low = pivot + 1;//尾递归
		}
	}
	else
	{
		insertsort(l);
	}
}