外国人做的网站吗,国内做网站的企业,网站建设费用分类,seo网站优化工具#x1f525;个人主页#xff1a;艾莉丝努力练剑 ❄专栏传送门#xff1a;《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题 #x1f349;学习方向#xff1a;C/C方向 ⭐️人生格言#xff1a;为天地立心#xff0c;为生民立命#xff0c;为… 个人主页艾莉丝努力练剑 ❄专栏传送门《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题 学习方向C/C方向 ⭐️人生格言为天地立心为生民立命为往圣继绝学为万世开太平 这个用来测试代码的对比排序性能的代码博主还是放在下面大家可以对比一下各种排序算法的运行时间从而对不同排序方法的时间复杂度有更加直观地认识 代码演示
//测试排序的性能对比
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];}//begin和end的时间差就是int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();QuickSort(a5, 0, N - 1);int end5 clock();int begin6 clock();MergeSort(a6, N);int end6 clock();int begin7 clock();BubbleSort(a7, N);int end7 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);printf(BubbleSort:%d\n, end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
} 前言本篇文章我们继续来介绍排序相关的知识点在初阶的数据结构与算法阶段我们把知识点分成三部分复杂度作为第一部分顺序表和链表、栈和队列、二叉树为第二部分排序为第二部分我们之前已经介绍完了第一部分算法复杂度和第二部分顺序表和链表、栈和队列、二叉树。本文我们继续开始学习第三部分中的排序的内容啦。 目录
正文
一、三路划分
1、三路划分的概念
2、思想
3、代码实现
1写法1
2写法2
3写法3
二、自省排序内观排序
1、找基准值出现问题
2、代码实现
3、完整代码
结尾 正文
一、三路划分
1、三路划分的概念
使用三路划分可以提升当数组中有大量相同的值时排序的时间效率三路划分的核心思想有点类似hoare版本的left、right左右指针和lomuto双指针法的前后指针的结合这里的hoare版本的左右指针和lomuto双指针的前后指针博主在之前的文章中已经介绍过了。 核心思想就是把数组中的数据分为三段比key小的值、跟key相等的值以及比key大的值因此叫做三路划分算法。 2、思想
三路划分实现的思想 1. key默认取left位置的值 2. left指向区间最左边right指向区间最后边cur指向left1位置 3. cur遇到比key小的值后跟left位置交换换到左边leftcur 4. cur遇到比key大的值后跟right位置交换换到右边right-- 5. cur遇到跟key相等的值之后cur 6. 直到 cur right 结束—— 3、代码实现
代码演示
1写法1
//三路划分
KeyWayIndex PartSort3Way(int* arr, int left, int right)
{int key arr[left];//left和right指向就是跟key相等的区间//[begin,left-1] [left,right] [right1,end]int cur left 1;while (cur right){//1、cur遇到比key小小的换到左边同时把key换到中间位置//2、cur遇到比key大大的换到右边if (arr[cur] key){Swap(arr[cur], arr[left]);left;cur;}else if (arr[cur] key){Swap(arr[cur], arr[right]);//cur不能动--right;}else{cur;}}KeyWayIndex kwi;kwi.leftkeyi left;kwi.rightkeyi right;return kwi;
} 不理解这个写法也没关系博主自己测试的时候用的是这个写法—— 2写法2
int _QuickSort3Way(int* arr, int left, int right)
{return;
}//三路划分实现
void QuickSort3Way(int* arr, int left, int right)
{if (left right){return;}//随机数取法srand((unsigned int)time(NULL));int randi left rand() % (right - left 1);Swap(arr[left], arr[randi]);//三数取中int midi _QuickSort3Way(arr, left, right);//三路划分int key arr[left];int cur left 1;int begin left;int end right;while (cur right){//1、cur遇到比key小小的换到左边同时把key换到中间位置//2、cur遇到比key大大的换到右边if (arr[cur] key){Swap(arr[cur], arr[left]);left;cur;}else if (arr[cur] key){Swap(arr[cur], arr[right]);//cur不能动--right;}else{cur;}}//三路划分 [begin,left-1] [left,right] [right1,end]QuickSort3Way(arr, begin, left - 1);QuickSort3Way(arr, right 1, end);
} 运行一下确实能跑出来—— 3写法3 此外还可以采用这种写法—— void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
void QuickSort(int* arr, int left, int right)
{if (left right)return;int begin left;int end right;//随机选keyint randi left (rand() % (right - left 1));Swap(arr[left], arr[randi]);//三路划分//left和right指向就是跟key相等的区间// [begin, left-1] [left, right] right1, end]int key arr[left];int cur left 1;while (cur right){//1、cur遇到比key小小的换到左边同时把key换到中间位置//2、cur遇到比key大大的换到右边if (arr[cur] key){Swap(arr[cur], arr[left]);left;cur;}else if (arr[cur] key){Swap(arr[cur], arr[right]);--right;}else{cur;}}// [begin, left-1] [left, right] right1, end]QuickSort(arr, begin, left - 1);QuickSort(arr, right 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums, 0, numsSize - 1);*returnSize numsSize;return nums;
}
时间复杂度O(n*logn) 。 二、自省排序内观排序 自省排序(Introsort)是一种混合排序算法它结合了快速排序(Quicksort)、堆排序(Heapsort)和插入排序(Insertion sort)的优点。其核心思想是利用快速排序的高效性同时在递归深度超过一定限制时切换到堆排序以避免最坏情况的发生从而保证整体性能。 introsort的快排排序OJ代码
——C库提出来的
1、找基准值出现问题 这里的introsort是introspective(自省的) sort采用了缩写他的名字其实表达了他的实现思路他的思路就是进行自我侦测和反省快速排序递归深度太深sgi stl使用的是深度为2倍排序元素数量的对数值就说明在这种数据序列下选key出现了问题性能在快速退化那么就不要再进行快排分割递归了改换为堆排序进行排序。 2、代码实现
代码演示
//自省排序(内观排序)
void IntroSort(int* arr, int left, int right, int depth, int defaultDepth)
{if (left right)return;//数组大小小于16的小数组换为插入排序简单递归次数if (right - left 1 16){InsertSort(arr left, right - left 1);return;}//当深度超过2*logn则改用堆排序if (depth defaultDepth){HeapSort(arr left, right - left 1);return;}depth;int begin left;int end right;//随机选keyint randi left (rand() % (right - left));Swap(arr[left], arr[right]);int prev left;int cur prev 1;int keyi left;while (cur right){if (arr[cur] arr[keyi] prev ! cur){Swap(arr[prev], arr[cur]);}cur;}Swap(arr[prev], arr[keyi]);keyi prev;//[begin,keyi-1] keyi [keyi1,end]IntroSort(arr, begin, keyi - 1, depth, defaultDepth);
}
时间复杂度O(n*logn) 。
3、完整代码
代码演示
#define _CRT_SECURE_NO_WARNINGS 1/*** Note: The returned array must be malloced, assume caller calls free().*/
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){//选出左右孩子中大的那⼀个if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆--向下调整建堆-- O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}// 自己先实现—— O(N * logN)int end n - 1;while (end 0){Swap(a[end], a[0]);AdjustDown(a, end, 0);--end;}
}
void InsertSort(int* a, int n)
{for (int i 1; i n; i){int end i - 1;int tmp a[i];// 将tmp插入到[0, end]区间中保持有序while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left right)return;//数组长度小于16的小数组换为插入排序简单递归次数if (right - left 1 16){InsertSort(a left, right - left 1);return;}//当深度超过2 * logN时改用堆排序if (depth defaultDepth){HeapSort(a left, right - left 1);return;}depth;int begin left;int end right;//随机选keyint randi left (rand() % (right - left 1));Swap(a[left], a[randi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;// [begin, keyi-1] keyi [keyi1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{int depth 0;int logn 0;int N right - left 1;for (int i 1; i N; i * 2){logn;}//introspective sort -- 自省排序IntroSort(a, left, right, depth, logn * 2);
}
int* sortArray(int* nums, int numsSize, int* returnSize)
{srand(time(0));QuickSort(nums, 0, numsSize - 1);*returnSize numsSize;return nums;
} 结尾
往期回顾
【数据结构与算法】数据结构初阶详解排序四——非比较排序计数排序鸽巢原理——对哈希直接定址法的变形应用排序算法复杂度及稳定性分析 本期内容需要回顾的C语言知识如下面的截图中所示指针博主写了6篇列出来有水字数嫌疑了就只放指针第六篇的网址博主在指针六把指针部分的前五篇的网址都放在【往期回顾】了点击【传送门】就可以看了。 大家如果对前面部分的知识点印象不深可以去上一篇文章的结尾部分看看博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了上一篇文章的链接博主放在下面了 【数据结构与算法】数据结构初阶详解顺序表和链表三——单链表上 结语本篇文章到这里就结束了对数据结构的排序知识感兴趣的友友们可以在评论区留言博主创作时可能存在笔误或者知识点不严谨的地方大家多担待如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正再次感谢友友们的关注和支持
