• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

互联网 diligentman 3小时前 2次浏览

文章目录

  • 排序的基本概念
  • 二 常见的基本排序
    • 1. 插入排序
    • 2. 希尔排序
    • 3. 选择排序
    • 4.堆排序
      • 1)维护堆的性质
        • 递归维护堆的性质
        • 非递归维护堆的性质
      • 2)建立堆
      • 3)堆排序
    • 5 归并排序
    • 6 快速排序
    • 7 计数排序
    • 8 冒泡排序

一 排序的基本概念

排序啊,一个很有趣的话题,排序就是使得数据能够成为一种有序的操作。(并不严谨,可是这样理解就够了。)准确的定义,朋友们可以看看数据结构的书哈,我就不复制粘贴了哈。

  1. 为什么要有排序这个概念呢,它有啥用呢?

答:其实排序的主要目的就是为了提高查找效率,就比如说,二分查找算法,前提必须有有序的数据才可以使用,极大提高了查找效率。,在我的理解,我的理解上啊,其实从广义上讲:把数据结构分为四大块,线性表,非线性表,排序,查找。前面的三大板块都是为了查找做准备的,都是为了提高查找效率,怎么说呢?假如你在某个浏览器,输入你想要查找的东西,可是它半天都没显示出来,这就说明这个浏览器很菜,为什么菜,很大原因就是底层的代码,如数据结构是按,线性的,非线性的,使用的排序算法安排的不合理导致的呗。所以有必要学习以下排序,并且它非常有用哦。

  1. 排序的稳定与否判断

稳定:如果a没排序之前在b前面,且a = b,在排序之后a仍然在b的前面;
不稳定:如果a排序之前在b前面,且a=b,在排序之后a有可能会出现在b的后面;

  1. 内外排序是啥?

内排序:所有排序操作都在内存中完成;适合小数据的排序
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

二 常见的基本排序

1. 插入排序

思想:插入排序,就是给你一组无序的数据,然后把数据分为 有序序列和无序序列 ,然后通过无序序列的数据和有序序列的数据进行比较,从而达到排序的目的。
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】
代码:

void InsertSort (int *a,int length)
{
	for (int i = 1; i< length;i++) // 控制比较次数
	{	
		if(a[i] < a[i-1]) //升序排序
		{
			swap(a[i],a[i-1]); //交换两个数
			//交换完两个数还不够,还要保证有序序列中也是有序的。
			for (j = i-1;j > 0 && a[j] < a[j-1];j--)
			{	
				swap(a[j],a[j-1]);
			}
		}
	}
}
//交换函数
void swap(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

另一种写法:

void InsertSort(int* a,int length)
{
	for (int i = 1;i < length;i++) //控制比较次数
	{
		key = a[i];  //保存要插入的值,为了下面执行a[j+1]  = a[j]时候,a[i]的值还在
		for (j = i-1;j >= 0 && key < a[j];j--) //开始比较插入
			a[j+1] = a[j];
			//退出循环后
		a[j+1] = key; //在执行a[j+1] = a[j]时候,
		//a[i]也就是a[j+1]就被a[j]覆盖了,所以这句话的是把a[i]还会原来的位置 
	}
}

文字解释:
假如有个 序列是 5 3;首先保存 3,3 和 5 比较,3比 5 小,把 5赋值给 3 的位置,最后,保存的 3 再赋值给 5 的位置;

算法在比较的过程就顺便把数移动了。合适,数据量比较少时候使用。


2. 希尔排序

思想:
希尔排序又叫增量缩小排序,就是把一组数据按一定的增量来分成多个小组来插入排序,直到增量缩小到1,则排序结束;

# include<stdio.h>
# include<windows.h>
void print(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);

	}
	printf("n");
}
void ShellSort(int* a, int length)
{
	int j = 0;
	for (int grap = length / 2; grap > 0; grap /= 2) //控制增量
	{	//每一趟增量的插入排序
		//每一趟都是排了一小组的一部分;
		for (int i = grap; i < length; i++)
		{
			int key = a[i];//保存要插入的值
			
			for ( j = i - grap; j >= 0 && key < a[j]; j -= grap)
				a[j + grap] = a[j]; // 若后面的数 小于 前面, 把 前面的给后面的
			//退出循环后,把前面的数插入要插入的值。
			a[j + grap] = key;
		}
		
	}
}

int main()
{
	int a[] = { 10, 8, 4, 6, 9, 11, 123, 6, 2, 14, 3, 8, 5 };
	int n = sizeof(a) / sizeof(a[0]);
	print(a, n);

	ShellSort(a, n);
	print(a, n);

	system("pause");
	return 0;
}



对于 这个循环的解释 for (int i = grap;i > length;i++)
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】
在我的理解:希尔排序也是插入排序的一种小变形方式;在插入排序中,增量就是为1的希尔排序;


3. 选择排序

思想: 选择排序就是,给定一组无序数据,让第一个数据作为最小(最大)的,然后剩下的数据与其比较,找到新的最小(最大)的数,把新的替换旧的数,依次循环认为第二个数据最小…直到排完。
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】
在这里插入图片描述

数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

void SelectSort(int* a, int length)
{
	for (int i = 0;i < length;i++) 
	{
		int min = i; //先假设第一个为最小的
		for(int j = i+1;j < length;j++) //第一个后面开始找新的最小的
		{
			if(a[j] < a[min])
				min = j;
		}
		swap(a[min],a[i]);
	}
}
//交换函数
void swap(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

4.堆排序

思想:堆排序,也是叫做优先队列,使用一种“完全二叉树”的模式去存储数据,然而完全二叉树又可以用数组的形式的方式存储。而且,每一个父结点的值大于(小于)左右孩子的节点值,叫做大堆(小堆)。

完全二叉树的性质

  1. 结点 下标 i 父结点的下标:i/2 -1;
  2. 结点下标 i 的左孩子的下标:i *2 +1;
  3. 结点下标 i 的有孩子的下标:i *2 +2;

推荐视频:堆排序(heapsort) 或者这个 排序算法:堆排序【图解+代码】,两个都讲得很清楚;

数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

1)维护堆的性质

递归维护堆的性质

维护堆的性质是把不满足堆的排序方式的结点,维护成为堆的排序方式的结点。

// a为堆的数组,n为数组大小,i为要维护堆的下标。
//维护大堆的例子
void Heapify (int* a, int n,int i) 
{
	if (i >=n) //递归的结束条件
		return;
	// 先把维护的下标默认认为是最大值的下标
	int maxIndex = i;
	int left = 2*i+1;
	int right = 2*i+2;
	//开始找真实最大值的下标
	if (left < n && a[left] > a[maxIndex]) //左大于父的话,就换新的maxIndex
		  maxIndex = left;
	if (right < n && a[right] > a[maxIndex]) 
	//右大于父(在左大于父不成立下)或者右大于左,
	//在(左大于父的前提下),把新的maxIndex找出来
		maxIndex= right ;
	if (maxIndex != i) //说明左右结点其中一个大于父结点
	{
		swap(a[maxIndex],a[i]);
		Heapify(a,n,maxIndex);
	}
		
}

这段代码的意思就是,假如要从某个已知不成堆的结点 i 开始 heapify; 假如我要从任意结点开始呢?那可以从最后一个结点的父结点开始逐渐递减就可以 heapify 全部的节点了。这就是建立堆的过程。

这图就是从最后一个结点的父节点开始堆化:
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

非递归维护堆的性质

void heapify(int *a,int n,int parent)
{
	int left = 2*parent + 1;
	while (left < n)
	{	//先找出根左右最大值的下标
		if (left + 1 < n && a[left+1] > a[left]) //交换前看看右结点的值是否大于根节点;
			left++;
		if (a[left] > a[parent]) //右结点的值不大于根节点;左结点和根结点交换
		{						//右结点得值大于根节点,
			swap(a[left],a[parent]);
			//继续对下面的结点堆化
			parent = left;
			left = 2*parent + 1;
		}
		else //假如没有 左右结点比parent大的话就结束堆化;
			break;
	}
}

2)建立堆

建立堆:就是维护堆的性质,把任意结点 i 的位置定为 最后一个结点;对最后一个结点的父节点进行维护堆;

void BulidHeap(int *a,int n)
{
	int lastNode = n - 1; //先找出最后一个结点
	for (int i = lastNode/2 -1; i >= 0;i--) // 从最后一个结点的父节点开始向上堆化构建,
										//到根节点时候结束堆化
	{
		heapify(a,n,i);
	}
}

3)堆排序

建立起的对我们结构我们还没开始排序呢。现在开始排序。
因为刚刚建立了大堆,所以我们可以知道根结点一定是堆树中最大的值,我们而要做就是

  1. 把根节点和最后一个结点做一次交换,然后取出交换后的最后一个结点,这样就可以把最大的值取出来了,取出来的目的也是为了排序,然后由于交换了就会破坏堆的结构。
  2. 然后对交换后的根结点再进行一次堆化就可以了。继续完成上诉操作,依次把堆树中最大的值取出来,这样就可以排序啦。

数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

void HeapSort(int* a,int n)
{
	int  lastNode= n -1;
	for (int i = lastNode; i >= 0; i--) //从最后一个结点开始和根交换
	{
		swap(a[0],a[i]);
		//交换后,根又不满足堆的性质了,所以重新堆化
		heapify(a,i,0); //对根堆化,根的下标为 0;数组大小每次会减一
	}
}

5 归并排序

思想:归并排序就是将一个无序得序列,先分开,直到分到只有一个元素,然后再合并排序
推荐一个视频:排序算法:归并排序【图解+代码】,这个视频讲得很清楚。

# include<stdio.h>
# include<stdlib.h>
void merge_sort(int a[], int temp[], int left, int right)
{
	if (left >= right) // left > right 不用分了, left = right 就是分到一个元素了,也不用分了
		return;
	//先把数组分开 ,在 left < right 的前提下 
	int mid = (left + right) / 2;
	//分为左边的数组
	merge_sort(a, temp, left, mid );
	// 分为右边的数组
	merge_sort(a, temp, mid + 1, right);
	//开始归并
	// 定义一个 左边数组的第一个元素的下标
	int l_pos = left;
	//定义一个 右边数组的第一个元素的下标
	int r_pos = mid + 1;
	// 定义一个存放归并结果的数组下标,用来后面归并时候的操作
	int t_pos = left;
	//开始归并,到临时数组
	//在满足左边数组的第一个元素下标<=最后一个元素的下标 
	//和右边数组第一个元素小于等于最后一个元素的下标前提下
	while (l_pos <= mid && r_pos <= right)
	{
		if (a[l_pos]<a[r_pos])
			temp[t_pos++] = a[l_pos++];
		else
			temp[t_pos++] = a[r_pos++];
	}
	//退出循环后
	//假如左边数组还有元素,直接将左边数组的元素丢进去临时数组
	while(l_pos <= mid)
	{
		temp[t_pos++] = a[l_pos++];
	}
	//假如右边数组还有元素,直接将右边数组的元素丢进去临时数组
	while(r_pos <= right)
	{
		temp[t_pos++] = a[r_pos++];
	}
	// 将临时数组拷贝到 原数组
	while (left <= right)
	{
		a[left] = temp[left];
		left++;
	}

}
void MergeSort(int a[], int n)
{	//给 归并的结果存放的数组开辟一个空间
	int *temp = (int*)malloc(n*sizeof(int));
	if (temp)
	{	//开辟成功;
		//开始归并排序,先分开再归并
		merge_sort(a, temp, 0, n - 1);
		free(temp);
	}
		
}
void print(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%dt", a[i]);
	}
	printf("n");
}
int main()
{
	int a[] = { 9, 5, 2, 7, 12, 4, 3, 1, 11 };
	int n = 9;
	print(a, n);
	MergeSort(a, n);
	print(a, n);
	system("pause");
	return 0;
}

6 快速排序

思想:就是任意选定一个数为 pivotKey(中心轴关键字),为了方便,通常这个pivotKet 为第一个元素,把剩余的元素和 pivotKey 比较,比它大放到右边,比它小放到左边;然后重复操作,直到分到左右的序列只有一个就排好序了。
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】
推荐视频:快速排序算法;

我们排序要的效果是 左边比 pivot 小,右边比 pivot 大;

# include<stdio.h>
# include<windows.h>

void QuickSort(int arr[], int begin, int end)
{
	int left = begin;
	int right = end;
	//把第一个元素作为 pivotKey 值;
	int pivotKey = arr[left];
	if (left >= right) //如果 left > right 就不用排了,
		return;		  //或者 left = right;说明就分到左右两边就一个元素了
	while (left < right)
	{
		while (left < right && arr[right] >= pivotKey)//若右边的元素比 key 值大或等于,
			right--;							//说明不用赋值到左边,直接下标往前移动
		//退出循环后,说明, arr[right] < pivotKey,就要放去左边
		if (left < right)
			arr[left++] = arr[right];

		while (left < right && arr[left] <= pivotKey)
			left++;
		if (left < right)
			arr[right--] = arr[left];
	}
	// 当 left >= right 时候,说明这就是 pivotKey 的位置
	arr[left] = pivotKey;
	//继续递归调用 左边快速排序
	QuickSort(arr, begin, right - 1);
	//继续递归调动 右边快速排序
	QuickSort(arr, right + 1, end);
}
//排序入口
void quick_sort(int arr[], int n)
{
	QuickSort(arr, 0, n - 1);
}

void print(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);

	}
	printf("n");
}

int main()
{
	int a[] = { 10, 8, 4, 6, 9, 10, 123, 6, 2, 14, 3, 8, 5 };
	int n = sizeof(a) / sizeof(a[0]);
	print(a, n);
	
	quick_sort(a, n);
	
	print(a, n);

	system("pause");
	return 0;
}

7 计数排序

思想:计数排序就是统计一个无序序列的范围大小,把里面相同的元素个数统计出来,把每组相同元素的个数存放到一个数组中,用数组下标对应元素的值。然后再取出其中的值。
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

类似一种哈希表的映射:用元素的值映射到数组下标。

# include <stdio.h>
# include <windows.h>
# include <stdlib.h>
# include <assert.h>
void counting_sort(int a[], int n)
{
	//统计元素的范围大小,先找出元素的最大和最小值
	int min = a[0]; //假定最小值为第一个元素
	int 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	*temp = (int*)malloc(range*sizeof(int));
	assert(temp);
	//初始化数组
	memset(temp, 0, range*sizeof(int));
	//往数组temp添加相同元素的个数,于此同时,下标对应着元素的映射值
	for (int j = 0; j < n; j++)
		temp[a[j] - min]++;
	//开始把值赋给 a 数组
	int i = 0; //存放数组 a 的下标
	for (int j = 0; j < range; j++)
	{
		while (temp[j]--)
		{
			a[i++] = j + min;
		}
	}
	free(temp);
}
void print(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("n");
}
int main()
{
	int a[] = { 6, 3, 4, 5, 2, 8, 6, 9, 2, 1 };
	int n = sizeof(a) / sizeof(a[0]);
	print(a, n);
	counting_sort(a, n);
	print(a, n);

	system("pause");
	return 0;
}

注意:记得开辟内存时候大小别赋值错了,要不然改bug,改到你头疼;

8 冒泡排序

思想:冒泡排序就是相邻的两个元素比较,前面大于后面的就交换,重复这个步骤;

普通的冒泡排序相信大家都会,这里我提供一种优化版的;我们都知道假如你给的序列就是有序的,就不需要排序了,可是,在普通冒泡排序中,并不是这样,及时给你是有序的还是会一直找很多遍,优化版的只需要找一遍就可以;
数据结构 第八篇:八大排序【插入,希尔,选择,堆,归并,快排,冒泡,计数】

# include<stdio.h>
# include<windows.h>
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void bubble_sort(int arr[], int n)
{
	bool flag = false;
	for (int i = 0; i < n; i++)
	{	//没交换保持flag = false;
		flag = false;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
				flag = true;
				swap(&arr[j], &arr[j + 1]);
		}
		//若一趟下来,都没有交换,说明 已经是有顺序的了,直接退出外循环
		if (flag == false)
			break;
	}

}
void print(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("n");
}
int main()
{
	int arr[] = { 8, 9, 1, 4, 2, 3, 6, 7, 5, 5 };
	int n = sizeof(arr) / sizeof(arr[0]);
	print(arr, n);
	bubble_sort(arr, n);
	print(arr, n);


	system("pause");
	return 0;
}


喜欢 (0)