常见排序算法:交换排序——冒泡排序、极快排序

冒泡排序（Bubble Sort）基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。直观表达，每一趟遍历，将一个最大的数移到序列末尾。也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，将他们之间小的，或者大的值交换过来。遍历数列的工作是重复地进行，直到没有再需要交换的，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

1.1 算法思想

比较相邻的元素，如果前一个比后一个大，交换之。
第一趟排序第i个和第i 1个比较与交换，随后第i 1个和第i 2个一对比较交换，这样直到倒数第n-1个和最后n个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位

……

1.2 动图演示

学新通

算法实现：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
Swap(int *p1, int * p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Print(int *a)
{
for (int i=0;i<N;i )
{
printf("%d ",a[i]);
}
}
void BubbleSort(int* a, int n)
{
for (int j=0;j<n; j)
{
int size = 0;
for (int i=1;i<N-j; i)
{
if (a[i-1]>a[i])
{
Swap(&a[i-1],&a[i]);
size =1;
}
}
if (size==0)
{
break;
}
}
}
int main()
{
int a[N] = {0};
for (int i=0;i<N; i)
{
a[i] = rand();
}
BubbleSort(a,N);
Print(a);
return 0;
}

其中有一段优化程序，是定义一个变量判断排序是否在做无效操作，当内循环处于交换状态时，则数据未排序完毕，否则视为，数据已有序，我们就可以break;中止掉程序，避免做无用遍历。

1.3 冒泡最好的情况

待排序数列有序时，时间复杂度是O(N)。外循环只执行一次，内循环N-1,N-2,N-3……

1.2 冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

总结：

总的来说，冒泡排序是一种可以的排序，比直接选择排序要好，虽然有优化程序，但是，整体算法效率跟其他排序来比，还是差一些，比较适合新手学习。

2. 交换排序——快速排序

快速排序(Quicksort)是Hoare于1962年提出的一种二叉树结构的交换排序方法，有时候也叫做划分交换排序，是一个高效的算法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。这是一个分治算法，而且它就在原地交换数据排序。

学新通

是目前已知最快的排序算法，会比一般的排序更节省时间。

2.1 快速排序——挖坑法

学新通

算算法实现：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
for (int i=0;i<n; i)
{
printf("%d ",a[i]);
}
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
if (left < right)
{
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;
}
//最后将坑值给到坑位
a[pivot] = key;
//[left,right]
//[left,pivot-1] [pivot 1,right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
QuickSort(a, left, pivot - 1);
QuickSort(a, pivot 1, right);
}
else
{
return;
}
}
int main()
{
int a[10] = {0,9,5,6,3,2,1,7,8,4};
//挖坑法
QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
//打印
Print(a,sizeof(a) / sizeof(a[0]));
return 0;
}

学新通

快排的缺点

根据上面的代码，我们来分析一下快排的缺点：

学新通

如何解决快排对有序数据排序效率很差的方法？

三数取中法

学新通

所谓三数取中，不是取最大值，最小值，以及他们的中间值，而是取左边（begin）、右边（end）和中间（begin end）/2;

在有序的情况下中间的值刚好就是二分，将取出的值作为坑位，就不会出现最差的这种情况。我们依旧使用区间的开头作为“坑值”，但是要使用三数取中的逻辑。

选坑位：

int begin = left;
int end = right;
//使用三数取中选“坑值”，用mid存储其下标
int mid = GetMidIndex(a, begin, end);
//将区间首值当作坑位
//坑值与首值交换，避免算法混乱
//一般我们会将区间首值作为坑值
Swap(&a[begin], &a[mid]);//传地址调用
//存储坑值
int key = a[begin];

三数取中 GetMidIndex();

int GetMidIndex(int *a,int left,int right)
{
//二分
int mid = (right - left) / 2;
if (a[left]<a[mid])
{
if (a[left]<a[right])
{
if (a[mid]<a[right])
{
return mid;
}
else //a[mid]>=a[right]
{
return right;
}
}
else //a[left]>=a[right]
{
return left;
}
}
else //a[left]>=a[mid]
{
if (a[mid]<a[right])
{
if (a[left]<a[right])
{
return left;
}
else //a[left]>=a[right]
{
return right;
}
}
else //a[mid]>=a[right]
{
return mid;
}
}
}

交换Swap()；

//交换
void Swap(int* p1, int*p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

经过三数取中的处理，就不会出现快排的最坏情况，但也几乎不会成为最好的情况，有利有弊，我们在面试的过程中只需要写基础版的快排即可，以防时间不够。

小区间优化：

关于如果处理数据多，相应的递归次数多，会不会影响操作快排的性能？

学新通

当我们在使用快排对大量数据进行排序时，我们可以采用小区间优化，减少递归次数，达到优化程序得到目的。

对当待处理数据大于10的子序列进行快排递归。

对当待处理数据低于10的子序列进行直接插入排序进行排序，避免递归次数过多。

这个10不是固定的，可以根据处理的数据量调整。

//区间[left,right]
//左区间[left,pivot-1] 右区间[pivot 1,right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
// 小区间优化
if (pivot - 1 - left > 10)//对当待处理数据大于于10的子序列进行快排递归排序
{
//快排
QuickSort(a,left,pivot-1);
}
else
{
//采用直接插入排序，对当待处理数据低于10的子序列进行排序，避免递归
InsertSort(a left,pivot-1-left 1);//为什么最后要加1,例如：区间[0,9]实际上有10个数
}
if (right - (pivot 1) > 10)
{
QuickSort(a,pivot 1,right);
}
else
{
InsertSort(a pivot 1, right-(pivot 1) 1);
}

如果大家有想了解直接插入排序可以查看博主的另一篇：

常见排序算法之插入排序——直接插入排序、希尔排序：http://t.csdn.cn/X2mlq

2.3 快速排序——左右指针法

学新通

根据上图的示例我们应该能够理解左右指针法是什么样的逻辑，跟挖坑法是一样的思想，单趟排序完毕实现左边比坑位小，右边比坑位大。但是即使左右指针法跟挖坑法的思想是一样的，但是他们单趟的运算结果是不一样的。

学新通

算法实现：

void QuickSort(int* a, int left, int right)
{
if (left < right)
{
int begin = left;
int end = right;
//选坑位
int mid = GetMidIndex(a, begin, end);//三数取中
Swap(&a[begin], &a[mid]);
int key = begin;
while (begin < end)
{
while (begin < end && a[end] <= a[key])
--end;
while (begin < end && a[begin] >= a[key])
begin;
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[key]);
//分治递归
QuickSort(a, left, begin - 1);
QuickSort(a, begin 1, right);
}
}

2.4 前后指针法

采用perv记录区间第一个元素的下标，采用cur记录区间第二个元素的下标。

cur找小，每次遇到比key(坑值)小的值就停下来， prev。

交换prev和cur位置的值

算法实现：

//左右指针法
void QuickSort(int* a, int left, int right)
{
if (left < right)
{
//选坑位
int mid = GetMidIndex(a, left,right);//三数取中
Swap(&a[left], &a[mid]);
int key = left;
//初始化指向
int prev = left, cur = left 1;
while (cur<=right)
{
if (a[cur] <= a[key])//&& prev!=cur
{
prev;
//避免无效操作
if(cur!=prev)
Swap(&a[prev],&a[cur]);
}
cur;
}
Swap(&a[key], &a[prev]);
//分治递归
QuickSort(a, left, prev - 1);
QuickSort(a, prev 1, right);
}
}

快速排序的特性总结：

1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2.时间复杂度：O(N*logN)

3.空间复杂度：O(logN)

4.稳定性：不稳定

总结：

快排是我们一定要掌握的一种排序算法，在面试、笔试中也是很常见的，博主分享的三种方法：挖坑法，左右指针法，前后指针法，只少要掌握一种，但是要其他的方法也要知道算法思想。还有两种优化方式，小区间优化和三数取中，也要知道是什么逻辑，解决什么问题。

学新通

文章存在借鉴，如有侵权请联系修改删除！

这篇好文章是转载于：学新通技术网

常见排序算法:交换排序——冒泡排序、极快排序

交换排序

1.交换排序——冒泡排序

1.1 算法思想

1.2 动图演示

算法实现：

1.3 冒泡最好的情况

1.2 冒泡排序的特性总结：

总结：

2. 交换排序——快速排序

2.1 快速排序——挖坑法

算算法实现：

快排的缺点

三数取中法

小区间优化：

2.3 快速排序——左右指针法

算法实现：

2.4 前后指针法

算法实现：

快速排序的特性总结：

总结：

photoshop保存的图片太大微信发不了怎么办

《学习通》视频自动暂停处理方法

word里面弄一个表格后上面的标题会跑到下面怎么办

Android 11 保存文件到外部存储，并分享文件

photoshop扩展功能面板显示灰色怎么办

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

TikTok加速器哪个好免费的TK加速器推荐

怎样阻止微信小程序自动打开