投稿
  1. 首页
  2. 随笔

数据结构 — 排序合集

java资料 • 2022-12-17 • 随笔 • 阅读 32

数据结构 — 排序合集,第1张

数据结构 — 排序合集 数据结构 — 排序合集！

文章目录
  • 数据结构 — 排序合集！
  • 前言
  • 一、插入排序
    • 1.直接插入排序
    • 2.shell排序（希尔排序）
  • 二、选择排序
    • 1.直接选择排序
    • 2.堆排序
  • 三、交换排序
    • 1.冒泡排序
    • 2.快速排序
  • 四、归并排序
    • 1.归并排序
  • 总结

前言

这篇文章主要是博主自己对数据结构中，七种排序算法的笔记以及思想的自我理解，如有更好的写法，欢迎大家指正。

一、插入排序 1.直接插入排序

思想：
把待排序的数据，按我们自己需要的排序方式，逐个插入到已经排好的序的有序序列中，直到所有待插入数据，全部插入位置，生成一个全新的序列。

二话不说先看代码：

void Insert_Sort_1(int* arr, int sz)    // 从前向后比较（有序序列）
{
	for (int i = 1; i < sz; i++)
	{
		int temp = arr[i];              // 需要插入的值
		int right = i;                  // 有序序列的终点
		int Left = 0;                   // 有序序列的起点
		while (Left <= right)           // 为 temp 寻找合适的插入位置
		{
			int mid = (Left + right) / 2;
			if (temp > arr[mid])
				Left = mid + 1;
			else
				right = mid - 1;
		}
		for (int j = i; j > Left; j--)   // 在有序序列中，插入temp
		{
			arr[j] = arr[j - 1];
			arr[Left] = temp;
		}
	}
}
void Insert_Sort_2(int* arr, int sz)   //从后向前比较（有序序列），不需要交换数据
{
	for(int i= 1; i 0 && tmp 

代码讲解：
 刚才，思想介绍中，我们提到了，它是将待插入数据，在已经有序的序列中找到合适的位置，进行插入，那么我们在没有使用额外空间的情况下，如何满足有序序列这个点呢？我们可以选择从头开始，选取 i = 1时的数据作为比较数据，将其保存在我们的临时空间temp中，因为我们没有额外开辟空间，所以我们找到需要插入的位置时，需要将该位置以后的数据向后移动（有序序列中的数据向后移动，这里有个很巧妙的点就是我们每次插入的数据都是有序序列结束后紧跟的数据，所以不用担心覆盖会覆盖错误），空出这个位置才能将我们的 temp 插入，不然就会覆盖原本的数据，我们的 Left 始终是数组的起始位置，因为我们需要在有序序列中找到合适的位置，所以我们必须保证一个数据遍历的起点。那我们的有序序列的终点又是哪里呢?就是我们的 right它始终代表着有序序列的终点，所以我们才会在第一层循环中，让 i 的值从 1 开始，因为有序的序列至少需要两条数据才能称为序列，这样，我们第一次循环结束时，前两个数据就会排序完成。
 

之后，i 每次向后移动，保存到 temp 中，为 temp 寻找合适的插入位置，向后移动数据，将 temp 插入，这就是我们的直接插入排序。
 

寻找合适的插入位置：
 聪明的小伙伴已经看出来了，我们中间还有一个二分查找，这个我不强求大家使用，大家也可以使用自己熟练的查找方法，但是二分查找是效率最高的查找方法，不懂得的大家可以照着代码画图看一下，这样记得更牢固，比我口头叙述给大家效果要好很多。
 

两种思想大致相同，但是第二相对来说更加简单，麻烦的会了，简单的也不需要别人多说了！加油！！
 

直接插入排序的特性总结：
 

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定
 
2.shell排序（希尔排序） 

为啥要用英文？因为可以装逼！！！！
 思想：
 先选定一个整数 gap，把待排序文件中所有数据分个组，所有 距离 相同的记录分在同一组内，并对每一组内的记录进行排序。然后选取不同 gap，重复上述分组和排序的工作。当到达 gap == 1 时，所有记录在统一组内排好序。
 

那么这里的gap如何选取呢？
 我们一般第一次选择数据的长度，也就是 gap = n;
 后续就是，gap = gap / 3 + 1（这个记住就好，文献上也没有准确的说法，这个是最为接近最佳效率的）
 

那么下面上代码：
 

void Shell_Sort(int* arr, int sz)
{
	gap = sz;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0;gap + i < sz; i++)
		{
			if (arr[i] > arr[i + gap])
			{
				int temp = arr[i];
				arr[i] = arr[i + gap];
				arr[i + gap] = temp;
			}
		}
	}
}
int main()
{
	int arr[] = { 2,1,4,3,6,5,3,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
}

 

代码讲解：
 每次按照，gap 为步长，间隔步长的两个数据为一组，按照咱们指定的顺序进行排序，当gap == 1时，数组已经接近有序的了，这个没什么难度，主要是记住 gap 的计算公式。
 

希尔排序的特性总结：
 

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：O(n ^ 1.25) ~ O(1.6 * n ^ 1.25)
  4. 稳定性：不稳定
 
二、选择排序 
1.直接选择排序 

思想：
 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
 

int SelectMin(int* arr, int i, int n)
{
	int min = arr[i + 1];
	int index = i+1;
	for (int j = i + 1; j < n; j++)
	{
		if (arr[j] < min)
		{
			min = arr[j];
			index = j;
		}
	}
	return index;
}
void SelectSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = arr[i];
		int index = SelectMin(arr, i, n);
		if (arr[index] < min)
		{
			int temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}
}

 

代码解析：
 emmm,有一说一，感觉这个没啥好说的，中间封装了一个寻找整个数组中最小值的函数，看起来美观一点，然就是比较，然后交换位置，这样。。。硬要说，就是每次从数组中找到最小值，然后跟下标为 i 的值进行比较，然后下次取最小值，就是从待排数组中寻找最小值，就这样 -.-
 

直接选择排序的特性总结：
 

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定
 
2.堆排序 

思想：
 堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
 需要注意的是：排升序要建大堆，排降序建小堆。
 

（这里要提一下，明天咱们开始更新二叉树的知识，也会讲到堆，会的同学可以继续往下看，不会的同学可以在明天看完二叉树和堆的知识点介绍，再来看这点，这里可以先跳过一下。）
 

直接上代码！！！！！
 

void AdjustDwon(int* a, int n,int start)
{
	int i = start;
	int j = 2 * i + 1;
	while (j < n)
	{
		if (j + 1 < n && a[j] < a[j + 1])
			j++;
		if (a[j] > a[i])
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		i = j;
		j = 2 * i + 1;
	}
}
void HeapSort(int* a, int n)
{
	int tail = (n - 1) / 2;
	while (tail >= 0)
	{
		AdjustDwon(a, n, tail);
		tail--;
	}

	int end = n - 1;
	while(end > 0)            //这里是排序循环，因为我们是建的大堆，所以是升序排序
	{
		int temp = a[0];
		a[0] = a[end];
		a[end] = temp;
		AdjustDwon(a, end, 0);
		end--;
	}
}

 

我觉得这里咱们得图示一下，图看懂了再看一下下面的讲解我觉得应该可以说明白：
 
 

代码讲解：
 这里主要牵扯到一个，建堆的时候，我们有一个 *** 作，叫做向下调整，这个可以说是堆的核心了，知道向下调整是，怎么调整的，我觉得你的堆就没多大问题了，奥，还有向上调整，这个是向堆里插入数据时候用的，这个在讲堆结构的时候会重点讲的，因为堆结构，咱们只能尾插，这时候插入一个数据，原来的堆结构就被破坏了，所以我们需要把新插入的数据，从下面把它向上调整符合堆结构的位置，这就是向上调整的目的。
 

大堆和小堆：
 大堆根节点永远都是所给有效数组中最大的数
 小堆根节点永远都是所给有效数组中最小的数
 

首先我们需要将数组调整为一个堆（大堆或小堆，这个由需求决定），所以为什么，建大堆就是升序排序呢，这里就利用到了堆的一个特性，它的数组的 “ 0 ” 下标位置（根节点）永远都是这一串数据中最大的数，那么我们是怎么利用这个性质的呢，就是我们的第二个 while 循环中，我们设置一个 end 变量，它是控制这里的临时数组有效长度的一个变量，end 永远都是我们的临时数组的最后一个下标，那么我们排序的方法就是，每次循环都将首尾元素进行交换，这时，数组中最大的数就到了末尾，然后我们将 **end–**但是我们在向下调整这里，我们是控制的长度是  

堆排序的特性总结：
 

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定
 
三、交换排序 
1.冒泡排序 

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

直接上代码！！！
 

void BubbleSort(int ar[], int left, int right)
{
	int n = right - left;
	bool is_change = false;                 // 用于标记是否进行了交换
	for(int i=0; i ar[j+1])
			{
				int tmp = ar[j];
				while(jar[j+1])
				{
					ar[j] = ar[j+1];
					j++;
				}
				ar[j] = tmp;
				is_change = true;           //发生了交换置为真
			}
		}
		if(!is_change)                      // 判断是否进行了交换，如果遍历一遍没有发生
			break;
		else
			is_change = false;
	}
}

 

这个冒泡排序跟C语言课本里的有一点细微的差距，多了一个判断，这个判断在某些时候可以让我在某些情况下，提高极大的效率，就比如 {2,1,3,4,5,6,7,8,9},如果是普通版本的冒泡排序，它将前两个交换之后，还是会继续向后遍历n*(n - 1)次，这将会极大浪费效率，但是这里多一个是否进行交换的判断，如果没有进行交换，那么我们判断条件就会成立，然后直接退出循环，这样就不会多余的无意义的遍历浪费效率。
 

冒泡排序的特性总结：
 

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定
 
2.快速排序 

思想：
 任取待排序数据序列中的某数据作为基准值，按照该排序码将待排序数据集合分割成两子序列，左子序列中所有数据均小于基准值，右子序列中所有数据均大于基准值，然后最左右子序列重复该过程，直到所有数据都排列在相应位置上为止。
 

代码：
 

int SelectIndex(int* arr, int left, int right)   //寻找中间值，在左右两边和去中间的值进行比较，取最小的数返回，作为我们分割集合的key值，返回其下标
{
	int key = (left + right - 1) / 2;
	if (arr[key] < arr[left] && arr[left] < arr[right - 1])
		return key;
	if (arr[key] > arr[left] && arr[key] < arr[right - 1])
		return left;
	return right - 1;
}
//hoare
int SelectMid_1(int* arr, int left, int right)
{
	int k = SelectIndex(arr, left, right);
	if (arr[left] != arr[k])
	{
		int temp = arr[k];
		arr[k] = arr[left];
		arr[left] = temp;
	}
	int key = arr[left];
	int low = left;
	int high = right - 1;
	while (low < high)
	{
		while (low < high && arr[high] > key)
			high--;
		Swap(arr[high],arr[low]);
		while (low < high && arr[low] < key)
			low++;
		Swap(arr[low],arr[high]);
	}
	return low;
}
//挖坑
int SelectMid_2(int* arr, int left, int right)
{
	int k = SelectIndex(arr, left, right);
	if (arr[left] != arr[k])        //判断寻找到的值是否跟最左边的值相等，相等就交换一下，因为我们要key值放在最左边，当然最右边也行，看习惯吧
	{
		int temp = arr[k];
		arr[k] = arr[left];
		arr[left] = temp;
	}
	int key = arr[left];             // 将我们选取的key值保存在我们定义的变量 key 中
	int low = left;                  // 从 0 下标开始
	int high = right - 1;            // 从末尾开始
	while (low < high)               // 开始进行分割
	{
		while (low < high && arr[high] > key)    //将大于 key 的值留在右边 
			high--;
		arr[low] = arr[high];                    //因为 high 下标的值 <=key 所以我们将其放在左边
		while (low < high && arr[low] < key)     //将小于 key 的值留在左边   
			low++;
		arr[high] = arr[low];                    //因为 low 下标的值 >=key 所以我们将其放在又边
	}
	arr[low] = key;
	return low;                     //返回的下标将作为，将数据集合分割的界线
}
//前后指针
int SelectMid_3(int* arr, int left,int right)
{
	int k = SelectIndex(arr, left, right);
	if (arr[left] != arr[k])
	{
		int temp = arr[k];
		arr[k] = arr[left];
		arr[left] = temp;
	}
	int key = arr[left];
	int pos = left;
	for (int i = pos + 1; i < right; i++)
	{
		if (arr[i] < key)
		{
			pos++;
			if (pos != i)
			{
				Swap(arr[i],arr[pos]);
			}
		}
	}
	Swap(arr[left],arr[pos]);
	return pos;
}
void QuickSort(int* arr, int left,int right)
{
	if (left >= right)
		return;
	int key = SelectMid_3(arr,left,right);     //调用前后指针法
	QuickSort(arr, left, key);                 //对左右两边数据进行分治，递归调用快速排序
	QuickSort(arr, key+1 ,right); 
}

 

代码解析：
 三种方法大同小异，主要思想都是 分治思想 ，找到一个emmm自己看着顺眼的值（我一把都是中间，左边，右边找一个最小的）然后，将其作为 key 值，放在最左边或者放在末尾（看你的心情！），这里我们主要讲一下前后指针法，懂一个其他都懂了，最主要的点，就是它是如何将数据集合划分成左右两个子集合的过程，以及递归的使用，剩下两个版本，我都有注释，主要核心思想理解了，我觉得其他的凭大家的聪明才智，一定可以理解，毕竟全让我说出来，这样不就失去了学习探索的乐趣，好了，回归正题那么双指针是如何实现的的呢？
 

int key = arr[left];
int pos = left;
for (int i = pos + 1; i < right; i++)
{
	if (arr[i] < key)
	{
		pos++;
		if (pos != i)
		{
			Swap(arr[i],arr[pos]);
		}
	}
}
Swap(arr[left],arr[pos]);

 

这里的 key 就是我们选取的关键值，pos 和 i 就我们意义上的前后指针，也就是两个数组下标，pos 比 i 走的慢，pos只有遇到小于 key 的值才会向前移动，它的作用就是给 i 遍历到小于 key 的数据时，将其交换到 pos 的位置，pos 所指向的数始终是小于key值的最后一个，pos + 1 始终都是比 key 值大的数，直到 i 遍历完整个数据集合，key 在遍历完成后与pos交换位置，即可完成分割，这里还是看图示比较明了。
 


 i < key 所以 pos++；
 
 但是 pos == i 所以不进行交换
 
 
 


 i 遍历结束
 进行pos 和 key 的交换,此时我们就可以发现，3左边的值都小于3 ，3右边的值都大于3，这就完成了分割，之后左右重复这个 *** 作，就可以完成。
 

快速排序的特性总结：
 

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定
 
四、归并排序 
1.归并排序 

思想：
 归并排序是建立在归并 *** 作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 

上代码！！！！
 

void _Merge_Sort(int* arr, int left, int right, int* temp)
{
	if (left >= right)
		return;
	//拆分
	int mid = (left + right) / 2;
	_Merge_Sort(arr, left, mid, temp);
	_Merge_Sort(arr, mid + 1, right, temp);
	//归并
	int tmp = left;
	int left1 = left, right1 = mid;
	int left2 = mid + 1, right2 = right;
	while (left1 <= right1 && left2 <= right2)
	{

		if (arr[left1] < arr[left2])
			temp[tmp++] = arr[left1++];
		else
			temp[tmp++] = arr[left2++];
	}
	while (left1 <= right1)
		temp[tmp++] = arr[left1++];
	while (left2 <= right2)
		temp[tmp++] = arr[left2++];
	memcpy(arr+left, temp+left, sizeof(int) * (right - left + 1));
}
void Merge_Sort(int* arr, int left, int right)
{
	int* temp = (int*)malloc(sizeof(int) * right);
	//排序
	_Merge_Sort(arr, left, right - 1, temp);
	//释放空间
	free(temp);
}

 

代码讲解：
 咱们先看一下图示：
 我们实现归并排序，我们主要的 *** 作就只有两步，分解和合并
 分解：
 应用二分查找的思想，将其化分到只有一个数据元素为止
 合并：
 将分解完成的数组进行排序合并
 

首先我们需要创建一个临时空间来保存我们归并完成的数组，如果在原来的数组空间进行存储，则会造成数据的覆盖，那我们在其内部实现了一个内部的排序算法，将这个申请的临时空间传入，用于数据的保存，随后进行数组的化分，将其分一个数据元素组成的数组，随后进行排序，因为我们有两个数组，所以我们定义了left1，right1，left2，right2，这四个下标来控制我们对数组的访问，第一次合并，left1和right1都是10的下标，left2和right2是6的下标，随后进行我们的排序，第一while循环，可以很明显的看出来是将两个数组第一个元素较小的存入临时空间temp,随后访问临时空间的下标和对应数组的的下标都 +1，去访问下一个空间和元素，然后因为存储完第一个元素 +1 之后 left2 > right2 循环结束，这时候，剩下的两个while循环就显示出来了他们的作用，他们是用来检测是否有数组数据没有完全访问，像上面所说，另外一个数组还有一个元素没有放入临时空间，所以我们需要把它也放入，但是也有可能两个数组的元素个数不同，循环结束了另外一个数组中还有数据，我们就把这些剩下的挨个放入temp中，递归到最后就是到第一次拆分的两个数组进行两个数组之间的元素比较，将较小的挨个放入临时空间，应为我们需要的是将原来的数组arr进行排序，所以我们最后将临时空间中的数据拷贝到arr中，完成归并排序。
 

归并排序的特性总结：
 

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

排序是我们需要掌握的基础的数据结构，也是经常会用到的数据结构，需要记住其各自的时间复杂度，空间复杂度，将其熟记于心，在相应的场合应用适当的排序算法，将会大大提高我们的代码质量和水平，加油！！！
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5696452.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
java资料 java资料 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存