数据结构|数据结构 第八篇（八大排序【插入，希尔，选择，堆，归并，快排，冒泡，计数】）
文章目录
- 一 排序的基本概念
- 二 常见的基本排序
-
- 1. 插入排序
- 2. 希尔排序
- 3. 选择排序
- 4.堆排序
-
- 1）维护堆的性质
-
- 递归维护堆的性质
- 非递归维护堆的性质
- 2）建立堆
- 3）堆排序
- 5 归并排序
- 6 快速排序
- 7 计数排序
- 8 冒泡排序
一 排序的基本概念 排序啊，一个很有趣的话题，排序就是使得数据能够成为一种有序的操作。（并不严谨，可是这样理解就够了。）准确的定义，朋友们可以看看数据结构的书哈，我就不复制粘贴了哈。
- 为什么要有排序这个概念呢，它有啥用呢？
答：其实排序的主要目的就是为了提高查找效率，就比如说，二分查找算法，前提必须有有序的数据才可以使用，极大提高了查找效率。，在我的理解，我的理解上啊，其实从广义上讲：把数据结构分为四大块，线性表，非线性表，排序，查找。前面的三大板块都是为了查找做准备的，都是为了提高查找效率，怎么说呢？假如你在某个浏览器，输入你想要查找的东西，可是它半天都没显示出来，这就说明这个浏览器很菜，为什么菜，很大原因就是底层的代码，如数据结构是按，线性的，非线性的，使用的排序算法安排的不合理导致的呗。所以有必要学习以下排序，并且它非常有用哦。
- 排序的稳定与否判断
稳定：如果a没排序之前在b前面,且a = b,在排序之后a仍然在b的前面；
不稳定：如果a排序之前在b前面,且a=b,在排序之后a有可能会出现在b的后面；
- 内外排序是啥？
内排序：所有排序操作都在内存中完成；适合小数据的排序二 常见的基本排序 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
# include
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.堆排序 思想：堆排序，也是叫做优先队列，使用一种“完全二叉树”的模式去存储数据，然而完全二叉树又可以用数组的形式的方式存储。而且，每一个父结点的值大于（小于）左右孩子的节点值，叫做大堆（小堆）。
完全二叉树的性质：
推荐视频：堆排序(heapsort) 或者这个 排序算法：堆排序【图解+代码】,两个都讲得很清楚；
- 结点 下标 i 父结点的下标：i/2 -1;
- 结点下标 i 的左孩子的下标：i *2 +1;
- 结点下标 i 的有孩子的下标：i *2 +2；
文章图片
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）堆排序
建立起的对我们结构我们还没开始排序呢。现在开始排序。
因为刚刚建立了大堆，所以我们可以知道根结点一定是堆树中最大的值，我们而要做就是
- 把根节点和最后一个结点做一次交换，然后取出交换后的最后一个结点，这样就可以把最大的值取出来了，取出来的目的也是为了排序，然后由于交换了就会破坏堆的结构。
- 然后对交换后的根结点再进行一次堆化就可以了。继续完成上诉操作，依次把堆树中最大的值取出来，这样就可以排序啦。
文章图片
void HeapSort(int* a,int n)
{ intlastNode= n -1;
for (int i = lastNode;
i >= 0;
i--) //从最后一个结点开始和根交换
{swap(a[0],a[i]);
//交换后，根又不满足堆的性质了，所以重新堆化
heapify(a,i,0);
//对根堆化，根的下标为 0；数组大小每次会减一
}
}
5 归并排序 思想：归并排序就是将一个无序得序列，先分开，直到分到只有一个元素，然后再合并排序；
推荐一个视频：排序算法：归并排序【图解+代码】，这个视频讲得很清楚。
# include
# include
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]6 快速排序 思想：就是任意选定一个数为 pivotKey(中心轴关键字)，为了方便，通常这个pivotKet 为第一个元素，把剩余的元素和 pivotKey 比较，比它大放到右边，比它小放到左边；然后重复操作，直到分到左右的序列只有一个就排好序了。
文章图片
推荐视频：快速排序算法；
我们排序要的效果是 左边比 pivot 小，右边比 pivot 大；
# include
# includevoid 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
# include
# include
# include
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
# include
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;
}
推荐阅读
- 2018年11月19日|2018年11月19日 星期一 亲子日记第144篇
- 《魔法科高中的劣等生》第26卷（Invasion篇）发售
- 拍照一年啦，如果你想了解我，那就请先看看这篇文章
- 亲子日记第186篇，2018、7、26、星期四、晴
- 漫画初学者如何学习漫画背景的透视画法（这篇教程请收藏好了！）
- 两短篇
- 第四十三篇接纳孩子的感受
- 感恩日记第111篇2020.02.06
- 2018年8月25日|2018年8月25日 星期六 晴 亲子日记第259篇
- 25篇中考随笔