海口网站建设是什么意思,企业网上注册登记系统,找企业老板的软件或平台,沈阳网站开发程序员工资代码位置#xff1a;test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言#xff1a;
1.1-排序定义#xff1a; 排序就是将一组杂乱无章的数据按照一定的规律#xff08;升序或降序#xff09;组织起来。(注#xff1a;我们这里的排序采用的都为升序)
1.2-排序分… 代码位置test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言
1.1-排序定义 排序就是将一组杂乱无章的数据按照一定的规律升序或降序组织起来。(注我们这里的排序采用的都为升序)
1.2-排序分类
常见的排序算法 插入排序 a. 直接插入排序 b. 希尔排序 选择排序 a. 选择排序 b. 堆排序交换排序 a. 冒泡排序 b. 快速排序归并排序 a. 归并排序非比较排序 a.计数排序 b.基数排序
1.3-算法比较 1.4-目的 今天我们这里要实现的是快速排序。
1.5-快速排序定义 通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分的关键字小然后分别对这两部分记录继续进行排序以达到整个序列有序。
二、快速排序-key的选择
2.1-直接在left和right中选择 这种选择方法具有局限性如果排序的序列已经为升序的情况下根据快速排序的定义我们可知快速排序的话会确定一个值的位置也就是key这个值的作用就是把数据分割成独立的两部分一部分是比他大一部分是比他小而如果是升序的情况下直接选择left选出的left的值是最小的也就是说右面的部分是N-1个数据而如果是用递归的方式实现的快排那么就需要递归N次也就是建立N个栈才能实现最终排序的操作如果数据量大就很有可能出现栈溢出的情况。
该情况下递归的图片如图所示 2.2-随机选择key: 随机选择key也就是说在数组下标范围内随机生成一个下标采用这个下标位置的数据值作为key这样的情况下我们就大大降低了选出的key是最小值的情况。能有效地减少栈溢出的情况。
2.3-三数取中 三数取中就是在left 、midi(rightleft)/2) 、right三个下标位置上的数据之间选择出这三个数据中的中间数。这样就避免了key为最小值的情况。
2.4-代码
void Swap(int* p, int* q) //交换函数
{int tem *p;*p *q;*q tem;
}
//直接选取法
int keyi left;//随机选keyi
int randi left (rand() % (right - left));
Swap(a[randi], a[left]);
int keyi left;//三数取中
int midi GetMidNumi(a, left, right);
if (midi ! left)Swap(a[midi], a[left]);
int keyi left;
int GetMidNumi(int* a, int left, int right) //三数取中法
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}if (a[left] a[right]){return left;}else{return right;}}if (a[left] a[mid]){if (a[left] a[right]){return left;}if (a[right] a[mid]){return mid;}else{return right;}}
}
三、快速排序-Hoare
3.1-思路
Hoare快速排序的思路就是: 如果key定义的是left那么就首先从右边找小找到以后再从左边出发找大找完以后后将他们俩的数据调换然后接着进行下一次先右后左找小再找大直到left小于right为止。同理若定义key在right处那么就先左后右处理方式与left类似。 这样排完一趟后我们能将大于key的数分布在右边小于key的数分布在左边最后我们只需要按照这个思路递归下去就实现快速排序啦。 注意:在递归时如果出现leftright的情况下我们就需要返回否则就会死循环。
左边做key为什么相遇位置一定比key小 3.2-过程图 3.3-代码
//Hoare
void QuickSort1(int* a, int left,int right) //快速排序---时间复杂度(O(N*logN))
{if (left right)return;int begin left;int end right;//直接选取法//int keyi left;//随机选keyi//int randi left (rand() % (right - left));//Swap(a[randi], a[left]);//int keyi left;//三数取中int midi GetMidNumi(a, left, right);if(midi!left)Swap(a[midi], a[left]);int keyi left;while (left right){//右边找小while (leftrighta[right] a[keyi]){--right;}//左边找大while (leftrighta[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);keyi left;//递归---小区间优化--小区间直接使用插入排序if (end - begin1 10){QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}
}
四、快速排序-挖坑法
4.1-思路 快速排序挖坑法的思路就是 先将第一个数据存放在临时变量k中形成一个坑位然后再数组的右边出发向左寻找小于key的数然后将这个数填在以前的坑位上然后在该处重新生成坑位接着在从左边向右寻找找大于ker的数然后将这个数填在生成的坑位上然后在该处重新生成坑位就这样一直循环实现上述操作直到left与right相遇为止此时该坑位就应该填key。。 这样排完一趟后我们能将大于key的数分布在右边小于key的数分布在左边最后我们只需要按照这个思路递归下去就实现快速排序啦。 注意:在递归时如果出现leftright的情况下我们就需要返回否则就会死循环。
4.2-过程图 4.3-代码
//挖坑法
void QuickSort2(int* a, int left, int right) //快速排序---时间复杂度(O(N*logN))
{if (left right)return;int begin left;int end right;//直接选取法//int keyi left;//随机选keyi//int randi left (rand() % (right - left));//Swap(a[randi], a[left]);//int keyi left;//三数取中int midi GetMidNumi(a, left, right);if(midi!left)Swap(a[midi], a[left]);int key a[left];int hole left;while (left right){while (left right a[right] key){--right;}a[hole] a[right];hole right;while (left righta[left] key){left;}a[hole] a[left];hole left;}a[hole] key;//递归---小区间优化--小区间直接使用插入排序if (end - begin 1 10){QuickSort2(a, begin, hole - 1);QuickSort2(a, hole 1, end);}else{InsertSort(a begin, end - begin 1);}
}
五、快速排序-前后指针法
5.1-思路
快速排序前后指针法的思路就是:
首先定义一个prevleft ; curleft1。这里我们实现的操作 1.cur找到比key小的值prove cur和prev位置的数调换然后cur。 2.cur找到比key大的值cur。
说明 1.prev要么紧跟着curprev下一个位置就是cur。 2.prev跟cur中间隔着一段比key大的值。 就这样按上述思想进入循环知道直到cur走到数组末端的下一个位置为止接下来我们要实行的操作就是将keyi位置的值(key)与prev位置的值交换。这样排完一趟后我们能将大于key的数分布在右边小于key的数分布在左边最后我们只需要按照这个思路递归下去就实现快速排序啦。 注意:在递归时如果出现leftright的情况下我们就需要返回否则就会死循环。
5.2-过程图 5.3-代码
//前后指针法
void QuickSort3(int* a, int left, int right) //快速排序---时间复杂度(O(N*logN))
{if (leftright)return;int begin left;int end right;//直接选取法//int keyi left;//随机选keyi//int randi left (rand() % (right - left));//Swap(a[randi], a[left]);//int keyi left;//三数取中int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[midi], a[left]);int keyi left;int prev left;int cur left 1;while (curright){if(a[cur]a[keyi]prev!cur)Swap(a[cur], a[prev]);cur;}Swap(a[keyi], a[prev]);keyi prev;//递归---小区间优化--小区间直接使用插入排序if (end - begin 1 10){QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}}
六、递归的问题与优化
6.1-递归的问题 1.效率问题略有影响。 2.深度太深时会栈溢出。
递归过程图 6.2-小区间优化
小区间优化的思想就是 将递归的最后几层也就是基本有序的小区间采用直接插入排序的方法不再采用递归的方式这样能够减少递归时所开辟栈。 因为递归栈的开辟相当于二叉树而二叉树的最后一层相当于总数的一半如果把最后一层省掉也就是省去了递归所需开辟栈的大概50%的空间。 所以我们可以通过小区间优化来减少栈的开辟在不影响时间复杂度的情况下也减小了深度太深时会栈溢出的问题。
6.3-小区间优化代码
//递归---小区间优化--小区间直接使用插入排序
if (end - begin 1 10)
{QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi 1, end);
}
else
{InsertSort(a begin, end - begin 1);
}
七、递归改非递归 由上述可知通过递归实现快排具有一定的弊端也就是栈溢出所以这里我们可以采取将递归改成非递归的方式来实现快速排序
7.1-方式 1.直接改成循环。 2.使用栈辅助改成循环。 通过上述代码可观察发现递归改非递归的第一种方式我们是实现不了的所以我们这里需要借助栈来辅助将递归改成循环。
7.2-思路 这里的思路就是将递归时的左右区间存入栈中。然后在循环的过程中我们只需将区间值出站即可。 注意栈的原理是后进先出。
7.3-代码
#include Stack.h
//递归改非递归
void QuickSortNonR(int* a, int left, int right) //快速排序---时间复杂度(O(N*logN))
{ST ps;STInit(ps);STpush(ps, right); //入栈STpush(ps, left); //入栈while (!STEmpty(ps)){int begin STTop(ps); //取栈顶元素STPop(ps); //出栈int end STTop(ps); //取栈顶元素STPop(ps); //出栈int midi GetMidNumi(a, begin, end);if (midi ! begin)Swap(a[midi], a[begin]);int keyi begin;int prev begin;int cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[keyi], a[prev]);keyi prev;if (keyi 1 end){STpush(ps, end); //入栈STpush(ps, keyi 1); //入栈}if (keyi - 1 begin){STpush(ps, keyi - 1); //入栈STpush(ps, begin); //入栈}}for (int i 0; i right; i){printf(%d , a[i]);}printf(\n);STDestory(ps);
}7.4-栈的代码
#pragma once#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps); //初始化
void STDestory(ST* ps); //释放销毁void STpush(ST* ps, STDataType x); //入栈
void STPop(ST* ps); //出栈
int STSize(ST* ps); //栈中元素个数
bool STEmpty(ST* ps); //判断栈空
STDataType STTop(ST* ps); //栈顶元素
#define _CRT_SECURE_NO_WARNINGS 1
#include Stack.hvoid STInit(ST* ps) //初始化
{assert(ps);ps-a (STDataType*)malloc(sizeof(STDataType) * 4);if (ps-a NULL){perror(malloc);return;}ps-capacity 4;ps-top 0; //top是栈顶元素的下一个位置//ps-top-1 //top是栈顶元素位置
}void STDestory(ST* ps) //释放销毁
{assert(ps);ps-top 0;ps-capacity 0;free(ps-a);ps-a NULL;
}void STpush(ST* ps, STDataType x) //入栈
{assert(ps);if (ps-top ps-capacity){STDataType* tem (STDataType*)realloc(ps-a, sizeof(STDataType) * ps-capacity * 2);if (tem NULL){perror(realloc);return;}ps-a tem;ps-capacity * 2;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps) //出栈
{assert(ps);assert(!STEmpty(ps));ps-top--;
}int STSize(ST* ps) //栈中元素个数
{assert(ps);return ps-top;
}bool STEmpty(ST* ps) //判断栈空
{assert(ps);return ps-top 0;
}STDataType STTop(ST* ps) //返回栈顶元素
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
}八、结语 上述内容即是我个人对数据结构排序中快速排序的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞关注收藏与支持我会更加努力的学习编程语言还望各位多多关照让我们一起进步吧
