前言:
接上篇,排序算法除了选择排序(希尔排序)和插入排序(堆排序)之外,还用交换排序(冒泡排序、快速排序)和归并排序已经非比较排序,本篇来深层解析这些排序算法
一、交换排序
1.1、冒泡排序
冒泡排序,这个再熟悉不过了,学校中老师讲的第一个排序就是冒泡排序;直接看代码
代码如下:
//冒泡排序
void BubbleSort(int* arr, int n)
{
int exchange = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
时间复杂度:O(n^2);空间复杂度O(1)。
1.2、快速排序
快速排序,是hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想为:任意取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列所有元素均大于基准值然后左右子序列重复此过程,直到所有元素都排列在相应位置上。
实现快速排序主要框架如下:
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right) {
return;
}
//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分
int meet = _QuickSort(a, left, right);
QuickSort(a, left, meet - 1);
QuickSort(a, meet + 1, right);
}
下面的不同方法指的是找基准值的方法不同而已。
1.2.1、hoare版本
思路:
1. 创建左右指针,却基准值
2. 从左到右找出比基准值大的数据,从右到左找出比基准值小的数据,左右指针数据交换,进入下一次循环
这里可能有一些问题,
1.跳出循环后,right位置的值一定不大于key?
当left > right时,即right走到了left的左侧,而left走过的位置值都不大于key,因此right此时指向的数据一定不大于key
2.为什么left或者right指定的数据与key值相等也要交换?
这里如果,数组中大量的数据都相等,不进行交换的话,就无法进行有效的分割数组。
代码实现:
//快速排序
int _QuickSort1(int* arr, int left, int right)
{
int key = arr[left];
int mid = left;
left++;
while (left <= right)
{
//左边找大
while (left<=right && arr[left] < key)
{
left++;
}
//右边找小
while (left <= right && arr[right] > key)
{
right--;
}
if (left <= right)
{
Swap(&arr[left], &arr[right]);
left++;
right--;
}
}
Swap(&arr[mid], &arr[right]);
return right;
}
1.2.2、挖坑法
思路:
创建左右指针;首先从右向左找出比基准值小的数据,找到后立即放入左边 "坑" 中,当前位置变为新的 "坑",然后从左往右找出比基准值大的数据,找到后立即放入右边坑中,当前位置变为新的 "坑",结束循环后将最开始存储的分界值放入当前的 "坑"中,返回当前"坑"下标。
代码实现如下:
int _QuickSort2(int* arr, int left, int right)
{
int tmp = arr[left];
int hole = left;
left++;
while (left < right)
{
//从右边开始找
while (left < right && arr[right] > tmp)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < tmp)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = tmp;
return hole;
}
1.2.3、lomuto指针法
思路:
创建前后指针,从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。
代码实现:
int _QuickSort(int* arr, int left, int right)
{
int prev = left, pcur = left + 1;
int key = left;
while (pcur <= right)
{
if (arr[pcur] < arr[key] && ++prev != pcur)
{
Swap(&arr[prev], &arr[pcur]);
}
pcur++;
}
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) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid+1, right, tmp);
//合并数组
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
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 n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
三、非比较排序
非比较排序,就是不进行比较数据来进行排序。
计数排序
1> 统计相同元素出现次数
2> 根据统计的结果将序列回收到原来的序列中
这里又会存在一些问题,比如如果数据是负数,那该怎样开辟空间?
这里,我们开辟空间大小为数组数据最大值和最小值之差。
然后在将统计结果返回到原来数组当中时,让数组下标加上原数组最小值即可。
//计数排序
void CountSort(int* arr, int n)
{
int max = arr[0];
int min = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//开辟空间
int range = max - min + 1;
int* tmp = (int*)calloc(sizeof(int),range);
if (tmp == NULL)
{
perror("calloc fail");
return;
}
for (int i = 0; i < n; i++)
{
tmp[arr[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (tmp[i]--)
{
arr[j++] = i + min;
}
}
}
各种排序算法的算法复杂度和稳定性分析
到这里,排序算法就结束了,希望你能有所收获
感谢各位大佬支持并指出问题,
如果本篇内容对你有帮助,可以一键三连支持以下,感谢支持!!!
标签:归并,right,基准值,int,arr,冒泡排序,排序,left From: https://blog.csdn.net/LH__1314/article/details/140799886