常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)

目录

一.插入排序

1.插入排序的基本思想:

2.插入排序的时间复杂度 O(N²)

3.插入排序的空间复杂度 O(1)

稳定性概念!!!:

4.插入排序的稳定性——稳定

 二.冒泡排序

1.冒泡排序思想:

2.冒泡排序时间复杂度O(N²):

3.冒泡排序空间复杂度O(1):

4.冒泡排序的稳定性——稳定

5.比较插入与冒泡排序

三.希尔排序

1.希尔排序的思想:

2.希尔排序时间复杂度gap=3时:O(N*log3 N) gap=2时:O(N*logN)

3.希尔排序空间复杂度O(1)

4.希尔排序的稳定性——不稳定

四.选择排序

1.选择排序的思路很简单:

2.选择排序的时间复杂度O(N²)

3.选择排序的空间复杂度O(1)

4.选择排序的稳定性——不稳定

五.快速排序

1.【1】递归版本

快排递归版本一共多少种写法?:

快排大致的递归思路:

前提:

(1)hoare法(念hao er)

(2)挖坑法

(3)前后指针法

①稍微拉胯一点的写法(自己和自己交换的情况没有优化)

 ②第二种稍微拉胯一点的写法(自己和自己交换的情况没有优化)

③第三种最优写法(自己和自己交换的情况得到优化)

1.【2】 快排递归版本复杂度

(1)时间复杂度(未优化是O(N²) 优化最坏情况后是O(N*logN))

(2)空间复杂度O(logN)

1.【3】快排的稳定性——不稳定

1.【4】对快排递归时间复杂度的优化

(1)三数取中:

(2)小区间优化

2.快排的非递归版本

3.给出快排所有的代码:(其中主要思路有递归和非递归2种,单排有3种思路,6种写法)

六.归并排序

1.归并递归版本代码:

1.【1】归并递归版本解析

(1)递归思路:

(2)归并思路:

1.【2】归并排序时间复杂度O(N*logN)

1.【3】归并排序空间复杂度O(N)

2.归并非递归版本代码:

2.【1】归并非递归版本解析

七.计数排序

1.计数排序思路:

2.计数排序时间复杂度:O(range + N)

3.计数排序空间复杂度:O(range)

4.计数排序稳定性:不用看,没有意义

八.堆排序

1.堆排序时间复杂度:O(N*logN)

2.堆排序空间复杂度:O(1)

3.堆排序稳定性:不稳定


常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第1张图片

常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第2张图片

一.插入排序

1.插入排序的基本思想:

有一个有序区间,插入一个数据,依旧保持他有序

单趟排序:[0, end]有序 ,把end+1 位置的值a[end+1]插入进入,保持他依旧有序,a[end+1]和前面的有序数组从后往前比较,只要比自己大的都往后放,直到a[end]比tmp小,就跳出循环并把tmp放到这个数的后面,即:a[end + 1] = tmp; 

a[end + 1] = tmp; 正常情况能通过,但是如果放到 else 特殊情况不能通过,比如把最后一个数1插入排序,有序数组2 3 4 5 1 end=3, 5>1, end-- ;end=2, 4>1, end-- ;end=1, 3>1, end-- ;end=0, 2>1, end-- ;end=-1,此时while (end >= 0) 不满足,跳出循环,而我们所说的情况是 在else后面放tmp,所以此时跳出循环就结束了

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)   
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i) //最后一个数下标是n-1,走到n-2位置就比较a[n-2]和a[n-1],就比较完了,所以条件是 i < n - 1
	{
		int end = i;
    //单趟排序:[0, end]有序 end+1位置的值,插入进入,保持他依旧有序
		int tmp = a[end + 1];
		while (end >= 0)           //end走完整个数组就结束
		{ //a[end+1]和前面的有序数组从后往前比较,只要比自己大的都往后放,
//直到a[end]比tmp小,就跳出循环并把tmp放到这个数的后面,即:a[end + 1] = tmp;    
			if (tmp < a[end])     
			{
				a[end + 1] = a[end];
				--end;
			}
			else    //a[end + 1] = tmp; 如果放到 else 特殊情况不能通过,看上面解析
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
int main()
{
	TestInsertSort();

	return 0;
}

2.插入排序的时间复杂度 O(N²)

最坏情况:逆序 O(N²)

用插入排序 排成顺序,比如5,4,3,2,1, i=0时,4和5交换,end-- 1次;数组状态:4,5,3,2,1 i=1时,end-- 2次;数组状态:3,4,5,2,1 i=2时,end-- 3次;数组状态:2,3,4,5,1 i=3时,end--4次

这些次数加起来,相当于是等差数列相加,等差数列求和:(1+n)*n/2=n/2+n²/2 ,可知时间复杂度是O(N²)

最好情况:顺序 O(N) 

因为是顺序,所以每次for循环进去就会break,执行n-1次,时间复杂度就是O(N)

3.插入排序的空间复杂度 O(1)

插入排序没有开辟额外数组,只是函数调用中存储了一些局部变量,是常数个,所以空间复杂度是O(1) .

稳定性概念!!!:

稳定性 :假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j] ,且 r[i] r[j] 之前,而在排序后的序列中, r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的。
总而言之就是一句话:相同的数在排序结束后相对顺序不变就是稳定。

4.插入排序的稳定性——稳定

插入排序思想是把end+1 位置的值a[end+1]插入进入有序数组 [0, end] 中,(假设排升序)a[end+1]从前往后逐一和有序数组 [0, end] 中的数比较,a[end+1]比这个数小,就把这个数往后挪一格,a[end+1]比这个数大,就把a[end+1]放到这个数的后面,如果a[end+1]和这个数一样,也就把a[end+1]放到这个数的后面,不会改变前后顺序,所以插入排序是稳定的。

(温馨提示:但是有的同学说,那我就让它相等时也往后挪不就改变顺序了吗?——这样确实会改变顺序了,但是如果这样说所以的排序都可以变的不稳定,所以我们规定:只要这个排序能变的稳定,那他就是稳定排序

 二.冒泡排序

1.冒泡排序思想:

单趟就是从第一个数开始,把相邻两个数逐次比较,如果前面的数大,就交换这两个数,这一趟下来一定把最大的数放到了最后面,第1趟执行单趟需要拿第一个数和后面的n-1个数逐次比较n-1次,第2趟比n-2……,第n-1趟比较1次(趟数+比较次数=n),需要执行n-1次,比较次数需要加入一个不断增长的值,正好用趟数 i ,因此先写成n-i,i是从0开始,所以要多减1,比较次数写成n-i-1(就是for (j = 0; j < n - i - 1; j++)),第n-1趟是比较1次,第n趟就是比较0次,因此我们就走n趟(就是for (int i = 0; i < n; ++i) )只不过第n趟不比较

优化:

①如果恰好是顺序,那还是比较n²次就很浪费时间,所以加入exchange,只要交换一次就把exchange置为1,如果第一趟进去,发现一次也没交换,那exchange还是0,就是顺序,第一趟跑完后直接break,这种情况时间复杂度直接优化到了O(N),就防止了顺序还要跑n²次的情况。

②其次,只要有序了就不会进行后面的排序:这是exchange定义进第一层循环内的目的,详细讲解:每次进行一趟排序后,发生了交换,exchange变成1,再进行下一趟时,把exchange重置成0,如果这一趟结束exchange如果依然是0,说明在这一趟之前就已经有序了,直接break即可。


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 时间复杂度:O(N^2)
// 最好情况:顺序有序  O(N)
void BubbleSort(int* a,int n )
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n; i++)
	{
	    int exchange = 0;
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j + 1] < a[j])
			{
				exchange = 1;
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
		}
		if (exchange == 0)
			break;
	}
}

void TestBubbleSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	BubbleSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestBubbleSort();

	return 0;
}

2.冒泡排序时间复杂度O(N²):

最坏情况:逆序 次次都要比较,第1趟比较n-1次,第2趟比n-2次……,第n-1趟比较1次,1+2+3+……+n-1还是等差数列求和,所以时间复杂度是O(N²)

最好情况:顺序  刚刚算过,是O(N)

3.冒泡排序空间复杂度O(1):

冒泡并没有开额外数组,只需要存储局部变量即可,所以空间复杂度是O(1).

4.冒泡排序的稳定性——稳定

每一趟冒泡都是比较,(假设排升序)前大于后就交换两个数,如果前小于后就不交换,如果相等也不交换,所以冒泡是稳定的。

5.比较插入与冒泡排序

看似插入和冒泡最好情况都是O(N),最坏情况都是O(N²),但实际上他俩的效率还是有差别的:

举个例子:数组:1 2 3 4 5 6 8 7 这个数组

用插入排序运行几次?:end=0时,1<2,不用换,比较1次;end=1时,2<3,不用换,比较1次;end=2时,3<4,不用换,比较1次;end=3时,4<5,不用换,比较1次;end=4时,5<6,不用换,比较1次;end=5时,6<8,不用换,比较1次;end=6时,8>7,用换,比较1次后,8放到7的位置,7和6再比较一次,7>6,并把7放在6后面就结束。一共比较了8次。

用冒泡排序运行几次?:1和2比较,1<2,不用换,比较一次;2和3比较,2<3,不用换,比较一次;3和4比较,3<4,不用换,比较一次;4和5比较,4<5,不用换,比较一次;5和6比较,5<6,不用换,比较一次;6和8比较,6<8,不用换,比较一次;8和7比较,8>7,用换,比较一次后,交换8和7;一共比较了7次,此时数组是:1 2 3 4 5 6 8 7 ,因为已经发生过交换,exchange=1,则不结束,需要进行第二次比较:1,2比,不换;2,3比,3,4比,4,5比,5,6比,6,7比,都不换,发现exchange=0,break结束冒泡。一共比较了7+6=13次。

这个例子冒泡比插入多走了5次!由此我们发现:如果是顺序有序,那么插入和冒泡是一样的
但是如果是局部有序或者接近有序,那么插入适应性更好,比较次数更少。(比如一个数组整体顺序是乱的,但中间有一段是顺序,也会减少一些比较次数)

总体来说是一个数量级,但是局部有序情况插入还是比冒泡强

三.希尔排序

代码先给出来,我们逐步讲解:

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
void TestShellSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestShellSort();

	return 0;
}

1.希尔排序的思想:

相当于插入排序的优化;我们知道插入排序在 局部有序或者接近有序 的情况下适应性更强,比较次数更少,那我们就想怎么快速把它排成接近有序的数组呢?——进行预排序

(1)预排序(目的使数组接近有序):

方法一(传统法):分组后每一组进行插入排序,分组排大的数更快的到后面小的数更快的到前面接近有序,给数组 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 ,我们可以给出一个gap(假设gap=3),从下标0开始把隔着gap距离的数先进行插入排序,从下标1开始把隔着gap距离的数先进行插入排序,从下标2开始把隔着gap距离的数先进行插入排序,一共gap组,每一组走到下标n-1-gap就结束插入排序, 这样间距是gap的数就是有序的,虽然整体不是有序但是接近有序。(分成gap=3组插入排序)

 常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第3张图片

 举例说明:数组:9, 1, 2, 5, 7, 4, 8, 6, 3, 5,gap=3

先从下标0开始隔着gap=3距离的数进行插入排序后就是:5, 1, 2, 5, 7, 4, 8, 6, 3, 9

数组状态:5, 1, 2, 5, 7, 4, 8, 6, 3, 9

再从下标1开始把隔着gap=3距离的数进行插入排序后就是:5, 1, 2, 5, 6, 4, 8, 7, 3, 9

数组状态:5, 1, 2, 5, 6, 4, 8, 7, 3, 9

再从下标2开始把隔着gap=3距离的数进行插入排序后就是:5, 1, 2, 5, 6, 3, 8, 7, 4, 9

进行gap=3次就变得整体接近有序了,这样怎么实现呢?我们先把插入排序的间距1改成gap,再让每组完整的插入排序从下标0,1,2分别进行gap=3次,每一组走到下标n-1-gap就结束插入排序

    int gap = 3;
	for (int j = 0; j < gap; j++)    //分成gap组
	{
		for (int i = j; i < n - gap; i += gap)    //每组完整的插入排序
		{
			int end = i;            //到下标为i数据的单次插入排序
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

上面我们说要分别从下标0,下标1,下标2开始把间距为gap的一串数进行插入排序,这样需要两层排序,写全要3层循环,但是最优的方法一层循环即可

方法二:,把 i += gap 改成 i++ ,不分组了,过程请看动态图常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第4张图片如果gap越小,越接近有序
gap越大的,大的数据可以更快到最后,小的数可以更快到前面,但是它越不接近有序

(2)最后再直接插入排序

1、gap > 1 预排序

2、gap == 1 直接插入排序

加一层循环,对gap进行控制,通常gap从n/3开始依次缩小,每循环一次gap就/3,gap越小,越接近有序,最后要进行一次插入排序,即:gap=1,但是如果只是每次gap=gap/3,最后有可能不是1,假如gap=8,8/3=2,2/3=0,所以为了最后进行一次插入排序,写成gap=gap/3+1,这样gap最后一次一定是1,并且条件写成while (gap > 1),使gap=1插入排序以后就结束。

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
}

2.希尔排序时间复杂度gap=3时:O(N*log3 N) gap=2时:O(N*logN)

(1)先看内存for循环的复杂度:有两种情况

①预排序gap很大时,数据跳的很快,差不多是O(N),假设gap=n/3(n是数组长度),for循环要走n-gap=2n/3 次,如果数组前面有一个很大的数,他要跳到最后一个,也最多需要3次,就是每次end增加后进去最多也就跳3次,3*(2n/3)=2n,所以时间复杂度是O(N)

②gap很小时,他很接近有序差不多也是O(N),因为gap在很大的时候(gap>1时,预排序的情况)进行预排序以后数组已经接近有序了,当gap每次/3+1到gap=1时,就是插入排序一个接近有序的数组,是插入排序的最好情况(或者其他gap比较小的时候,也是很接近有序),时间复杂度也是O(N)

所以不管gap很大还是很小的时候数据复杂度都是O(N)。
(2)外层

        int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;

+1太小忽略的就行,意思就是:n/3/3/3……=1,3^x=n,x=log3 N        x循环次数=log以3为底N的对数,时间复杂度是:O(log3 N)

总结:内层O(N)*外层O(log3 N)=O(N*log3 N)        

希尔排序时间复杂度就是O(N*log3 N) ,如果你的gap取的是2,那时间复杂度就是O(N*logN),经计算平均下来时间复杂度为:O(N^1.25)

有文献:常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第5张图片

3.希尔排序空间复杂度O(1)

希尔排序就是插入排序前加了个预排序,也没有开额外数组,只是放局部变量,所以空间复杂度是O(1)。

4.希尔排序的稳定性——不稳定

预排序时分组可能把相同的数分到不同的组,不同组再分别插入排序(这就是预排序),就有可能把相同的数前后顺序改变,所以希尔排序不稳定。



四.选择排序

先给出代码:

void PrintArray(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)    //当left和right中间没有值或只有一个值结束循环(只有一个值时说明他的左边都是比他小的值,右边都是比他大的值,并且有序)
	{
		int mini = left;
		int maxi = left;
		for (int i = left + 1; i <= right; i++)    //遍历数组,找最大最小值的下标
		{
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		swap(&a[left], &a[mini]);    //把最小值放到左边left处
		if (maxi == left)       // 如果left和maxi重叠,修正一下maxi即可  
		{
			maxi = mini;       //对maxi的修正请看下面详解!!!
		}
		swap(&a[right], &a[maxi]);    //把最大值放到右边right处
		left++;                //左右下标向中间走,缩小区间
		right--;
	}
}

void TestSelectSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintArray(a,sizeof(a)/sizeof(int));
}
int main()
{
	TestSelectSort();
	return 0;
}

1.选择排序的思路很简单:

(1)遍历一遍整个数组,找出数组最大值和最小值,把最小值放的数组最左边left=0处,最大值放最右边right=n-1处,然后left++,right--,缩小区间,再遍历,再找最大最小值,再分别放到left和right处,直到left

(2)对maxi的修正:上面还有特殊情况不能通过,当最大值就是最左边的值时,上面的swap就会把最大值调包,虽然成功把最小值放到左边left处,但是下面再把最大值放到right处时,最大值已经被调包成最小值了,就错了,所以要进行优化:如果最大值就是最左边的值时,最小值和a[left]交换后,最大值就到了原来最小值的地方,所以使修正maxi,使maxi=mini就是最大值了。

2.选择排序的时间复杂度O(N²)

选择排序原本是每次遍历选一个值,我们这里每次遍历选两个值还是优化过的,相当于执行了n/2次遍历,每次遍历都要走一遍数组,因此时间复杂度O(N²),最好情况和最坏情况都是O(N²)

3.选择排序的空间复杂度O(1)

选择排序没有开额外数组,仅保存局部变量,所以空间复杂度是O(1).

4.选择排序的稳定性——不稳定

就说未优化的选择排序:每次选一个最小的数放到数组最左边,看似没问题,但是你把这个最小数和最左边的数交换时就有可能打乱顺序,举例:3 3 7 1 1 9 8 4 ,找最小值找到第一个1,需要把第一个1和第一个3交换,交换完是: 1 3 7 3 1 9 8 4 虽然两个1的前后顺序没变,但是 两个3的前后顺序改变了,就是当前两个数相同时,找小发生交换就会改变相同数的前后顺序,所以选择排序不稳定。

五.快速排序

1.【1】递归版本

由于快排的递归写法较多我们就把完整的代码放到大标题五.的末尾。

快排递归版本一共多少种写法?:

单排 PartSort 函数 有3种思路分别是hoare法(1种),挖坑法(1种),前后指针法(4种),前后指针法分为key选left(1种)和key选right(3种), 合计6种写法,这6种写法只是单排 PartSort 的写法不同,外层递归函数都是一样的

快排大致的递归思路:

单趟排序:选出一个key,一般是第一个数或者是最后一个数,先排成全部小于key的数和全部大于key的数(不一定是有序的),再把key和全部小于key的数的最后一个数交换,就达到key左边全部是小于自己的数,右边是全部是大于自己的数。这是单趟排,单趟完了就整体有序了,那么左边和右边如何有序呢?分治解决子问题:
通过递归调用单趟函数QuickSort,把左右区间分成两个子区间,再分别找key,把key左放小的数,右放大的数,再分区间再递归,直到区间只剩一个数或没数就结束,这样就能排成有序。

前提:

QuickSort(int* a, int begin,int end) 是外层递归函数,不同的递归方法QuickSort函数都是一样的,PartSort(int* a,int left,int right) 是单趟函数,也正是写法不同的地方,所以我们这里主要探讨的是 PartSort 函数

(1)hoare法(念hao er)

过程讲解:TestQuickSort() 函数中给出数组,并通过调用 QuickSort 快排函数来实现排升序。我们先来看单趟的hoare法  PartSort 函数:给PartSort函数 传入数组地址,数组的左右边界下标left=0;right=n-1.选第一个数做key,用keyi存储key的下标,让right从右往左走找比key小的数,找不到就一直right--,找到就停下,再让left从左往右走找比key大的数,找不到就一直left++,找到就交换a[left]和a[right],相当于 让小的数去左边,大的数去右边,因为key是最左边的第一个数,我们要排升序,最后为了保证key在 全部小于key的数和全部大于key的数 的中间,key就会和全部小于key的数的最后一个数交换,所以必须让right先走,因为right找的是比key小的数,当right和left相遇,相遇的位置左边包括自己都是小于key的数(除了第一位是key),右边都是大于key的数,再把相遇位置的值跟keyi位置的值交换即可。(代码内仍有逐条过程解析)

//1.hoare版本
int PartSort(int* a,int left,int right)
{

	int keyi = left;        //用keyi记录key的下标
	while (left= a[keyi])         //right找小,找不到就right--
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])        //left找大,找不到就left++
		{
			left++;
		}
		swap(&a[left], &a[right]);  //找到后就交换a[left]和a[right],让小的去左边,大数去右边
	}
	swap(&a[left], &a[keyi]);       //最后把key放到小数和大数的中间位置
	return left;
}
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

特殊情况:①让right先走,正常情况是找一个小,就和left交换。如果刚交换完找不到比key小的了,right再走,直接跟left相遇。相遇的位置也是比key小的(因为刚交换完)

②如果刚上来先让right走,一次交换还没发生就找不到比key小的了,那right就直接和left相遇,说明key是1,就不用发生交换了,顺序本来就已经符合了,只不过1左边没数。

③while (left < right && a[right] >= a[keyi]) 中为什么要加 = ?:

当数组中还有和key相同的值时,如果没写 = ,就会死循环。

为了使right和left相遇后能停下,也要加上left < right 这个条件。

(如果右边做key,就需要让left先走,这样能保证相遇位置比key大)

(具体过程请看下面的动态图)常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第6张图片

(2)挖坑法

过程:开始跟上面hoare法一样,都是找个key,left找大,right找小,不同在于先给个坑pit,哪个数是坑就用pit记录下标,让left是pit,让右边right先找小,找到小,把小放到坑处,并使right成为新的pit,再让left找大,找到大后放入pit,再使left成为新的pit,再让right找小,放坑,成为新坑,反复进行,直到right让小的数去左边,大的数去右边,结束while大循环后需要把key放入最后一个坑即可。(代码内仍有逐条过程解析)

注意:这里就不能用keyi记录key下标的形式了,要不然填left坑的时候就找不到原来的key了,所以要直接用key保存数值

//2.挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pit = left;        //用key保存数值
	while (left < right)        
	{
		while (left= key)    //right找小,找不到就right--
		{
			right--;
		}
		a[pit] = a[right];           //找到比key小的值后放入坑pit中
		pit = right;                //right成为新的坑
		while (left= end)
		return;
	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

(具体过程请看下面的动态图)常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第7张图片

(3)前后指针法

①稍微拉胯一点的写法(自己和自己交换的情况没有优化)

key=left,cur找小,++prev,交换prev和cur位置的值

prev跟cur的关系:
1、cur还没遇到比key大的值时,prev紧跟着cur, 一前一后
2、cur遇到比key大的值以后,prev和cur之间间隔着一段比key大的值的区间,只要cur一遇到小,prev++后所在位置就是中间的那段key大的值的第一个,交换prev和cur位置的值,就达到了让小的数去左边,大的数去右边的目的。不断重复操作,直到cur超过数组最后一个值就结束循环,最后把key和小于key值的数们的最后一个数(a[prev])交换,也就成功让key左边都小于key,右边都大于key。

缺陷是:刚开始cur=left+1,prev=left,cur直接找到小于key的数时,prev++后交换prev和cur位置的值,prev和cur指向同一个值,自身和自身交换没用,第③做法会解决这个缺陷

注意细节:这里跟上面的方法有不同之处,while (cur <= right)和while (cur<=right && a[cur]>=a[keyi])   的cur <= right 都是要加等号的,因为上面left

int PartSort333(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		while (cur<=right && a[cur]>=a[keyi])   //cur找小,找不到就往后走
		{
			cur++;
		}
		if (cur <= right)    //cur找到小,++prev,交换prev和cur位置的值
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;
		}
	}
	swap(&a[prev], &a[keyi]);    //最后key和prev交换
	return prev;
}
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

(具体过程请看下面的动态图)常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第8张图片

 ②第二种稍微拉胯一点的写法(自己和自己交换的情况没有优化)

跟上面那种写法唯一不同的就是上面是while找小,找不到就一直走,这里是if判断,如果找到小就prev++并交换,但是同样的缺陷是 当cur直接找到小于key的数后prev追上cur时,prev和cur指向同一个值,自身和自身交换没用

int PartSort33(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort33(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

③第三种最优写法(自己和自己交换的情况得到优化)

在第二种写法的基础上优化,把prev++放进if判断中,如果找到小并且prev在++后的值和cur位置的值不相等,就交换cur和prev位置的值,如果找到小但是prev在++后的值和cur位置的值相等,说明prev和cur指向同一位置,则不进入循环交换,这样就很好解决了自身和自身交换的缺陷!

int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi]&&a[++prev]!=a[cur])
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

1.【2】 快排递归版本复杂度

(1)时间复杂度(未优化是O(N²) 优化最坏情况后是O(N*logN))

最好情况: 每次选key都是中位数O(N*logN)
最坏情况: 每次选的key是最小或者最大的O(N*N),请看下图
常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第9张图片

一个快排的时间复杂度是O(N²),那他为什么叫快排呢?最坏的情况就是每次选的key是最小或者最大的,继续优化逻辑:

针对选key进行优化即可
1、随机选key
2、左,中,右三数取中,选不是最大,也不是最小的那个。即三数取中

(2)空间复杂度O(logN)

如果是递归算法,每次建立的栈帧里面都存局部变量什么的空间复杂度是O(1),然后乘深度就是空间复杂度了,即O(logN)

如果是非递归算法,需要模拟递归的过程,即需要保存子区间的索引,每次都会成对的保存,最多保存的索引也和二叉树的高度有关:2 * logN

所以空间复杂度为logn。

1.【3】快排的稳定性——不稳定

每次选key最后和中间某个值交换,中间某个值左右有可能有和他自己相同的值,发生交换就有可能改变相同值的前后顺序,所以快排不稳定。

1.【4】对快排递归时间复杂度的优化

(1)三数取中:

再退一万步讲:就算第一次三数取中左,中,右分别是最大,最小,次大,第一次三数取中选了个次大,效率不会提升太高,但是分成左右区间再三数取中,不会次次取次大。次次取次大次小 这种概率本身是不大的,为什么不大呢?因为正常的情况下,数据都是随机的,这些数据你有一两次,本来取中间那个数是二分的,然后你反而去取了一个次大的或者次小的,不可能每次都是这样的情况。

int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + (right - left) / 2;        //防止left + right 过大溢出
	// left mid right
	if (a[left] < a[mid])        //分a[left] < a[mid]和a[left] > a[mid]2种情况
	{
		if (a[mid] < a[right])    //即: left mid right    此时mid是中间的数
		{
			return mid;
		}
		else if (a[left] > a[right])    //right left mid     此时left是中间的数
		{
			return left;
		}
		else
		{
			return right;    //只剩right在中间的情况了:left right  mid  此时right是中间的数
		}
	}
	else // a[left] > a[mid]    
	{
		if (a[mid] > a[right])    //right mid left    此时mid是中间的数
		{
			return mid;
		}
		else if (a[left] < a[right])    //mid left right   此时left是中间的数
		{
			return left;
		}
		else              //只剩right在中间的情况了:mid right left   此时right是中间的数
		{
			return right;
		}
	}
}

我个人更喜欢下面这种写法:分mid在最左边和最右边2种情况,更容易理解:

//三数取中
int GetMidIndex(int* a,int left,int right)
{
	int mid = left + (right - left ) / 2;        //防止left+right过大溢出
	if (a[left] < a[right])           
	{
		if (a[mid] < a[left])   //分mid在最左边和最右边2种情况,跟上面一个意思,不过多赘述了
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}
	else
	{
		if (a[mid] < a[right])
			return right;
		else if (a[mid] > a[left])
			return left;
		else
			return mid;
	}
}

 完整应该这么写:

//三数取中
int GetMidIndex(int* a,int left,int right)
{
	int mid = left + (right - left ) / 2;        //防止left+right过大溢出
	if (a[left] < a[right])           
	{
		if (a[mid] < a[left])   //分mid在最左边和最右边2种情况,跟上面一个意思,不过多赘述了
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}
	else
	{
		if (a[mid] < a[right])
			return right;
		else if (a[mid] > a[left])
			return left;
		else
			return mid;
	}
}

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);					//三数取中
	swap(&a[midi], &a[left]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi]&&a[++prev]!= a[cur])
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}

(2)小区间优化

快排递归调用展开简化图就是一颗二叉树,区间很小时,不再使用递归划分的思路让他有序,而是直接使用插入排序对小区间排序,减少递归调用了
 

2.快排的非递归版本

快排递归版本和非递归版本不同之处又在于外层函数 QuickSort 的不同,我们记非递归版本为 QuickSort1,单趟快排函数我们就随便用一个,比如就用hoare法的单趟快排。

大体思路:前面通过递归思路,这里就利用一个栈,拿区间的左右下标,然后单趟快排得到keyi,再分别拿左右区间的左右下标,单趟快排得keyi,再分别拿左右区间的左右下标,反复缩小区间,直到区间小到只有一个数或者是空,就不再往栈中放左右下标了,并且此时已经进行完了所有的单排,所以栈为空就结束即可。详细步骤在下面代码内:

//1.hoare版本
int PartSort(int* a,int left,int right)
{

	int keyi = left;        //用keyi记录key的下标
	while (left= a[keyi])         //right找小,找不到就right--
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])        //left找大,找不到就left++
		{
			left++;
		}
		swap(&a[left], &a[right]);  //找到后就交换a[left]和a[right],让小的去左边,大数去右边
	}
	swap(&a[left], &a[keyi]);       //最后把key放到小数和大数的中间位置
	return left;
}
void QuickSort1(int* a, int begin, int end)
{
	ST st;                        //创建一个栈st
	StackInit(&st);        
	StackPush(&st, begin);        //将数组的左右下标都入进栈
	StackPush(&st, end);
	while (!StackEmpty(&st))      //栈不为空时进行下列操作
	{
		int right = StackTop(&st);    //拿出此区间的右下标,后入end就先出,拿完就pop
		StackPop(&st);                
		int left = StackTop(&st);     //拿出此区间的左下标,先入begin就后出,拿完就pop
		StackPop(&st);

		int keyi = PartSort(a, left, right);    //单趟快排后拿到key的下标
//当左区间不为空时,就入左区间的左右下标,在后面循环中会拿出这里入的左右下标进行单排
		if (left < keyi - 1)      
		{
			StackPush(&st, left);
			StackPush(&st, keyi-1);
		}
//当右区间不为空时,就入右区间的左右下标,在下次循环中会拿出这里入的左右下标进行单排
		if (keyi + 1 < right)
		{
			StackPush(&st, keyi+1);
			StackPush(&st, right);
		}
	}                //当栈为空说明已经没有可以入的左右下标了,说明已经快排结束
}
void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort1(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

3.给出快排所有的代码:(其中主要思路有递归和非递归2种,单排有3种思路,6种写法)

//快排单趟有3种思路:
//1.hoare版本
int PartSort(int* a,int left,int right)
{

	int keyi = left;
	while (left= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[keyi]);
	return left;
}
//2.挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pit = left;
	while (left < right)
	{
		while (left= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left=a[keyi])
		{
			cur++;
		}
		if (cur <= right)
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;
		}
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}
//————————————————————————————————————
//快排递归写法函数
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort36(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}
//快排非递归写法函数
void QuickSort1(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort(a, left, right);
		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi-1);
		}
		if (keyi + 1 < right)
		{
			StackPush(&st, keyi+1);
			StackPush(&st, right);
		}
	}
}
void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{

	TestQuickSort();
	return 0;
}

六.归并排序

先给出归并排序代码:

1.归并递归版本代码:

void PrintArray(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void _MergeSort(int* a,int* tmp,int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;

	_MergeSort(a,tmp, begin, mid);
	_MergeSort(a,tmp, mid+1, end);
    //条件断点,用于调试!!
	//if (begin == 0 && end == 1)
	//{
	//	int x = 0;
	//}
//归并:  
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
	while(begin1 <= end1)
		tmp[index++] = a[begin1++];
	while(begin2 <= end2)
		tmp[index++] = a[begin2++];
	memcpy(a+begin,tmp+begin,sizeof(int)*(end-begin+1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int)malloc(sizeof(int)*n);
	assert(tmp);
	_MergeSort(a,tmp,0,n-1);
}
void TestMergeSort()
{
	int a[] = { 10,6,7,1,3,9,4,2,5,2 };
	PrintArray(a, sizeof(a) / sizeof(int));

	MergeSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{

	TestMergeSort();
	return 0;
}

1.【1】归并递归版本解析

(1)递归思路:

数组:10,6,7,1,3,9,4,2,5,2  ,可以利用后序遍历的思想,把a[begin]~a[end]分为两组a[begin]~a[mid]和a[mid+1]~a[end]进行归并,但归并前提是两组数有序,就继续把a[begin]~a[mid]分成两组进行归并,把a[mid+1]~a[end]分成两组进行归并,一直分,直到一组的区间内有一个数或者没有数就return,即if (begin >= end) 不成立就return。这样就和二叉树中的后序遍历 先左右孩子最后根 的思路很相似了,思路相同,整体写法也相同:

void _MergeSort(int* a,int* tmp,int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;

	_MergeSort(a,tmp, begin, mid);
	_MergeSort(a,tmp, mid+1, end);
    //这里进行归并
}

最后在后面序遍历的位置再写上两个数组归并的思路:

(2)归并思路:

先不看如何把归并和递归链接起来,我们就先看归并的思想和代码:

假设有两个数组 a[begin1]~a[end1]和 a[begin2]~a[end2] ,想把他俩归并:首先在最外层或者外层函数里面malloc一个数组tmp用于存数,再给一个变量index用于记录tmp的下标走向,让先从两个数组的第一个元素开始比较,比较a[begin1]和a[begin2],谁小就把谁放进tmp中,比如a[begin1]小,那就把a[begin1]放进tmp  一个一个比较

    int* tmp = (int)malloc(sizeof(int)*n);
	assert(tmp);

    int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
	while(begin1 <= end1)
		tmp[index++] = a[begin1++];
	while(begin2 <= end2)
		tmp[index++] = a[begin2++];
	memcpy(a+begin,tmp+begin,sizeof(int)*(end-begin+1));

1.【2】归并排序时间复杂度O(N*logN)

        ​​​​常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第10张图片 

1.【3】归并排序空间复杂度O(N)

归并排序过程中malloc了一个tmp数组用于存放数据,局部变量那些可以忽略,空间复杂度就是O(N)。

2.归并非递归版本代码:

void PrintArray(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;
	while (gap < n)
	{   // 间距为gap是一组,两两归并
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap-1;
			int begin2 = i+gap, end2 = i+gap*2-1;
			int index = begin1;
			//end1越界,修正end1——————————————————————————————————修正部分
			if (end1 >= n)
			{
				end1 = n - 1;
			}
            // begin2 越界,第二个区间不存在
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
            // begin2 ok, end2越界,修正end2即可
			if (begin2 < n && end2 >= n)
			{
				end2 = n - 1;
			}//———————————————————————————————————————————————————修正部分

			while (begin1<=end1&& begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while(begin1<=end1)
				tmp[index++] = a[begin1++];
			while (begin2 <= end2)
				tmp[index++] = a[begin2++];
		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;
	}
}
void TestMergeSort()
{
	//int a[] = { 10,6,7,1,3,9,4,2,5,2 };
	//int a[] = { 10, 6, 7, 1, 3, 9,4,2};
	int a[] = { 10, 6, 7, 1, 3, 9,4};
	PrintArray(a, sizeof(a) / sizeof(int));

	MergeSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{

	TestMergeSort();
	return 0;
}

2.【1】归并非递归版本解析

我们可以先给一个间距gap,让每隔间距为1的两组数(每组gap个数)先归并,即让整个数组的数据两两归并,再让gap*=2,让每隔间距为2的两组数归并,即2个2个归并,再4个4个归并,直到gap=n/2,就相当于整个数组的归并。

举例:10 6 7 1 3 9 4 2

常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第11张图片

  此时我们可以写出除了修正部分的所有代码:

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;
	while (gap < n)
	{   // 间距为gap是一组,两两归并
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap-1;
			int begin2 = i+gap, end2 = i+gap*2-1;
			int index = i;
//————————————————————————————————————————————————————————归并过程
			while (begin1<=end1&& begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while(begin1<=end1)
				tmp[index++] = a[begin1++];
			while (begin2 <= end2)
				tmp[index++] = a[begin2++];
		}
		memcpy(a, tmp, sizeof(int) * n);
//————————————————————————————————————————————————————————归并过程
		gap *= 2;
	}
}

写成这样是考虑不全的:我们每次以2的倍数来归并数组,那如果我给奇数个或者给10个时,比如给10个数,当4个4个归并时就会越界

常见排序算法详解:插入,冒泡,希尔,选择,快速排序,归并,计数排序,堆排序(已完结)_第12张图片

 这里越界还要分3种情况:

①end1越界,修正end1,将end1改为区间最后一个下标即可

②begin2越界,第二个区间不存在,将第二个区间设置成一个不可能存在的区间,让接下来的归并过程条件不成立就不会进行归并,让begin2

③begin2不越界,end2越界,修正end2即可,end2改为区间最后一个下标即可

            //end1越界,修正end1
			if (end1 >= n)
			{
				end1 = n - 1;
			}
            // begin2 越界,第二个区间不存在
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
            // begin2 ok, end2越界,修正end2即可
			if (begin2 < n && end2 >= n)
			{
				end2 = n - 1;
			}

七.计数排序

先给出计数排序的完整代码:

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	assert(countA);
	memset(countA,0, sizeof(int) * range);
	for (int i = 0; i < n; ++i)    //计数
	{
		countA[a[i]-min]++;
	}
	int j = 0;
	for (int i = 0; i < range; ++i)     //计数后逐个传给原数组a
	{
		while (countA[i]--)
		{
			a[j++] = i+min;
		}
	}
}


void TestCountSort()
{
	//int a[] = { 10, 6, 7, 1, 6, 1};
	int a[] = { 100, -60, 70, 100, 65, -60 };
	PrintArray(a, sizeof(a) / sizeof(int));
	CountSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestCountSort();
	return 0;
}

1.计数排序思路:

建立映射关系(这里是绝对映射:10000 9999 5000 9999 5000 8888 减去最小值5000成为:5000 4999 0 4999 0 3888 放进a[0]~a[5000]),创建一个范围值range=max-min+1, malloc一个大小是range的数组countA统计每个数绝对映射的出现次数,(注意开始要把数组countA的所有元素初始值用memset给成全0)遍历原数组,一个值的出现几次,他映射的位置countA[a[i]-min]就+ +几次,最后传回原数组a。

2.计数排序时间复杂度:O(range + N)

前面有两个时间复杂度是O( N)的for循环,最后有一个时间复杂度是O( range )的for循环,总时间复杂度是O( 2*N+range ),去掉系数总时间复杂度就是O(range + N)。

3.计数排序空间复杂度:O(range)

额外malloc了一个range大小的countA数组用来计数,则计数排序空间复杂度就是O(range)

4.计数排序稳定性:不用看,没有意义

八.堆排序

堆排详见(202条消息) “堆的增删查改“以及“堆排序“详解_beyond.myself的博客-CSDN博客

还是给出代码:

void AdjustDown_better(HPDataType* a, size_t size, int parent)
{
	size_t child = parent * 2 + 1;				
 
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child]) 
		{
			child++;
		}
		if (a[child] > a[parent])		//大堆
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort1(int a[], int size)
{
	int i = 0;
	for (i = 1; i 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown_better(a, end--, 0);
	}
}
 
void test2()
{
	int a[] = { 15, 18, 28, 34, 65, 19, 49, 25,37,27 };
	int size = sizeof(a) / sizeof(a[0]);
	HeapSort2 (a, size);
	int i = 0;
	for (i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
}
 
int main()
{
	test2();
	return 0;
}

1.堆排序时间复杂度:O(N*logN)

从最后一个叶子的父亲开始向下调整法,从最后一个叶子一直遍历到根节点时间复杂度是O(N),一次向下调整法走高度次复杂度是O(logN),则总的堆排序时间复杂度就是O(N*logN)

2.堆排序空间复杂度:O(1)

未开辟额外空间,仅仅保存局部变量,所以空间复杂度是O(1)。

3.堆排序稳定性:不稳定

最后swap交换堆顶和堆尾数据时,若有相同值就可能改变相同值的前后顺序。所以不稳定。​​​​​

你可能感兴趣的