两万字搞定《数据结构》 八大排序 必读(建议收藏)

x33g5p2x  于9个月前 转载在 其他  
字(11.7k)|赞(0)|评价(0)|浏览(81)

前言:本章将介绍常见八大排序包括如下直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快排、归并排序以及计数排序(基数排序和桶排序面试基本不涉及,本文忽略了,有兴趣的读者可以自行补充),本章内容是重点中的重点!!!铁子们务必全部掌握!!!

1.插入排序

1.1直接插入排序

基本思想
把一个数插入到有序区间,保持这个区间有序,当前第n+1个数插入到前面,前面的arr[0]到arr[n-1]已经排好序,此时用arr[n]与前面的arr[n-1], arr[n-2]…的值。进行比较找到合适的位置将arr[n]进行插入,原来位置上的元素顺序后移实现了插入

代码实现

//插入排序
void InsertSort(int* a, int n){
    //控制起始条件
    //注意控制好终止条件,这里的end的位置是在倒数第二个位置,所以要-1
    for(int i=0; i<n-1;i++){ 
        //单趟插入
        int end = i;
        int temp = a[end + 1]; //有序区间的后面
        while(end>=0){ //end到-1就终止了
            if(a[end]>temp){
                a[end+1] = a[end];
                --end;
            }else{
                break;
            }
        }
        //两种情况:第一种在最右边,第二种在最左边,end为-1了,始终放在end后面
        a[end+1] = temp;    
    }
}

时间复杂度

插入排序的时间复杂度也是O(N^2),在接近有序的情况下他的时间复杂度是O(N),因为遍历一遍就可以出结果了,空间复杂度O(1)。

1.2希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。

基本思想
希尔排序就是在处理一些极端情况比较高效,比如在上面的插入排序时如果我们在原数组降序的情况下去排升序,那么我们交换的次数是十分多的,也可以说是插入排序的最坏的情况,这个时候聪明的先辈想到了希尔排序,将数组分成了gap组,然后可以理解为分别处理每一个小组,gap从5 – 2 – 1的过程在降序的情况下,排在后面的数值小的数能步子更大排到前面,当gap为1的时候实际上就是进行了一次插入排序。设置gap的过程我们也称之为预排序。

gap越小,越接近有序,gap越大,越不接近有序;
但是gap越小挪动越慢,gap越大挪动越快;

代码实现

void ShellSort1(int* a, int n)
{
    int gap = n;

    while (gap>1)//别傻乎乎的加等号啊,死循环
    {
        gap = gap / 3 + 1;end的范围是[0,n-gap)
        
        for (int i = 0; i < n - gap; i++)//并排走
        {
            int end = i;
            int temp = a[end + gap];
            while (end>=0)
            {
                //当前的end的值比tmp大就要往end+gap位置挪
				//所以要提前保存end+gap的值
                if (temp < a[end])
                {
                    a[end + gap] = a[end];
                    end = end-gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = temp;
        }
    }
}

时间复杂度

O(N^1.3),一般gap建议以gap/3+1的步骤走。

2.选择排序

简单选择排序思路如下动图所示,就是只针对头部的一个数进行对比,代码实现大家可以自己敲敲!

2.1 选择排序(二元改进版)

基本思想
优化的选择排序,每次可以选择一个最大的和一个最小的,然后把他们放在合适的位置,即最小的放在第一个位置,最大的放在最后一个位置。
然后再去选择次小的和次大的,依次这样进行,直到区间只剩一个值或没有。

代码实现

void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int min = begin, max = begin;
		for (int i = begin; i <= end; i++)//注意起点是begin
		{
			if (a[i] >= a[max])
				max = i;
 
 
			if (a[i] < a[min])
				min = i;
		}
		//最小的放在
		Swap(&a[begin], &a[min]);
		//如果最大的位置在begin位置
		//说明min是和最大的交换位置
		//这个时候max的位置就发生了变换
		//max变到了min的位置
		//所以要更新max的位置
		if (begin == max)
			max = min;
 
		Swap(&a[end], &a[max]);
		++begin;
		--end;
	}
}

时间复杂度

O(N^2),最坏的排序

2.2 堆排序

堆排之前文章详细介绍过,具体细节欢迎点击查阅

基本思想
细节去查阅之前的文章,现在就强调一点:排升序要建大堆,排降序建小堆

这里以升序为例:先建堆,排升序建大堆,选出最大的数将其放到最后面,然后满足大小堆后即可做向下调整动作。

代码实现

//堆排序
void AdjustDown(int* a, int n, int parent){
    int child = parent*2 + 1;
    while(child < n){
        if(child+1<n && a[child+1] > a[child]){
            ++child;
        }
        if(a[child]>a[parent]){
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent*2+1;
        }else{
            break;
        }
    }
    
}
void HeapSort(int* a, int n){
    //排升序建大堆 O(N)
    for(int i=(n-1-1)/2; i>=0; i--){
        AdjustDown(a, n, i);
    }
    
    //O(N*logN)
    int end = n - 1;
    while(end > 0){
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0); //是不是妙不可言hhh!
        end--;
    }
}

记录下写堆排时犯的错误(读者可以跳过,这是留给作者复习自用的):

边界问题,画图画图,冷静分析!!!

时间复杂度

时间复杂度是O(N/*logN),空间复杂度O(1)

3.交换排序

3.1 冒泡排序

基本思想
以升序为例,每一趟的冒泡排序都是把一个最大的数放到最后面,如果 a[i-1]>a[i],我们将i-1,i的值进行交换,依次循环反复。

代码实现

void BubbleSort(int* a, int n){
    
    for(int j=0; j<n; j++){
        int flag = 0;
        for(int i=1; i<n-j; ++i){
            if(a[i] < a[i-1] ){
                Swap(&a[i], &a[i-1]);
                flag = 1;
            }
        }
        if(flag == 0){
            break;
        }
    }
}

时间复杂度

O(N^2)

3.2 快速排序

3.2.1 Hoare

基本思想

选一个关键key,一般都是选择头。
单趟:key放在他正确的位置上,key的左边值比key小,key右边值比key大(这是key一趟下来排完后最终要放的位置)
单趟拍完,再想办法让左边区间有序,key的右边区间有序

那么还有优化解决方案:
第一种是取随机值做下标
第二种是获取这三个数中不是最大,也不是最小的那个值的下标,这种情况下不会有最坏情况,因为有三数组取中

代码实现

三数取中(为了优化)

//三数取中
int MidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//不妨思考一下我们进行“三数取中”的意义是什么?

单趟排序:

//一个单趟进行的排序操作的时间复杂度是多少?思考下一次完整的快排需要进行多少趟这样的单趟排序?

int PartSort1(int* a, int left, int right)
{
	int midi = MidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	//最左边的做key为例
	int key = left;
	while (left<right)
	{
		//因为我们是最左边的取key,所以必须是右边先走找比key小的,思考下为什么?
		//右边先走
		while (left < right && a[right] >= a[key])
		{
			--right;
		}
		//然后左边走
		while (left < right && a[left] < a[key])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);//此时left已经和right相遇,一样的
	return left;
}

全趟排序(递归):

void QuickSort(int* a, int left, int right)
{
	//当区间分割到只剩一个或者没有的时候就返回
	if (left >= right)
		return;
	//确定一个位置,划分区间递归
	//分为[left,key-1]   key   [key+1,right]
	//int key = PartSort1(a, left, right);
	int key = PartSort2(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

第一个问题:不妨思考一下我们进行“三数取中”的意义是什么?

如果我们不进行“三数取中”,快排如果遇见最坏的情况——有序,时间复杂度将会变成O(N^2),如果加了“三数取中”,这一最坏情况将会不复存在(后边俩种单趟排序同理)。当然了,实际面试过程当中时间不够没必要再来写一个“三数取中”,面试争分夺秒啦!

第二个问题:一个单趟进行的排序操作的时间复杂度是多少?思考下一次完整的快排需要进行多少趟这样的单趟排序?

一个单趟的时间复杂度是O(N),一个完整的快排需要O(logN)趟这样的单趟排序。

第三个问题:为什么key选择最左边的值,就要先让右边的数先走先去找小?

为了确保最后相遇时的a[left]<a[key],只要让右边的数先走,最后停下来时无论是“左边遇到右边”还是“右边遇到左边”,都满足a[left]<a[key]。

时间复杂度

一整个快排:O(N/*logN)

3.2.2 前后指针法

基本思想
1.cur往前走,找到比key小的数据

2.找到比key小的数据以后,停下来,++prev

3.交换prev和cur指向位置的值

直到cur到达最右边的位置结束!

cur还没遇到比key大的数据之前,prev紧跟着cur,cur遇到比key大的值以后,prev和cur之间间隔着一段比key大的数据。

代码实现

int PartSort2(int* a, int left, int right)
{
	int midi = MidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	//这里key选取最左边的元素为例
	int key = left;
	int prev = left, cur = prev + 1;

	while (cur<=right)
	{
		if (a[cur] < a[key] && ++prev != cur)//防止自己与自己交换
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
    //cur走到末尾啦,交换一下。
	Swap(&a[prev], &a[key]);//这里可以保证交换之前a[prev]一定小于a[key],思考下为啥?
	return prev;
}

答案:跳出while循环的a[prev],在跳出循环之前刚与a[cur]交换过,而a[prev]与a[cur]交换的条件就是a[cur]小于a[key],所以可以保证交换跳出while循环后发生最后一次交换之前a[prev]一定小于a[key]。

全趟排序(递归):

void QuickSort(int* a, int left, int right)
{
	//当区间分割到只剩一个或者没有的时候就返回
	if (left >= right)
		return;
	//确定一个位置,划分区间递归
	//分为[left,key-1]   key   [key+1,right]
	//int key = PartSort1(a, left, right);
	int key = PartSort2(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

时间复杂度

一整个快排:O(N/*logN)

3.2.3 挖坑法

基本思想
挖坑法可以选择在0索引处挖坑(即把数拿走保存),然后从右边找一个小的填坑,再从左边找一个大的埋住右边的坑,以此反复循环,直到left与right相遇,最后把key放入相遇点(最后一个坑位)即可。

代码实现

int PartSort3(int* a, int left, int right)
{
	int midi = MidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	//这里key取最左边的数,让右边的先开始走找小
	int hole = left;
	int key = a[left];

	while (left < right)
	{
		//先找右边比key小的,填到左边的坑里面去
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;

		//再找左边比key大的,找到就交换坑位
		while (left<right&&a[left]<key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[left] = key;//最后把key放到相遇点
	return left;
}

全趟排序(递归):

void QuickSort(int* a, int left, int right)
{
	//当区间分割到只剩一个或者没有的时候就返回
	if (left >= right)
		return;
	//确定一个位置,划分区间递归
	//分为[left,key-1]   key   [key+1,right]
	//int key = PartSort1(a, left, right);
	int key = PartSort3(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

时间复杂度

一整个快排:O(N/*logN)

3.3 快速排序(非递归)

我们前面实现快排是采用递归的方式,但是递归本身是有“原罪”的,这个“原罪”在于如下:
1.当递归深度过大的时候,递归程序本身可能没用错误,但是编译之后会报错——栈溢出(stack overflow)。

2.性能问题(某些书上提到的,但是现在编译优化得很好,这个问题不大)。

任何一个递归程序,我们要把他改成非递归程序有如下俩种方式:

1.循环(但是有的东西是不好改成循环的,比如二叉树的遍历、快排等)

2.“栈”模拟(这个“栈”是数据结构中的“栈”,不是系统内部那个“栈”,一般用到栈难度都是略大的)

这里的快排改非递归用的就是“栈”模拟。

基本思想

非递归的在这里借助栈,依次把我们需要单趟排的区间入栈,依次取栈里面的区间出来单趟排,再把需要处理的子区间入栈,以此循环,直到栈为空的时候即处理完毕。

非递归代码实现

void QuickSortNonR(int* a, int left, int right)
{
	//非递归,我们可以处理当前的区间,再处理分区间
	//先入右,后入左,就先拿到左
	Stack s;
	StackInit(&s);
	StackPush(&s,right);
	StackPush(&s,left);
	while (!StackEmpty(&s))
	{
		left = StackTop(&s);
		StackPop(&s);
		right = StackTop(&s);
		StackPop(&s);
		//处理当前区间 [left,right]
		int key = PartSort3(a, left, right);

		//划分左右区间,分别入栈
		//[left,key-1] key [key+1,right]
		//先入右区间,区间有两个值才需要处理
		if (key + 1 < right)
		{
			StackPush(&s, right);
			StackPush(&s, key + 1);
		}
		//再入左区间
		if (left < key - 1)
		{
			StackPush(&s, key - 1);
			StackPush(&s, left);
		}
	}	
}

时间复杂度

最优的时间复杂度是O(nlogn),最差的空间O(n^2) ,因为进行了三数取中,不存在最差情况。

4.归并排序

4.1 递归实现归并排序

基本思想
我们可以把一个数组分成两半,对于每一个数组当他们是有序的就可以进行一次合并操作。对于他们的两个区间进行递归,一直递归下去划分区间,当区间只有一个值的时候我们就可以进行合并返回上一层,让上一层合并再返回。

代码实现

void _MergeSort(int* a, int left, int right,int* newArr)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	//[left,mid][mid+1,right]
	_MergeSort(a, left, mid,newArr);
	_MergeSort(a, mid + 1, right,newArr);
	//走到这里已经是左右区间有序
	//将两个区间合并成一个区间
	//拷贝到newArr当中,排完再放回
	int index = left;
	int begin1 = left, end1 = mid;
	int begin2 = mid+1,end2 = right;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			newArr[index++] = a[begin1++];
		}
		else
		{
			newArr[index++] = a[begin2++];
		}
	}
	//走到这里一定有一边没有走完
	while (begin1 <= end1)
	{
		newArr[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		newArr[index++] = a[begin2++];
	}
	//拷贝回元素组 letf -- right 的位置
	for (int i = left; i <= right; ++i)
	{
		a[i] = newArr[i];
	}
}
void MergeSort(int* a, int n)
{
//归并排序就是在左右区间有序重新组合起来
//所以保证左右区间都是有序,遍历到叶子就可以
	int* newArr = (int*)malloc(sizeof(int) * n);
	int left = 0;
	int right = n - 1;
	_MergeSort(a, left, right,newArr);
}

时间复杂度

O(NlogN),可以看出他的递归过程中每次都将一组平均分,分完后高度大概是logN,空间复杂度O(N)

4.2 迭代实现归并排序

跟快排类似,递归会带给快排的问题同样会给归并排序带来,所以尝试用非递归方式!

任何一个递归程序,我们要把他改成非递归程序有如下俩种方式:
1.循环(但是有的东西是不好改成循环的,比如二叉树的遍历、快排等)

2.“栈”模拟(这个“栈”是数据结构中的“栈”,不是系统内部那个“栈”,一般用到栈难度都是略大的)

这里归并排序非递归实现就是采用“循环”。

基本思想

迭代实现可以用循环来实现,这里我们根据递归思想其实很容易知道,我们控制迭代从最小的子问题出发,保存最小子问题的值,然后提供给后面用,这其实就是一个动态规划的思想,我们可以从利用子问题的解,解决 “大BOSS”

代码实现

void MergeSortNonR(int* a, int n)
{
	//int a[] = { 8,4,5,7,1,3,6,2,7,8 };
	
	int* newArr=(int*)malloc(sizeof(int)*n) ;
	int groupNum = 1;
	int left;
	int right;
	//动态规划的思想,当我们把最小的问题切割
	while(groupNum<n/2+1)
	{
		for (int i = 0; i < n; i += (2*groupNum))
		{
		//分成两组[begin1,end1][begin2,end2]
		int begin1 = i;
		int end1 = i + groupNum - 1;
		int begin2 = i + groupNum;
		int end2 = i + 2 * groupNum - 1;
		//处理两种情况,当end1已经越界,说明处理end1的边界
		if (end1 >= n)
		{
			end1 = n - 1;
		}
		//当end1越界,理所当然的begin2和end2都越界了
		//这里可能的[begin1,end1]区间,也需要拷贝到临时数组,再拷回原数组
		if (begin2 >= n)
		{
			//表示右区间不存在
			begin2 = n;
			end2 = n-1;
		}
		else if (begin2 < n && end2 >= n)
		{
			end2 = n - 1;
		}

		left = begin1;
		right = end2;
		//index用于放到临时数组newArr当中的
		int index = begin1;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					newArr[index++] = a[begin1++];
				}
				else
				{
					newArr[index++] = a[begin2++];
				}
			}
			//走到这里一定有一边没有走完
			while (begin1 <= end1)
			{
				newArr[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				newArr[index++] = a[begin2++];
			}
			//拷贝回元素组 letf -- right 的位置
			for (int x = left; x <= right; ++x)
			{
				a[x] = newArr[x];
			}
		}
		groupNum*=2;
	}
	free(newArr);
	newArr = NULL;
}

时间复杂度

O(NlogN)

5.计数排序

基本思想
1.统计原数组中每个值出现的次数

2.排序:遍历Count数组,对应位置的值出现多少次就往原数组写几个这个值

当然,在对于数据比较大的时候我们可以通过相对映射,让(该值-min)后的数组加一,最后还原回去即可。

代码实现

void CountSort(int* a, int n)
{
	//int a[] = { 31,24,25,16,1,0,79 };

	//遍历一遍找到最大和最小,然后开大一的数组
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int size = max - min + 1;
	int* tmp = (int*)calloc(size,sizeof(int));
	//将a遍历映射到tmp当中,a的长度是n,tmp的长度只有size
	for (int i = 0; i < n; ++i)
	{
		tmp[a[i] - min]++;//tmp[i]存放的是这个值出现的次数
	}
	//在按照tmp当中的存放放回去
	int index = 0;
	for (int i = 0; i < size; ++i)
	{
		while (tmp[i] > 0)
		{
			//这里应该是下标+映射的
			a[index++] = i + min;
			--tmp[i];
		}
	}
}

时间复杂度

计数排序的时间复杂度是O(N),空间复杂度是O(max-min),就是我们开的数组是这个区间的范围差。

6.八大排序对比

6.1八大排序的性能测试评估

// 测试排序的性能对比
void TestOP()
{
srand(time(0));
const int N = 10000;
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();
    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();
 QuickSort(a4, 0, N-1);
 int end5 = clock();
    
 int begin6 = clock();
 MergeSort(a6, N);
 int end6 = clock();
 printf("InsertSort:%d\n", end1 - begin1);
 printf("ShellSort:%d\n", end2 - begin2);
 printf("SelectSort:%d\n", end3 - begin3);
 printf("HeapSort:%d\n", end4 - begin4);
 printf("QuickSort:%d\n", end5 - begin5);
 printf("MergeSort:%d\n", end6 - begin6);
 free(a1);
 free(a2);
 free(a3);
 free(a4);
 free(a5);
 free(a6);
 free(a7);
 }

结果如下:

6.2 各个排序的稳定性如何判断?

直接看排完序后是否能保证相同的值的相对位置不会发生变化,若能保证,就是稳定,反之即不稳定。

不要死记,一定要理解分析!

冒泡排序:俩俩对比,前一个大于后一个才发生交换(升序),不会出现相等值互换顺序的情况,能保证不改变相同值的相对顺序,稳定。

简单选择排序:在进行俩数交换位置的过程当中,可能数组当中有一个数跟发生交换的俩数数值是一样的,这样就改变的相同数之间的相对顺序,不稳定。

直接插入排序:从前到后一个个元素拿出来跟前面的对比,若插入的数值比被对比的数值小,被对比的数值往后挪动;若插入的数值比被对比的数值大,直接插入到被对比数值的后面,并没有改变俩个相同值得相对顺序,稳定。

希尔排序:在预排序时,相同的数据可能在不同的组里面,没办法控制,所以不稳定。

堆排序:比如俩个一样大的数值,一个在“树顶”,一个在“树中”,树顶元素跟最后一个元素发生交换立马影响相同数值的相对顺序,不稳定。

归并排序:能保证相同值得相对顺序不变,稳定。

快速排序:比如数组中存在跟key数值一样的值,而key是肯定会移动的,这样相对顺序就改变了,所以不稳定。

计数排序:计数是在统计每个数出现的次数,但是相同的数哪个在前哪个在后,并没有区分,所以不稳定。

补充:稳定性有什么意义?

比如我们做了一个考试系统,考生当中先交卷的,成绩在数组的前面,后交卷的,成绩在数组后面。当我们对前几名进行排名的时候,就可能会遇见俩个分值相同的考生,这时候为了公平性考试用时较短者应当在前面。

6.3八大排序时间/空间复杂度一览

相关文章