数据结构——排序（续集）

---

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥

✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨

---

上一篇博客我们说到了四种排序算法数据结构——排序，这一篇博客我们继续在排序算法里面遨游~体会更多的排序算法的魅力~

目录

交换排序

冒泡排序

基本思想

代码

时间复杂度

快速排序

基本思想

Hoare版本找基准值

挖坑法找基准值

lomuto前后指针找基准值

快速排序特性总结

归并排序

基本思想

代码

时间复杂度

交换排序

》 交换排序基本思想：所谓交换，就是 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

》 交换排序的 特点 是：将 键值较大的记录向序列的尾部移动，键值小的记录向序列的前部移动

交换排序包括两种，一种是冒泡排序，一种是快速排序，我们一个个来看看~

冒泡排序

基本思想

它的基本思想是根据元素个数来比较不同趟数， 每一趟里面元素两两比较 ，如果满足一定的条件就进行交换， 最终最大的（或者最小的）元素会到最后面 ~

这里举一个简单的例子：

现在我们想要排序【3，5，9，7，2】这个数组排成升序~

第一趟比较：

【3，5，9，7，2】——>【3，5，9，7，2】——>【3，5，7，9，2】——>【3，5，7，2，9】

第二趟比较：（最后一个元素已经是最大的了，排序剩下的元素）

【3，5，7，2，9】——>【3，5，7，2，9】——>【3，5，2，7，9】

第三趟比较：

【3，5，2，7，9】——>【3，2，5，7，9】

第四趟比较：

【2，3，5，7，9】

经过四趟的排序，我们的数组就已经成为了升序~

代码

通过前面的思路，我们可以写出下面的代码：

//冒泡排序
void BubbleSort(int* arr, int sz)
{
//外层循环比较趟数
for (int j = 0; j < sz - 1; j++)
{
//内层循环元素两两比较
for (int i = 0; i < sz - 1 - j; i++)
{
//前面元素比后面大就交换
if (arr[i] > arr[i + 1])
{
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
}
}

排序成功~

时间复杂度

按照上面的代码，第一趟比较次数为n-1，第二趟比较次数为n-2……第n-2趟比较次数为2，第n-1趟比较次数为1，是一个等差数列（n-1+1)(n-1)/2,根据时间复杂度的规则也就是O（N^2),事实上，上面的代码我们也可以给它做出优化~如果数组有序，那么第一趟就不会进行交换，我们可以标记一下~后面就不需要继续比较了~

优化代码：

//优化的冒泡排序
void BubbleSort(int* arr, int sz)
{
//外层循环比较趟数
for (int j = 0; j < sz - 1; j++)
{
int flag = 1;//标记当前数组是否有序
//内层循环元素两两比较
for (int i = 0; i < sz - 1 - j; i++)
{
//前面元素比后面大就交换
if (arr[i] > arr[i + 1])
{
//进行了交换，说明数组无序
flag = 0;
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
if (flag == 1)
{
break;//数组有序，不需要继续比较
}
}
}

排序成功~这样如果是一个有序的数组，时间复杂度就会降低，最好的情况是第一趟就发现有序，那么时间复杂度为O（N），如果本来就是无序的，时间复杂度依然是O（N^2)

现在我们来比较一下排序100000个数据的运行时间~

我们可以看到冒泡排序达到了二十几秒，所以我们排序中是不推荐使用的~

快速排序

基本思想

》 快速排序是Hoare于1962年提出的 一种二叉树结构的交换排序方法

》 基本思想为： 任取待排序元素序列中的某元素作为基准值 ，按照该排序码 将待排序集合分割成两子序列 ， 左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值（这样就可以 把基准值放到它该放的位置上） ，然后 再分左右子序列重复该过程 ，直到所有元素都排列 在相应位置上为止。

Hoare版本找基准值

》 right 从右往左找比基准值要小的数据

》 left 从左往右找比基准值要大的数据

》找到之后， left 和 right 交换
》当 left > right ，基准值 key 和 right 交换

//Hoare版本找基准值
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;//记录基准值下标
left++;
while (left <= right)
{
//每一个循环都写left <= right，确保不越界
// right 从右往左 找比基准值要小的数据
while (left <= right && arr[right] > arr[keyi])
{
right--;
}
// left 从左往右 找比基准值要大的数据
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//找到了，交换
if (left <= right)
{
Swap(&arr[left], &arr[right]);
//交换后继续找直到left>right
left++;
right--;
}
}
Swap(&arr[keyi], &arr[right]);
return right;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
//找基准值
int key = _QuickSort(arr, left, right);
//左右子序列重复操作
//[left,key-1]   [key+1,right]
if (left < key - 1)
{
//需要判断，避免越界！！！
QuickSort(arr, left, key - 1);
}
if (key + 1 < right)
{
//需要判断，避免越界！！！
QuickSort(arr, key + 1, right);
}
}

我们可以看到快速排序效率还是很高的~

挖坑法找基准值

这里快速排序也是使用递归来实现，但是找基准值方法不一样，我们一起来看看~

》创建左右指针left、right，首先 right 从右向左找出比基准值小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"

》然后 left 从左向右找出比基准值大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"

》结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）

我们依然画图理解~

3比基准值小，把它拿到原来的坑位，right成为新的坑位

left找比基准值大的7，找到了，7去填坑

现在的left成为新坑

right继续找，如果相遇就停下来~

arr【hole】=key；返回坑hole就是基准值下标

代码：

//挖坑法找基准值
int _QuickSort2(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];//保存最开始坑位值,也就是基准值
while (left < right)
{
// right 从右向左找出比基准值小的数据
// 找到后立即放入左边坑中，当前位置变为新的"坑"
//这里相等就继续遍历
while (left<right && arr[right] >= key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
// left 从左向右找出比基准值大的数据
// 找到后立即放入右边坑中，当前位置变为新的"坑"
while (left<right && arr[left] <= key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
//相遇或者left>right跳出循环
arr[hole] = key;
return hole;//返回坑位
}

排序成功~

注意点：

》这里相等也继续找

例：（一方面，如果里面元素相同，那么不断的交换也就降低了效率~）

另外一方面，同时以代码里面的数组为例

{ 9,1,2,5,7,4,8,6,3,5 }

第一轮：

left最开始就是hole的位置，arr【left】=key，那么就会不停的与自己进行交换，成为新坑位，不会往后面走，这就出现问题了~死循环了~

有的人可能会说left++不就可以了吗？

我们依然使用上面的数组验证~

 

这个时候我们就发现坑位一直在俩个位置变化，没有改变~因为依然有相同的元素，所以left++也不能解决这个问题~

接下来我们看看left能不能++呢？

》这就是另外一个注意点：left不能++

我们依然使用上面的数组验证~

这就分左右序列了，我们先来看看左边的序列

我们继续来看看它的左边的序列

我们发现left和right已经相遇了，那么就不会去填坑了~所以left不能++

所以写代码的时候还是需要多多注意这些问题~

时间复杂度依然为O（N*logN）

lomuto前后指针找基准值

基本思想： 创建前后指针，从左往右找比基准值小的进行交换，使得小于基准值的都排在基准值的左边

思路：

//lomuto前后指针找基准值
int _QuickSort3(int* arr, int left, int right)
{
int key = left;//当前基准值下标
int prev = left, cur = left + 1;//cur探路
while (cur <= right)//确保下标不越界
{
//比基准值小，++prev如果不等于cur，交换prev和cur位置数据,cur++
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
cur++;
}
//比基准值大
else
{
cur++;
}
}
//cur已经越界，交换key和prev位置数据，返回prev就是基准值下标
Swap(&arr[key], &arr[prev]);
return prev;
}

不断地二分最终得到每个子序列只有一个元素（只有一个元素肯定是有序的），然后合并序列成为有序的序列~这里毫无疑问就需要使用到递归了！我们来写写代码~

代码

//归并排序
//合并序列成有序的序列，需要一个临时数组来保存
void _MergeSort(int* arr, int left, int right, int* tmp)
{
//相等说明只有一个元素，直接返回
if (left >= right)
{
return;
}
//分成子序列
int mid = left + (right - left) / 2;//这种写法好处是避免数据过大引起存储不了
//【left，mid】  【mid+1，right】
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);

//合并左右有序子序列
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;//保存数组的下标
//合并
while (begin1 <= end1 && begin2 <= end2)
{
//前面序列元素小，就放到tmp数组中
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
//别忘记下标往后面走
}
else
{
tmp[index++] = arr[begin2++];
//别忘记下标往后面走
}
}
//已经跳出循环，说明越界了
// 处理还有剩余元素的情况
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}

while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}

//将排序好的tmp给arr
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}


//归并排序
void MergeSort(int* arr,int sz)
{
//开辟一块空间存排序的数组
int* tmp = (int*)malloc(sizeof(int) * sz);
if (tmp == NULL)
{
perror("malloc fail");
exit(1);
}
//调用排序方法
_MergeSort(arr, 0, sz - 1, tmp);
//动态申请的空间一定要释放,并且及时置为空
free(tmp);
tmp = NULL;
}

排序成功~

时间复杂度

递归的时间复杂度=递归的次数*一次递归的时间复杂度

这与我们前面的快速排序时间复杂度推导方法是一样的，也是一个二分递归的过程~我们认为递归的次数为logN，一次递归时间复杂度O（N），时间复杂度也为（N*logN），这也是一个比较快速的排序算法

比较时间

到目前为止，我们已经知道了解了七种排序算法~这些排序算法都是比较排序的方法~想看更多的内容~请看下一篇详解~

---

♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

✨✨✨✨✨✨个人主页✨✨✨✨✨✨

---

原文地址：https://blog.csdn.net/2401_82924480/article/details/143668393

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！