• 【数据结构】手撕排序算法（中）交换排序 （冒泡排序、快速排序的递归方式（挖坑法、前后指针法、左右指针法））、归并排序的递归方式

    文章目录

    1. 前言

    在上一节中，我们已经掌握了插入排序（包括直接插入排序和希尔排序）和选择排序（直接选择排序和堆排序）；在这一节我们主要讲述选择排序（冒泡排序和快速排序）和归并排序的非递归形式

    2. 交换排序

    2.1 冒泡排序

    • 基本思想：

    所谓交换，就是根据序列中两个纪录键值的比较结果来对交换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

    在这里插入图片描述
    冒泡排序的特性总结：

    1. 冒泡排序是一种非常容易理解的排序
    2. 时间复杂度：O（N^2）
    3. 空间复杂度：O（1）
    4. 稳定性：稳定
    //时间复杂度：O（N^2)
//最好情况 O（N)
//很直接插入排序比较？谁更好？-》直接插入更好
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)//比较n个数的n-1趟
	{
		int exchange = 0;//用来判断数组是否已经有序了
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;//此时说明数组已经有序，无须再排，退出程序
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    2.2 快速排序

    • 基本思想：

    任取待排序元素序列的某个元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中的所有元素均小于基准值，右序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。快速排序大类上有两种方法，一种是非递归的，包括①挖坑法②双指针算法③前后指针法；还有一种是非递归法（下一节我们会讲到）。我们一定要掌握每种方法的思想，因为在面试题里，经常会问你下列选项是快速排序第一趟的结果是哪一个，他的选项可能会包含这四种方法。但是，我们必须要能写出来至少一种。

    快排的特性总结：

    1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
    2. 平均时间复杂度：O（N*logN）（相当于每次正好是二分）
    3. 最坏时间复杂度：O（N^2）（有序数组）
    4. 空间复杂度：O（logN）
    5. 稳定性：不稳定

    在这里插入图片描述

    常用方法一：挖坑法

    整体实现思想：

    在这里插入图片描述

    在这里插入图片描述

    void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;
	int pivot = begin;//坑的位置
	int key = a[begin];
	//单趟排序
	while (begin < end)
	{
		//右边找小，放到左边
		while (begin<end && a[end] >= key)
		{
			--end;
		}
		//小的放到左边的坑里，自己形成新的坑
		a[pivot] = a[end];
		pivot = end;
		//左边找大，放到右边
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//大的放到右边的坑里，自己再形成新的坑
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;
	//[left,right]分成了
	//[left,pivot-1] pivot [pivot+1,right]
	//左子区间和右子区间有序，我们就有序了，->分治递归
	QuickSort(a, left, pivot - 1);
	QuickSort(a, pivot + 1, right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    快速排序虽然快，性能比较好，但它有一个致命的弱点，就是如果一个数组原本就是一个有序的，它排的就非常非常的慢。我们可以用三数取中来解决这个问题，就是从数组的第一个元素、中间的一个元素、最后一个元素取一个不大不小的那个数当做key，可以有效解决这个问题。

    //三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;//中间坐标
	if (a[left] < a[mid])//第一个坐标的值小于中间坐标的值
	{
		if (a[mid] < a[right])//中间坐标的值小于最后一个坐标的值
		{
			return mid;//a[left] < a[mid] 
		}
		else if (a[left] > a[right])
		{
			return left;//a[right] < a[left] 
		}
		else
		{
			return right;
		}
	}
	else//a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;//a[left] > a[mid] > a[right]
		}
		else if (a[left] < a[right])
		{
			return left;//a[right] > a[left] > a[mid]
		}
		else
		{
			return right;
		}
	}
}

//1.挖坑法
int PartSort1(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[left], &a[index]);//把中间的值再放到第一个位置上
	int begin = left;
	int end = right;
	int pivot = begin;//坑的位置
	int key = a[begin];//记录坑的值，否则后面会覆盖，找不到了
	//单趟排序
	while (begin < end)
	{
		//右边找小，放到左边
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		//小的放到左边的坑里，自己形成新的坑
		a[pivot] = a[end];
		pivot = end;
		//左边找大，放到右边
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//大的放到右边的坑里，自己再形成新的坑
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;
	return pivot;//返回坑的下标
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyIndex = PartSort1(a, left, right);
	//[left,right]分成了
	//[left,keyIndex - 1] pivot [keyIndex + 1,right]
	//左子区间和右子区间有序，我们就有序了，->分治递归
	QuickSort(a, left, keyIndex - 1);
	QuickSort(a, keyIndex + 1, right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81

    这里面还有一个小点可以继续优化，就是在函数递归的时候，递归越到后面，调用三数区取中函数的次数会非常的多，我们可以采用小区间优化的思想来解决，但是只能快一点点。

    	//小区间优化
	if (keyIndex - 1 - left > 10)
	//keyIndex - 1 - left表示这个区间有多少个数，
	//数字越少，说明越到递归的后面了，那么递归调用三数取中函数的次数是肯定非常多的
	{
		QuickSort(a, left, keyIndex - 1);
	}
	else
	{
		InsertSort(a + left, keyIndex - 1 - left + 1);//这时候，我们换别的排序
	}
	if (right - (keyIndex + 1) > 10)
	{
		QuickSort(a, keyIndex + 1, right);
	}
	else
	{
		InsertSort(a + keyIndex + 1, right - (keyIndex + 1) + 1);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    在这里插入图片描述
    常用方法二：左右指针法

    前后指针法的思想和挖坑法一样，都是先找一个坑。我们定义两个指针下标begin end分别指向数组的前后，从前（begin）找比key值大的数，从后（end）找比key值小的数，当前后都找到了，就交换这两个数。

    在这里插入图片描述

    //2.前后指针法
int PartSort2(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);//三数取中
	Swap(&a[left], &a[index]);//把中间的数放到数组第一个位置上
	int begin = left;
	int end = right;
	int keyi = begin;//key的下标

	while (begin < end)
	{
		//后面找小
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}
		//前面赵大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}
		Swap(&a[begin], &a[end]);//交换这两个数
	}
	Swap(&a[begin], &a[keyi]);//把三数取中的那个数放到最后的坑里面，记住这时候坑的下标就是begin或者end
	return begin;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    常用方法三：前后指针法

    我们定义两个指针下标，一个是prev指向的是key的下标，一个是cur先指向的是key后一个值的下标。我们利用cur来找比key小的值，每次遇到比key小的值就停下来，prev就++，交换prev和cur位置的值。（前面一般是和自己交换），若果遇到的是比key大的值，prev就不动

    在这里插入图片描述

    //3.前后指针法
int PartSort3(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[left], &a[index]);
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    3. 归并排序

    • 基本思想

    归并排序（Merge-Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

    • 排序步骤——先分解再合并

    在这里插入图片描述

    归并排序特性总结：

    1. 归并排序的缺点在于需要O（N）的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题
    2. 时间复杂度：O（N*logN）
    3. 空间复杂度：O（N）
    4. 稳定性：稳定

    归并的前提是左右子区间必须有序，那么归并前，左右子区间没有序怎么办？-》一直往下分，分成只有一个数的时候，就肯定是有序的了。
    归并就是依次对比，取小的数放到新的临时数组。最后把临时数组拷贝给原来的数组

    void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) >> 1;
	//如果 [left,mid] [mid + 1,right]有序了，那么我们就可以合并了
	_MergeSort(a, left, mid, tmp);//左区间
	_MergeSort(a, mid + 1, right, tmp);//右区间

	//归并操作
	int begin1 = left, end1 = mid;//左子区间
	int begin2 = mid + 1, end2 = right;//右子区间
	int index = left;
	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++];//先赋值，再++
	}

	//临时区间拷贝回去
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    递归调用图：

    在这里插入图片描述

  • 相关阅读:
    逆向工程：Python反编译工具的一点介绍（如何还原pyc文件）
    【部署之后的错误排查】远程不能访问
    手撸MQ消息队列——循环数组
    android--屏幕适配
    vue之小知识罗列
    如何使用ebpf kprobe探测内核函数
    K线形态识别_T字线和倒T字线
    Linux：详细介绍如何挂载？及其命令
    WifiCountryCode&信道
    pycharm专业版使用
  • 原文地址：https://blog.csdn.net/qq_59702185/article/details/126542018