博客

• 前言

排序是按照关键字的非递减或非递增顺序对一组记录重新进行排列的操作，是对无规律的一组序列转化为递增或递减的操作。

排序的稳定性：

       当排序记录中的关键字都部相同时，则任何一个记录的无序序列经过排序后得到的结果都唯一，反之，若存在两个或多个关键字相同时，则得到的结果可能不唯一。

       假设Ki=Kj且排序前Ki在Kj之前，排序后Ki仍然在kj之前，则称排序时稳定的，反之，若可能使排序后Ki在Kj之后，则称排序是不稳定的。注意，只要有一组关键字的实例不满足稳定的要求，则该排序算法就是不稳定的。各有各的适用场合。

内部排序和外部排序：

       由于待排序记录的数量不同，使得排序过程中数据所占用的存储设备会有所不同。根据在排序过程中记录所占用的存储设备，可将排序分为两大类：内部排序和外部排序。

       内部排序是的是待排序记录全部存放在内存中进行排序的过程，外部排序指的是由于待排序记录的数量很大，以至内存不能一次全部容纳，在排序过程中仍需对外存进行访问的过程。

• 冒泡排序

基本思想：

       两两相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。之所以叫做冒泡排序，是因为每次将一个最大或最小的数往后沉淀，沉淀到后面的数比它大或比它小为止，类似于泡泡向上浮起来的过程。

 冒泡排序是排序方法中最直观也是最简单的，我们接触的第一种排序方法也是冒泡排序，基本步骤：

  有一个数组a[10]，用变量i表示它的下标(i从0开始）
（1） 比较两个相邻元素a[i]和a[i+1]，如果a[i]>a[i+1]，就交换这两个数的位置；
（2）重复执行第一步，直到比较到最后一对的时候（例：首次是a[8]和a[9]，此时，a[9]的值为该数组的最大值，这个值属于有序数列）；
（3）对所有元素（除了有序数列里的元素），重复执行第一步和第二步，每执行完一次，都会找到当前比较的数里最大的那个（有序数列就会增加一个）；
（4）随着参与比较的元素越来越少，最终没有任何一对元素需要比较的时候，排序完成。

void BubbleSort(int a[],int n)
{
	for(int i=0;i<n;i++)
	for(int j=0;j<n-i-1;j++)
	if(a[j]>a[j+1]) //两两比较 
	swap(a[j],a[j+1]);
}

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：由于交换的if条件是a[j]>a[j+1]，所以如果等于的话并没有交换，所以冒泡排序是一种稳定排序算法。

冒泡排序较稳定，可用于链式存储结构，时间复杂度较高，当n较大，初始记录无序时，不宜采用此方法

• 选择排序

通过n-1次关键字比较，从n-i+1个记录中选择关键字最小的记录，并和第i个记录交换。

选择排序是经过一次一次在无序区间中找到最值，放到无序区间的前一个位置，基本步骤：

（1）设待排序的记录存放在数组r[n]中，第一趟从r[1]开始，通过n-1次比较，从n个记录中选取最小的记录，记为r[k]，交换r[1]和r[k]

（2）第二趟从r[2]开始，通过n-2次比较，从n-1个记录中选出关键字最小的记录，记为r[k]，交换r[2]和r[k]

（3）以此类推，第i趟从r[i]开始，通过n-i次比较，从n-i+1个记录中选取最小关键字记录，记为r[k]，交换 r[i]和r[k]

（4）经过n-1趟，排序完成

void SelectSort(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		int k=i;
		for(int j=i+1;j<n;j++) //寻找最小元素的下标 
		if(a[j]<a[k])
		k=j;
		
		if(k!=i)  //放在已排序好的区间后面 
		swap(a[i],a[k]);
	}
}

时间复杂度：O（n^2)

空间复杂度：O（1）

稳定性：就算法本身来说，是一种稳定排序

选择排序可用于链式存储结构，移动记录次序较少，当每一记录占用空间较多时，此方法比插入排序快

• 插入排序

插入排序（直接插入排序）是一种最简单的排序方法，其基本操作是将一条记录插入到已排号的序列当中，从而得到一个有序的记录。

算法步骤：

（1）设待排序数组a[n]，默认a[0]是一个有序序列

（2）循环n-1次，每次将为排序序列插入到前面的已排序序列当中，将已排序序列区间长度加1，未排序区间长度减一

（3）重复（2）直到未排序区间长度为0

void InsertSort(int a[],int n)
{
	for(int i=1;i<n;i++)
	{
		int end=a[i]; //记录未排序序列的第一个元素 
		int j=i-1;
		while(j>=0&&a[j]>end) //寻找位置 
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=end; //插入 
	}
}

时间复杂度：O（n^2)

空间复杂度：O（1）

稳定性：稳定排序

算法简单稳定，容易实现，也适用于链式存储结构，在单链表中只需修改指针，更适用于初始记录基本有序的情况。对与查找插入位置，我们可以用二分查找获取位置。

• 希尔排序

       希尔排序实质上是采用分组插入的方法，先将整个待排序记录序列分成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组，这样经过几次分组后，整个序列基本有序，在对全体进行插入排序，希尔排序记录的分组，不是简单的逐段分组，而是将相隔某个记录增量的记录分成一组。

希尔排序的基本步骤：

（1）第一趟取增量gap（gap<n）把全部几记录分成gap个组，对每组进行直接插入排序

（2）第二趟取gap=gap/2，重复第一步

（3）以此类推，直到gap=1，再对整个序列排序一次

​
void ShellSort(int a[],int n)
{
    for(int gap=n/2;gap>0;gap/=2)
    for(int i=gap;i<n;i+=gap)
    {
    	int end=a[i];
    	int j=i-gap;
    	while(j>=0&&a[j]>end)
    	{
    		a[j+gap]=a[j];
    		j-=gap;
        }
	a[j+gap]=end;
   }
}

​

注意这里的gap不是区间长度，而是区间的跨度，例如数组a[10]，此时gap=n/2=5；每个区间的跨度为5，每次gap取上一次的一半，第一次就分为了5组分别为[0,4]、[1,5] 、[2,6]、 [3,7] 、[4,8]、 [5,9]；注意是左闭右闭区间。希尔排序做到了跳跃式移动，从而使最后一次gap=1时，序列已基本有序，因此较直接插入排序时间复杂度低。

时间复杂度：时间复杂度比较复杂，通常认为O(n*log 2  n)，当n趋近于无穷大时，可以为O（n(log2 n)^2)

空间复杂度：O（1）

稳定性：不稳定

        希尔排序只能用于顺序存储结构，不能用于链式存储结构，增量gap可以有各种取法，但最后一次gap必须等于1, 总比较次数和移动次数较直接插入排序少，当n越大，序列越无序时，效果越明显。

• 堆排序

        堆排序是一种树性选择排序，再排序过程中，将排序序列a[n]看成一个完全二叉树，利用二叉树双亲节点与孩子节点的内在联系，在当前无序的序列中，选择的关键字最大（或最小）的记录。

        堆的定义为 a[i]>=a[2*i]&&a[i]>=a[2*i+1]  或  a[i]<=a[2*i]&&a[i]<=a[2*i+1]，通俗的理解就是在完全二叉树中，一个节点必须同时大于它的左节点和右节点。前者为大根堆后者为小根堆。

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得当前无序的序列中选择关键字最大（或最小）的记录变得简单，步骤为：

（1）按照堆的定义将待排序序列a[n] 调整为大根堆，这个过程称为初建堆，交换a[1]和a[n] ，则a[n]为关键字的最大记录

（2）将a[n-1]重新调整为堆，交换ra[1]和a[n-1]，此时a[n-1]为关键字最大记录

（3）循环n-1次，直到交换a[1]和a[2]为止

所以实现堆排序需要熟悉两个问题：建初堆、调整堆

调整堆就是比较此节点与它的左右孩子节点，选孩子节点中取最大或者最小的一个，与此节点比较，如果不满足条件就交换，直到进行到叶子节点为止。而要将一个无序序列调整为堆，就必须将其所在的二叉树中以一个节点为根的子树都调整为堆。

int a[10] = {1,3,2,4,8,9,7,5,6,0};

void adjust(int root, int n)
{
	int node = root * 2 + 1; //左子节点

	while(node < n)
	{
		//如果右节点比左节点大，node指向右节点
		if(node + 1 < n && a[node] < a[node+1])
			node++;

		if(a[node] < a[root])
			break;

		swap(a[node], a[root]);

		root = node;
		//向下
		node = node * 2 + 1;
	}
}

void heapSort(int n)
{
	//从最后一个非叶子节点往上调整
	for(int i = n/2; i >= 0; i--)
		adjust(i, n);

	for(int i = n-1; i > 0; i--)
	{
		//把根节点放到后面
		swap(a[0], a[i]);
		adjust(0, i);
	}
}

时间复杂度：O(nlog2 n)

空间复杂度：O(1)

稳定性：不稳定

       堆排序只能用于顺序存储结构，初始建堆比较次数较多，记录较少时不宜采用，在最坏情况下较快速排序而言是一个有点，记录较多时较为高效。

• 归并排序

        归并排序类似与二分查找，都是二分当前区间，分别进行操作，可通过递归与送代进行实现，书面上定义是将两个或两个以上的有序表合成一个有序表的过程，将两个有序表合成一个有序表的过程称为2-路归并，2-路归并最为简单常用。

归并排序的算法思想：

       假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列，再两两归并。。。如此重复，直到得到一个长度为n的有序序列为止。

2-路归并排序将r[n]中的记录放到t[n]中，当序列长度等于1时，递归结束，否则：

（1）将当前序列一分为二，求出分裂点mid=(l+r)/2

（2）对子序列r[l]-r[mid]递归，进行归并排序，结果放在t[l,mid]中

（3）对子序列r[mid+1,r]递归，进行归并排序，结果放在t[mid+1,r]

（4）将两个有序的子序列t[l,mid]，t[mid+1,r]归并为一个有序的序列放入r[l,r]中

void Merge(int a[], int left, int center, int right, int n) 
{
	int *t = new int[n];//存放被排序的元素
	int i = left;
	int j = center + 1;
	int k = 0;
	while (i<=center && j<=right)
		if (a[i] <= a[j])     t[k++] = a[i++];
		else                  t[k++] = a[j++];

	if (i == center+1)
		while (j <= right) t[k++] = a[j++];
	else
		while (i <= center) t[k++] = a[i++];

	//把t[]的元素复制回a[]中left到right段
	for (i=left,k=0; i<=right; i++,k++)
		a[i] = t[k];
	//释放内存
	delete []t;
}
void MergeSort(int a[], int left, int right) 
{
	if (left < right) 
	{
		int center = (left + right) / 2;//取得中点
		MSort(a, left, center);
		MSort(a, center+1, right);
		Merge(a, left, center, right, right-left+1);
	}
}

时间复杂度：O(nlog2n)

空间复杂度：O(n)

稳定性：稳定排序

归并排序可用于链式结构，且不需要附加存储空间，但递归实现任需要开辟相应的递归工作栈。

• 快速排序

      快速排序在算法竞赛中用到的比较多，快速排序比冒泡排序要快很多，C语言中也有快速排序的函数qsort()，不过最好去理解一下底层代码实现。在冒泡排序过程中，只对两个相邻的记录进行比较，因此每次比较只能消除一个逆序，如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度，快速排序就是利用这个原理。

基本步骤：

（1）选择待排序记录中第一个记录作为基准，将基准暂存在r[0]的位置上，假设两个指针low和high，初始分别指向表的下界和上界

（2）从表的最右侧位置向左寻找第一个比基准数小的位置，从表的最左侧寻找第一个比基准数大的位置，交换两个元素

（3）重复（2）当low==high时，将基准数放到low位置处的元素判断大于还是小于后，与基准数交换

（4）此时以基准数的位置为分界点，将序列分为两个子序列，分别进行（1），（2），（3）操作，直到序列的长度为1为止

void QuickSort(int a[], int low ,int high) 
{
	if(low<high) 
	{ //判断是否满足排序条件，递归的终止条件
		int i = low, j = high;   
		int x = a[low];    
		while(i<j) 
		{
			while(i<j && a[j] >= x) j--;  
			
			if(i<j) a[i++] = a[j];   
			
			while(i<j && a[i] <= x) i++; 
			
			if(i<j) a[j--] = a[i];
		}
		a[i] = x;   
		QuickSort(a, low ,i-1); 
		QuickSort(a, i+1 ,high);
	}
}


//---------------------------------
//非递归版
#include<bits/stdc++.h>
using namespace std;

int a[1000];

int quick(int i, int j)
{
	int x = a[i];
	
	while(i < j)
	{
		while(i < j && a[j] >= x) j--;
		if(i < j)
			a[i++] = a[j];
		
		while(i < j && a[i] <= x) i++;
		if(i < j)
			a[j--] = a[i];
	}
	
	a[i] = x;
	
	return i;
}

void quicksort(int len)
{
	stack<int> s;
	
	int i = 0, j = len - 1;
	
	s.push(i);
	s.push(j);
	
	while(!s.empty())
	{cout << 'd' << endl;
		j = s.top(), s.pop();
		i = s.top(), s.pop();
		
		int mid = quick(i, j);
		
		if(i < mid - 1)
			s.push(i), s.push(mid - 1);
		
		if(j > mid + 1)
			s.push(mid + 1), s.push(j);
			
			
	}
}

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	cin >> a[i];
	
	quicksort(n);
	
	for(int i = 0; i < n; i++)
	cout << a[i] << ' ';
	
	return 0;
}



/*
6
5 2 3 4 1 0
*/

时间复杂度：O(nlogn)

空间复杂度：O(log2n)—O(n)

稳定性：不稳定

快速排序过程中需要地位表的上界和下界，所以适合顺序结构，很难用于链式结构，当n非常大时，快速排序是所有排序过程中最快的一种，所以适合用于初始记录无序、n较大时的情况。