数据结构——排序算法分析与总结

一、插入排序

1、直接插入排序

核心思想：把后一个数插入到前面的有序区间，使得整体有序

思路：先取出数组中第一个值，然后再用tmp逐渐取出数组后面的值，与前面的值进行比较，假如我们进行的是升序排序，那么此时前面排序好的数组中，最后一个值最大，如果tmp大于它，就插入后面，否则end -- 往前走，进行比较，（注意：此时数组也要往后赋值），找到比它小的元素，则插在那个元素后面即可，如果直到为0的时候，仍然小于，则把它放在下标为0的位置。

最坏情况(数组元素逆序)：每次插入，元素都要往后移动

• 移动次数：1 +2 +3…+ n => 等差数列 ==>O(N^2)

最好情况：(接近有序或者有序)，基本不用移动数据 ->O(N)、

稳定性：稳定 

• 将x插入到[0,end]的有序区间的时候，当区间元素和x的值相同的时候，是将x插入到该区间元素后面，二者的相对顺序不变

图文演示：假如a[ 5 ] = {3 , 2, 1, 4, 5}

代码演示：

//插排二
//时间复杂度 O(N^2)
// 最坏情况 ：逆序
// 最好情况： 顺序或者接近有序 O（N)
void InsertSort(int* a, int n) //n表示数组有多少个元素
{
	for (int i = 0; i < n - 1; i++) //只需要走n-1个元素即可，防止越界
	{
		int end = i; //后面下标
		int tmp = a[end + 1]; //存下后面的值
		while (end >= 0) //与前面下标元素进行比较
		{
			if (a[end] > tmp) { //待插入元素小于前面元素，则数组往后走一位
				a[end + 1] = a[end];
				end--;
			}
			else break; //找到比待插入元素小的
		}
		a[end + 1] = tmp;  //插入当前位置
	}
}

2、希尔排序

核心思想：

1.先选定一个gap，把待排序数据分组，所有距离为gap分在同一组内，并对每一组内的记录进行排序。

预排序：目的是让数组更接近于有序，这样子后续gap为1进行直接插入排序，效率就是O(N)
2.然后取重复上述分组和排序的工作，当到达gap=1时，就是直接插入排序，整体就有序了

• gap越大：预排序越快，预排序后越不接近有序
• gap越小：预排序越慢，预排序后越接近有序。
• 数据是逆序的时候，预排序完成就接近有序，此时预排序的效果最好。

图文演示：

时间复杂度：O(N^1.3)

稳定性：不稳定

• 相同的值,预排序时可能分到不同的组里面,导致相对顺序发生改变

写法1：多组进行排序

//多组一起进行预排序
void Shellsort1(int* a, int n)
{
	//int gap = 1; //如果gap为1 则为插入排序
 
	//把间隔为gap的数组同时排
	int gap = n;
	while (gap > 1)
	{
		gap /= 2; //gap>1 都是预排序 接近有序
		//gap=gap/3+1;
		for (int i = 0; i < n - gap; i++)//注意:i的范围！ 否则end+gap会越界
		{
			int end = i;//end的范围:[0,n- gap -1]
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];//把a[end]往后移动,以gap为间隔的为一组,所以移动到a[end+gap]位置
					end -= gap;//下一轮循环,以gap为间隔的为一组,前一个数(end-gap位置对应的值)和 tmp 比较
				}
				else break;
			}
			a[end + gap] = tmp;
		}
	}
}

写法2：每一组分别进行预排序

每一组都进行预排序

• 一次只排序间隔为gap的元素(同组元素)，一共有gap组，所以要循环gap次

需要变动的位置：循环gap次，每次处理一组！

• 每一组的起始位置是当前组的组号，然后每次变化范围:  gap

//多组一起进行预排序
void Shellsort2(int* a, int n)
{
	//int gap = 1; //如果gap为1 则为插入排序
 
	//把间隔为gap的数组同时排
	int gap = n;
	while (gap > 1)
	{
		//目的是为了保证最后能让gap为1,进行直接插入排序
		gap /= 2; //gap>1 都是预排序 接近有序
		//gap=gap/3+1;
		for (int j = 0; j < gap; j++) {
			for (int i = j; i < n - gap; i += gap)//注意:i的初始值！！和变动范围 i+=gap
			{
				int end = i;//end的范围:[0,n- gap -1]
				int tmp = a[end + gap];//下一轮循环,以gap为间隔的为一组,前一个数(end-gap位置对应的值)和 tmp 比较
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else break;
				}
				a[end + gap] = tmp;//以gap为间隔的为一组,把tmp放在end + gap位置 
			}
		}
	}
}

---

二、选择排序

1、直接选择排序

核心思想：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

时间复杂度：遍历一遍才能选出一个数或者两个数，无论什么情况都是O(N^2)。

稳定性：不稳定

• 在区间当中找到最大和最小的数和区间左右端点位置的值交换，可能会导致两个相同的值相对顺序发生变化

图文演示：

代码演示：

方法一：每次选择一个数，比如一个移动范围内的最小值

//直接选择排序 
//写法1：每次选择一个数
void SelectSort1(int* a, int n)
{
	int begin = 0;
	while (begin < n - 1) {//当区间只有一个元素就不需要选了所以循环条件为：end > 0
		int mini = begin;
		for (int i =  begin + 1; i < n; i++) {// 在[begin, n-1]中选取最小值
			if (a[mini] > a[i]) mini = i;
		}
		swap(a[begin], a[mini]);
		begin++;
	}
}

方法2：每次选择两个数

思路：每次从要排序的区间当中找到最大和最小的数，如果是排序，那么把他区间的最大的数和区间右端点对应值交换，把区间中最小的数和区间左端点对应值交换，然后缩小区间重复上述步骤，直到区间只有一个数。

//写法2：每次选择两个数
void SelectSort2(int* a, int n)
{
	int begin = 0, end = n - 1;
	
	while (begin <end)
	{
		int mini = begin, maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini]) mini = i; //找出最小的值下标
			if (a[i] > a[maxi]) maxi = i; //找出最大的值下标
		}
		
		swap(a[begin], a[mini]);//最小值放到begin位置
 
		//注意：如果begin和maxi一样，即begin就是最大值的位置
		//因为下面一步begin位置和值已经和mini位置交换了,所以就导致了mini位置放的才是最大值了
		//所以需要特判一下,如果begin和maxi相同,那么经过上面一步交换之后,mini位置放的才是最大值
 
		if (begin == maxi) maxi = mini;//加以优化，避免最大的数出现在第一个
		
		swap(a[end], a[maxi]);//最大值放到end位置
		begin++, end--; //缩小区间
	}
}

2、堆排序

核心思想：

     1.首先需要先建堆，只需要从最后一个叶子结点的父节点开始，在数组当中从后往前去向下调整即可共n个元素。

• 共n个元素，最后一个结点的下标为: n -1
• 它的父亲结点的下标为:parent = (child - 1)/2 = (n - 1- 1)/2

        2.建好堆之后，将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个数不参与向下调整，然后缩小堆中有效数据个数，剩下的元素进行向下调整，其余数又成一个大堆…重复上述步骤，直到堆中只剩下一个元素。

       注意：

            a、排升序建大堆

            b、排降序建小堆

对于N个元素建堆，我们用筛选法建堆，从 N/2 (即最后一个非叶子节点)的元素开始建堆

时间复杂度分析：无论哪种方法建堆：都是O(N*logN)

• 建堆的时间复杂度 + 调堆的时间复杂度 N*logN

稳定性：不稳定

• 在调堆的时候，可能会导致相同元素的相对顺序改变

图文演示：

代码演示：

//排升序最后是建大堆
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1; //默认是左孩子，右孩子比左孩子大1
	while (child < n)
	{
		//1、选出左右孩子中大的那一个
		if (child+1<n && a[child + 1] > a[child]) //建一个大堆
		{
			child += 1;
		}
		//2、然后再与父亲比较，若比父亲大就发生交换
		if (a[child] > a[parent])//让父亲永远大于儿子
		{
			Swap(&a[child], &a[parent]);
			parent = child; //交换下标
			child = parent * 2 + 1;
		}
		else break; //记得跳出循环
	}
}
 
//第一个和最后一个交换，把它不看作堆里面，前n-1个数向下调整，选出次大的数，再跟倒数第二个位置交换
void HeapSort(int* a, int n)
{
	//把数组建成大堆
	for (int i = (n-1-1) / 2; i >= 0; i--) //筛选法选出最后一个非叶子节点
	{
		AdjustDwon(a, n, i); //建大根堆
	}
	int end = n - 1;
	while (end > 0)//开始向下调整
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		--end;
	}
}

 举例：将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在整个排序过程中，数组的顺序是_____。（6-5-3-2-4-1-7）

---

三、交换排序

1、冒泡排序

核心思想：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

• n个元素，只需排序n-1次，就可以让n个数有序

优化：如果提前有序了（某一趟冒泡当中没有元素交换），就不需要再冒泡了。

时间复杂度：

• 最坏情况：第一轮：N个数比较交换，第二轮：N-1个数比较交换… ，此时相当于是等差数列，复杂度为O(N^2)
• 最好情况：数组接近有序/有序，某一趟冒泡当中没有元素交换直接结束，O(N)

稳定性：稳定

• 相邻元素进行比较,相同的元素之间不进行交换

void BubbleSort(int* a, int n)
{
//每一趟可以确定一个元素到准确位置,n个元素只需要进行n-1趟
	for (int i = 0; i < n - 1; i++) 
	{
		bool flag = 0;
//每一趟都可以少比较一个已经确定好的数
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1]) {
				swap(a[j], a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0) break; //说明没有进行交换，此时已经有序，跳出即可
	}
}

 2、快速排序

快速排序是基于 分治法 的一个排序算法。

核心思想：取待排序区间上的某一个元素作为基准值，根据处理方法，将待排序区间上的元素划分为：左区间的元素小于基准值，右区间的元素大于基准值，然后对左右区间重复这个过程，直到所有元素都排列在相应位置上为止

代码演示：

最简便模板：（记住这个即可）

void QuickSort(int q[], int l, int r) //先分治再递归
{
	if (l >= r) return; //递归截止条件
 
	int x = q[l + r >> 1]; // 但是一般选择第一个或者最后一个
	int i = l - 1, j = r + 1; //注意：l-1 和 r + 1
	while (i < j)//x左边都是小于x的，右边都是大于x的 
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		//假设上面截止时且满足i < j，此时a[i] >= x, a[j] <= x 
		if (i < j) swap(q[i], q[j]);
	}
	QuickSort(q, l, j);
	QuickSort(q, j + 1, r);
}

比如快速排序的第一趟结果：

比如关键字（20，15，14，18，21，36，40，10）以20为基准进行排序。
第一步，先从后往前找出小于基准数20的数，并与基准数20交换得：10,15,14,18,21,36,40,20)。
第二步，再从前往后找出大于基准数20的数，并与基准数20交换得：10,15,14,18,20,36,40,21)。
再一次执行第一步与第二步，直到最后基准数左边的序列都小于基准数，基准数右边的序列都大于基准数。
所得结果：（10,15,14,18,20,36,40,21)。为第一趟排序的结果。

---

四、归并排序

核心思想：根据左右区间的值，计算一个中间值mid，先让[left，mid] [mid+1，right]两个区间有序， 然后这两个有序区间进行归并 (归并到临时数组)，将临时数组的内容拷贝回去。

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定

• 归并的时候，相同的值，先拷贝左区间的值，再拷贝右区间的

归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1。

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为14；（因此我们可以用 归并算法 来计算逆序数）

代码演示：

const int N = 10010;
int tmp[N];
void merge_sort(int q[], int l, int r) //先归并再分治
{
	if (l >= r) return; //递归截止
	int mid = l + r >> 1; //记录中间值
	merge_sort(q, l, mid);   
	merge_sort(q, mid + 1, r);
	
	int k = 0, i = l, j = mid + 1; //k表示tmp储存的元素数量
 
	while (i<=mid && j<=r) //注意下面都是<=，保证了它的稳定性
	{
		if (q[i] <= q[j])tmp[k++] = q[i++]; 
		else  tmp[k++] = q[j++];
	}
 
	//防止分布不均
	while (i <= mid) tmp[k++] = q[i++];
	while (j <= r) tmp[k++] = q[j++]; 
	//注意i的范围是[l,r]		
	for (i = l, j = 0; i <= r; i++,j++) q[i] = tmp[j]; //拷贝
 
}

---

五、计数排序——鸽巢原理

核心思想：统计相同元素出现次数，根据统计的结果将序列写回到原来的序列中

统计每个数据出现的次数 count[a[i]]++
适合数据集中的数组进行排序
  时间复杂度O（N+range）
  空间复杂度 O（range）

稳定性：不稳定

• 计数到count数组中,每个元素已经没有顺序了

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > max)max = a[i];   //找出最大值
		if (a[i] < min)min = a[i];  // 找出最小值		
	}
 
	int range = max - min + 1;  //比如109 100 实际有10个值
	int* count = (int*)malloc(sizeof(int) * range);
	//数组元素进行映射。此时x元素映射在x - min位置
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}
	//将count数组的内容映射回去原数组,此时对应的值为i + min
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(count);
}

---

上述八大排序的稳定性以及复杂度

注意：

1、对于快速排序:如果加了三数取中 + 三路归并 最坏就不是O(N^2)

2、为了绝对的速度选快排，为了省空间选堆排，为了稳定性选归并

3、时间复杂度:O(N*logN)，额外空间复杂度低于O(N)，且稳定的基于比较的排序是不存在的

最后下面我们再提一个排序

---

九、基数排序

代码演示：

bool check(int* arr, int l, int r)
{
	for (int i = l + 1; i < r; i++)
	{
		if (arr[i] < arr[i - 1]) return true;
	}
	return false;
}
 
// 扩大范围 从 0 - 99为基数
void radix_sort(int* arr, int l, int r)
{
#define K 65536
	int* cnt = (int*)malloc(sizeof(int) * K);
	int* temp = (int*)malloc(sizeof(int) * (r - l));
 
	// round 1
	memset(cnt, 0, sizeof(int) * K);
	for (int i = l; i < r; i++) cnt[arr[i] % K] += 1; //求前缀和
	for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
	for (int i = r - 1; i >= l; i--) temp[--cnt[arr[i] % K]] = arr[i]; //记录当前数字应该存放的位置
	memcpy(arr + l, temp, sizeof(int) * (r - l));
 
	// round 2
	memset(cnt, 0, sizeof(int) * K);
	for (int i = l; i < r; i++) cnt[arr[i] / K] += 1; //求前缀和
	for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
	for (int i = r - 1; i >= l; i--) temp[--cnt[arr[i] / K]] = arr[i]; //记录当前数字应该存放的位置
	memcpy(arr + l, temp, sizeof(int) * (r - l));
 
}