前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值
基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。
快速排序实现主框架:
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//keyi即是基准值
int keyi = _QuickSort1(arr, left, right);//实现找基准值的方法
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
算法思路: 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 keyi = left;
++left;
while (left <= right)
{
while (left <= right && arr[right] > arr[keyi])
{
right--;
}
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
Swap(&arr[keyi], &arr[right]);
return right;
}
思路: 创建左右指针。首先从右向左找出比基准小的数据,找到后立即放入左边坑中,当前位置变为新的"坑",然后从左向右找出比基准大的数据,找到后立即放入右边坑中,当前位置变为新的"坑",结束循环后将最开始存储的分界值放入当前的"坑"中,返回当前"坑"下标(即分界值下标)
int _QuickSort2(int* arr, int left, int right)
{
int hole = left;//坑
int key = arr[hole];//坑位数据
while (left < right)
{
while (left < right && arr[left] >= key)
{
--right;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key)
{
++left;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = arr[left];
return hole;
}
创建前后指针,从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。
int _QuickSort3(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
以上就是快速排序当中查找基准值的三种方法
快速排序特性总结: 1. 时间复杂度:O(nlogn) 2. 空间复杂度:O(logn)
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);//栈的初始化
STPush(&st, right);//压栈
STPush(&st, left);//压栈
while (!STEmpty(&st))
{
//取栈顶元素两次
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//找基准值[begin,end]
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间:[begin,keyi-1]
//右区间:[keyi+1,end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st,keyi + 1);
}
if (keyi - 1 > begin)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);//销毁
}
冒泡排序核心思想是通过反复遍历待排序的序列,比较相邻的元素并交换它们的位置,使得每一趟遍历后,最大的元素逐渐"冒泡"到序列的末尾。
核心步骤如下:
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
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²),由于每次都要遍历未排序的部分,并且重复多次比较操作,因此效率较低。
直接插入排序(Direct Insertion Sort)的原理是通过逐步将待排序数组中的元素插入到已排序部分的正确位置,最终实现排序。它是一种简单且直观的排序算法,尤其适用于小规模或近乎有序的数据集。
假设有一个数组 [5, 2, 9, 1, 5, 6] 需要排序,步骤如下:
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
希尔排序(Shell Sort)是插入排序的改进版,它通过比较和交换不相邻的元素来减少数据的移动次数,以加速排序过程。希尔排序的核心思想是将待排序的序列按一定间隔分组,分别对每一组进行插入排序,逐步缩小间隔,直到间隔为 1 时,完成最终的插入排序。
假设对数组 [23, 29, 15, 19, 31, 7, 9, 5, 2] 进行希尔排序,初始数组如下:
第一步:假设初始间隔为 4,将数组分组进行插入排序:
结果数组:[2, 7, 9, 5, 23, 29, 15, 19, 31]
第二步:缩小间隔到 2,继续分组排序:
结果数组:[2, 5, 9, 7, 15, 19, 23, 29, 31]
第三步:间隔为 1 时,进行最后一次插入排序,得到最终排序结果:[2, 5, 7, 9, 15, 19, 23, 29, 31]
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
归并排序算法思想: 归并排序(MERGE-SORT)是建立在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法(Divide andConquer)的⼀个非常典型的应⽤。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成⼀个有序表,称为二路归并。归并排序核心步骤:
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 = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//要么begin1越界,要么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. 时间复杂度: O(nlogn) 2. 空间复杂度: O(n)
计数排序⼜称为鸽巢原理,是对哈希直接定址法的变形应⽤。
操作步骤: 1)统计相同元素出现次数 2)根据统计的结果将序列回收到原来的序列中
void CountSort(int* arr, int n)
{
int max = arr[0];
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if(arr[i] < min)
{
min = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!");
exit(1);
}
//初始化range中的数据为0
memset(count, 0, range * sizeof(int));
//统计数组中每个数据出现的个数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
int index = 0;
//取count中的数据往arr中放
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}
1. 快速排序:
2. 希尔排序:
3. 直接插入排序:
4. 归并排序:
5. 计数排序: