设计网站公司名称,工业产品设计有哪些,潮州网站开发,法人查询企业名称数据结构----算法–排序算法
一.冒泡排序#xff08;BubbleSort#xff09;
1.冒泡排序的核心思想
相邻两个元素进行大小比较#xff0c;如果前一个比后一个大#xff0c;就交换
注意#xff1a;
在冒泡排序的过程中#xff0c;促进了大的数往后去#xff0c;小的数…数据结构----算法–排序算法
一.冒泡排序BubbleSort
1.冒泡排序的核心思想
相邻两个元素进行大小比较如果前一个比后一个大就交换
注意
在冒泡排序的过程中促进了大的数往后去小的数往前去
2.冒泡排序的实现步骤
1.从头开始将相邻两个元素进行大小比较如果前一个比后一个大就交换直到全部比较完成固定最右边的值此时固定的就是最大的值
2.重复操作1直到最后剩一个元素了排序结束
3.看下图冒泡排序的过程加深理解 4.冒泡排序的代码实现如下
void BubbleSort(int a[],int length) {if (a NULL || length 0) return;for (int i 0; i length -1; i) {for (int j 0; j length -1-i; j) {if (a[j] a[j 1]) {a[j] a[j] ^ a[j 1];a[j 1] a[j] ^ a[j 1];a[j] a[j] ^ a[j 1];}}}
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {cout a[i] ;}cout endl;
}int main() {int a[] { 3,11,9,2,16,8,20,28,31,44 };BubbleSort(a,sizeof(a)/sizeof(a[0]));//将排好序的数组进行输出Print(a,sizeof(a)/sizeof(a[0]));cout endl;return 0;
}5.冒泡排序的优化 我们发现第二趟完事之后这个数组就已经有序了我们就不需要再进行下面几次的操作了
1.优化的思路
我们在进行冒泡排序时每一趟都找到最后交换的位置那下一趟的右端范围到最后交换位置之前就可以了用这种方法优化之后冒泡排序所需要的次数一般都会大幅减少如果没有交换发生就说明此数组已经有序了
2.对上面优化方法的两种实现方式
方式一通过改变总趟数改变总趟数的同时每一次的范围也会进行改变来进行代码的优化此方法需要用到数学进行计算下面为方法一要注意的一些问题
当缩小范围减少趟数的时候也就是对第一个循环进行的操作我们控制的是左端点右端点不动并且通过数学的计算得出每次左端点要变为 数组长度 - 最后交换的位置在数组中的下标所得的值
方式二通过直接对范围进行修改不用管趟数因为当当前范围中没有发生交换那么冒泡排序就会结束
3.优化的代码如下这里用方法一实现
#includeiostream
using namespace std;void BubbleSort(int a[],int length) {if (a NULL || length 0) return;int flag 0;for (int i 0; i length -1; i) {//总趟数flag 0;for (int j 0; j length -1-i; j) {//每趟的范围if (a[j] a[j 1]) {a[j] a[j] ^ a[j 1];a[j 1] a[j] ^ a[j 1];a[j] a[j] ^ a[j 1];flag j 1;}}if (flag 0) break;//如果没有交换发生就说明此数组已经有序了,结束操作i length - flag - 1;//这里多减了一个一是因为每一次循环i都会自增1}
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {cout a[i] ;}cout endl;
}int main() {int a[] { 3,9,2,11,8,16,20,28,31,44 };BubbleSort(a, sizeof(a) / sizeof(a[0]));//将排好序的数组进行输出Print(a, sizeof(a) / sizeof(a[0]));return 0;
}二.选择排序SelectSort
1.选择排序的核心思想
每趟找最值放入到对应位置上整体要保持一致性要找最大就只能找最大反则亦然
2.选择排序的实现步骤
1.假设数组的第一个元素就是最大值此时最大值的下标为0然后依次进行比较如果遇到大的数那么最大值的下标进行更新直到所有的元素都比较完成了将最大值与数组最右边的数进行互换如果最大值的下标就是数组最右边元素的下标那么就不交换固定数组最右边的元素之后此位置就不参与比较了
2.重复操作1直到数组中只剩一个元素了排序结束
3.选择排序的代码实现如下
#includeiostream
using namespace std;void SelectSort(int a[], int length) {if (a NULL || length 0) return;int i;int j;for ( i 0; i length - 1; i) {int MaxIndex 0;for (j 0; j length - i-1; j) {//与最值进行比较if (a[MaxIndex] a[j]) {MaxIndex j;}}//将最值放到数组的最右边通过交换实现的if (MaxIndex ! j-1) {//如果最大值的下标不是数组最右边元素的下标进行交换a[MaxIndex] a[j-1] ^ a[MaxIndex];a[j-1] a[j-1] ^ a[MaxIndex];a[MaxIndex] a[j-1] ^ a[MaxIndex];}}
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {cout a[i] ;}cout endl;
}int main() {int a[] { 9,1,3,7,98,58,15,4,45,5,2131,23 };SelectSort(a, sizeof(a) / sizeof(a[0]));//将排好序的数组进行输出Print(a, sizeof(a) / sizeof(a[0]));return 0;
}三.插入排序InsertSort
1.插入排序的核心思想
将待排序数据分为两部分一部分无序一部分有序将无序元素依次插入到有序中去完成排序
2.插入排序的适用场合
1.元素很少的时候元素小于16时就认为元素很少
2.每个元素在排序前的位置距排好序的最终位置不远的时候
3.插入排序的实现步骤
注意插入排序过程中没有交换
1.申请两个标记变量一个指向有序的最后一个另一个指向无序的第一个元素最开始时我们把数组第一个元素看成是有序的其他的元素是无序的所以最开始有序的标记变量指向的是数组的第一个元素无序的标记变量指向的是数组的第二个元素再申请一个临时变量临时变量用来存每一次要进行操作的无序元素防止无序的这个元素被覆盖
2.插入无序元素
1遍历无序的元素
2插入每一个无序的元素时进行倒叙遍历有序数组
如果遍历到的元素的值小于无序值那么无序值就放到当前元素的下一个位置上继续遍历无序的元素此时无序的标记变量向后移一位有序元素的标记指向的位置变为无序标记的指向的位置的前一位
如果遍历到的元素的值大于无序值那么当前元素后向右移一位继续倒叙遍历有序数组
如果遍历到了边界也就是数组的起始元素那么该无序元素变为有序元素的第一个继续倒叙遍历有序数组
4.插入排序的代码实现如下
#includeiostream
using namespace std;void InsertSort(int a[],int length) {int yesIndex 0;int noIndex 1;int temp a[noIndex];//依次插入无序while (noIndex length yesIndex-1) {if (yesIndex -1) {a[0] temp;noIndex;yesIndex noIndex - 1;temp a[noIndex];}if (a[yesIndex] temp) {a[yesIndex1] a[yesIndex];yesIndex--;}else {a[yesIndex1] temp;noIndex;yesIndex noIndex - 1;temp a[noIndex];}}}int main() {int a[] { 5,1,856,6,32,14,7,9,77 };InsertSort(a, sizeof(a) / sizeof(a[0]));for (int i 0; i sizeof(a) / sizeof(a[0]); i) {cout a[i] ;}return 0;
}四.希尔排序ShellSort也叫缩小增量排序
希尔排序可以理解成放大版的插入排序
1.希尔排序的实现步骤
1.定间隔造图时用的时二分实际生产应用中会和斐波那契数列有关系这里我们用二分来确定间隔
1初始定间隔:我们用数组的总长度除以2得到的结果向下取整然后我们以此结果作为间隔执行第二步
2重新定间隔:间隔变为间隔减半的结果向下取整这里除2了但是真正使用的时候不是除2的执行第二步
2.将数组中的元素根据间隔进行分组例如如果所得的间距为6那么下标为0的就和下标为6的一组下标为1的就和下标为7的一组
3.各组内进行插入排序
4.如果排序还没有完成的话(我们需要重新定间隔重新分组)从第一步的2重新开始
如果排序完成结束
2.希尔排序的时间复杂度
希尔排序的时间复杂度是无法计算的一般会有一个范围在n的1.2次方到n的1.5次方我们一般取n的1.3次方
五.计数排序CountingSort
1.计数排序的核心思想
核心思想基于非比较
2.计数排序的使用场合
数据是有范围的分配比较密集数据重复出现次数比较多
3.计数排序的实现步骤
1.先遍历一遍数组找到该数组的最大值和最小值
2.申请一个计数数组它的长度是上一步找的最大值和最小值的差值1并将计数数组所有元素初始化为0
3.遍历原数组进行计数
遍历到的每一个元素的值减去步骤1中获得的最小值作为计数数组的下标然后计数数组的对应下标进行1操作以此实现计数
4.放回操作
遍历计数数组当遍历到的计数数组的元素不为0时将当前元素所在的下标加上步骤1中获得的最小值得到的值依次放回到原数组中覆盖操作
4.计数排序的代码如下
#includeiostreamusing namespace std;void CountingSort(int a[],int length) {//找到最大值和最小值int min a[0];int max a[0];for (int i 0; i length; i) {if (min a[i]) {min a[i];}if (max a[i]) {max a[i];}}//申请array数组用来计数int* array (int*)malloc(sizeof(int) * (max - min 1));memset(array, 0, sizeof(int)*(max - min1));//用array数组进行计数for (int i 0; i length; i) {array[a[i] - min];}//开始排序,放回int t 0;for (int i 0; i max - min 1 ; i) {while (array[i]) {a[t] i min;t;array[i]--;}}
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {cout a[i] ;}cout endl;
}int main() {int a[] { 2,9,4,1,8,9,3,1,4,7,6,9,4 };CountingSort(a, sizeof(a) / sizeof(a[0]));Print(a, sizeof(a) / sizeof(a[0]));return 0;
}5.计数排序的优化
1.为什么要进行优化
因为如果元素是结构体的话比如学生这个结构体包括学生分数学生姓名学号等等那么我们没进行优化之前只能把学生分数进行排序那么就会出现信息不匹配的问题所以我们要进行优化优化的方法就是再申请一个数组在这个数组中进行排序此数组复制了一份原来数组中的元素然后将排好序的元素放回到原数组中
2.优化的计数排序实现的步骤
1.先遍历一遍数组找到该数组的最大值和最小值
2.申请一个计数数组它的长度是上一步找的最大值和最小值的差值1并将计数数组所有元素初始化为0
3.遍历原数组进行计数
遍历到的每一个元素的值减去步骤1中获得的最小值作为计数数组的下标然后计数数组的对应下标进行1操作以此实现计数
4.遍历一遍计数数组计算名次
计数数组中的每一个元素都跟前一个元素相加依次来得到名次 同分并列的记录的名次是最后一次出现的名次
5.申请一个新数组在这个新数组中进行排序
倒叙遍历原数组遍历到的每一个元素减去第一步中的最小值获得的值以找到每一个元素在计数数组中的位置然后获得该元素的名次从而找到它在新数组中的位置最后复制这个元素到该位置注意每次获得名次后该名次应进行减1操作为了下一次有相同值的元素能够继续成功排序
6.排好序的元素放回到原数组中
7.释放申请的空间
3.优化的计数排序的代码如下
#includeiostream
using namespace std;void CountingSort(int a[],int length) {//找到最大值和最小值int min a[0];int max a[0];for (int i 0; i length; i) {if (min a[i]) {min a[i];}if (max a[i]) {max a[i];}}//申请array数组用来计数int* array (int*)malloc(sizeof(int) * (max - min 1));memset(array, 0, sizeof(int)*(max - min1));//用array数组进行计数for (int i 0; i length; i) {array[a[i] - min];}//排名次for (int i 1; i max - min 1; i) {array[i] array[i - 1];}//申请一个新空间int* Temp (int*)malloc(sizeof(int) * length);memset(Temp, 0, sizeof(int) * (max - min 1));//倒叙遍历原数组进行排序for (int i length - 1; i 0; i--) {Temp[array[a[i] - min] - 1] a[i];array[a[i] - min]--;}//放回for (int i 0; i length; i) {a[i] Temp[i];}//释放free(Temp);Temp NULL;free(array);array NULL;
}int main() {int a[] { 2,9,4,1,8,9,3,1,4,7,6,9,4 };CountingSort(a, sizeof(a) / sizeof(a[0]));for (int i 0; i sizeof(a) / sizeof(a[0]); i) {cout a[i] ;}return 0;
}六.快速排序QuickSort
1.快速排序的核心思想
找一个标准值将比标准值小的都放在其左侧比标准值大的都放在其右侧根据标准值将数据分割成两部分两部分分别重复以上操作
2.快速排序实现的方法是挖坑填补法
操作步骤如下
1.选定标准值标准值在某些算法里也叫枢轴然后保存一下标准值此处变为坑注意这里我们选择数组的首元素作为标准值
2.从右向左找比标准值小的找到填入到前面的坑中此处变为坑
从左向右找比标准值大的找到之后填到后面的坑中此处变为坑
直到从右向左和从左向右相遇的时候此操作结束此位置就是标准值的位置放入标准值
3.根据标准值的部分将这组数据分为两部分左部分从起始位置到标准值左边的位置右部分从标识值右边的位置到结束位置然后将这两部分重新进行操作注意如果某一部分只有一个元素或者没有元素那么就不用进行操作了因为如果只有一个元素那它一定是有序的而如果没有元素那就根本不需要进行排序
3.快速排序的代码如下
#includeiostream
using namespace std;int Sort(int arr[],int begin, int end) {int temp arr[begin];while (begin end) {//从右向左找比标记值小的元素while (begin end) {if (arr[end] temp) {//填入左侧坑arr[begin] arr[end];begin;break;}end--;}//从左向右找比标记值大的元素while (begin end) {if (arr[begin] temp) {//填入右侧坑arr[end] arr[begin];end--;break;}begin;}}//将标准值放入arr[begin] temp;return begin;}void QuickSort(int arr[], int begin, int end) {if (arr NULL || begin end) return;//标准值int standard;standard Sort(arr, begin, end);//拆分QuickSort(arr, begin, standard - 1);QuickSort(arr, standard 1, end);
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {cout a[i] ;}cout endl;
}int main() {int a[] { 5,6,9,74,5,2,3,84,39,6,21,65,1,77 };int begin 0;int end sizeof(a) / sizeof(a[0]);QuickSort(a, begin, end - 1);//遍历Print(a, sizeof(a) / sizeof(a[0]));return 0;
}
4.快速排序的另一种实现方法区间分割法
1.此方法的好处
较于挖空填补法能够使程序编译期的所用时间变短
2.此方法的操作步骤如下
1.选定标准值标准值在某些算法里也叫枢轴然后保存一下标准值注意这里我们选择数组的尾元素作为标准值
2.申请一个小空间变量存的是小于标准值元素小空间的最后的那个下标最开始的值是起始位置-1所得到的值
3.从小空间最后的那个下标的下一个元素遍历如果遍历到的元素比标准值小的话那么元素与小空间最后的那个元素的下一个元素进行交换小空间变量进行1操作当遍历完所有元素除最后的那个元素之后最后的那个元素标准值与小空间最后的那个元素的下一个元素进行交换小空间变量进行1操作
4.根据标准值的部分将这组数据分为两部分左部分从起始位置到标准值左边的位置右部分从标识值右边的位置到结束位置然后将这两部分重新进行操作注意如果某一部分只有一个元素或者没有元素那么就不用进行操作了因为如果只有一个元素那它一定是有序的而如果没有元素那就根本不需要进行排序
3.此方法代码如下
#includeiostream
using namespace std;int Sort(int arr[], int begin, int end) {int small begin - 1;//遍历for (begin; begin end; begin) {//比较if (arr[begin] arr[end]) {//小区间扩张if (small ! begin) {arr[small] arr[small] ^ arr[begin];arr[begin] arr[small] ^ arr[begin];arr[small] arr[small] ^ arr[begin];}}}//放入if (small ! end) {arr[small] arr[small] ^ arr[end];arr[end] arr[small] ^ arr[end];arr[small] arr[small] ^ arr[end];}return small;
}void QuickSort(int arr[], int begin, int end) {if (arr NULL || begin end) return;//标准值int standard;standard Sort(arr, begin, end);//拆分QuickSort(arr, begin, standard - 1);QuickSort(arr, standard 1, end);
}int main() {int a[] { 5,6,9,74,5,2,3,84,39,6,21,65,1,77 };int begin 0;int end 14;QuickSort(a, begin, end - 1);//遍历for (int i 0; i 14; i) {cout a[i] ;}return 0;
}5.快速排序的的优化基于挖坑填补法和区间分割法的优化
1.标准值选取的优化
1.如何进行标准值的选取
方法一
3选1选起始位置中间位置结束位置然后找到三者中的中间值作为标准值
方法二适用于数据量大的
9选1选九个位置然后每三个再选一个中间值然后得到的这三个中间值作为一组再在其中选一个中间值作为标准值
2.针对于数据比较大且标准值重复率很高时使用的优化
1.如何进行优化
将标准值进行聚集
2.如何进行聚集
如果遍历到的元素的值和标准值一样大的话就放在最前面/最后面的位置上最后确定完标准值的位置之后将这些元素放到标准值左侧/右侧形成聚集
3.当数据元素分割到较少的时候使用插入排序元素16时认为元素较少
6.快速排序的再次优化
1.采用循环额外存储空间的方式取代快排时的递归
2.使用尾递归了解
7.数据有序对于快排来说是最坏的场合
七.归并排序MergeSort
1.归并排序的核心思想
将多个有序数组进行合并
2.归并排序的实现步骤
1.找到数组中间位置
2.根据中间位置进行拆分使其变成有序的
左半部分从起始部分到中间位置
右半部分从中间向右一位的位置到结束位置
注意某一部分中的元素只有一个时那这一部分就是有序的
3.将两个有序的部分合并
注意这里我们会申请数组进行元素的处理当全部处理完成后我们把处理完的元素放入到原数组中
1从头开始遍历两个部分进行比较谁小谁先放进申请的数组中
2当有一个部分遍历完成后看另外一部分是否遍历完成没完成就将还没遍历的部分放进数组中
3把在申请的数组中处理完的元素放入到原数组中
3.代码如下
#includestdio.h
#includestdlib.h
#includestring.h
void Sort(int arr[],int res[],int begin, int end) {if (begin end) {res[0] arr[begin];return;}int mid (begin end) 1;int* res1 (int*)malloc(sizeof(int) * (mid - begin 1));memset(res1, 0, sizeof(int) * (mid - begin 1));int* res2 (int*)malloc(sizeof(int) * (end - mid));memset(res1, 0, sizeof(int) * (end - mid));Sort(arr, res1, begin, mid);Sort(arr, res2, mid1, end);//合并int i 0;int index1 0;int index2 0;int mid1 mid;while (begin mid1 end mid 1) {if (res1[index1] res2[index2]) {res[i] res1[index1];i;begin;index1;}else {res[i] res2[index2];i;mid;index2;}}if (begin mid1) {for (int j index2; j end-mid11; j) {res[i] res2[j];i;}}if (mid 1 end) {for (int j index1; j mid1; j) {res[i] res1[j];i;}}//释放空间free(res1);free(res2);
}void MergeSort(int arr[],int begin,int end) {if (arr NULL||begin end) return;//申请一个数组int* a (int*)malloc(sizeof(int) * (end - begin 1));memset(a, 0, sizeof(int) * (end - begin 1));//排序Sort(arr,a,begin,end);for (int i begin; i end; i) {arr[i] a[i];}free(a);
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {printf(%d , a[i]);}printf(\n);
}int main() {int a[] { 1,57,56,3,23,4,65,123,19,46,88,5};int begin 0;int end sizeof(a) / sizeof(a[0]);MergeSort(a, begin, end-1);Print(a, end);return 0;
}八.堆排序HeapSort
1.堆排序的功能
堆排序可以动态维护一组数据内的最值
2.堆的分类
1.大顶堆
定义
在整棵二叉树中父亲和左右孩子三者中父亲都是最大值就被称为大顶堆
2.小顶堆
定义
在整棵二叉树中父亲和左右孩子三者中父亲都是最小值就被称为小顶堆
3.堆排序的实现步骤
注意
堆排序中我们用到了完全二叉树的一些逻辑一颗完全二叉树按照从上到下从左至右从0开始编号0~n-1)编号为i的节点
如果满足2*i1n-1则其有左孩子否则没有
如果满足2*i2n-1则其有右孩子否则没有
父亲节点的编号是0~2分之n-1
操作步骤
1.建初始堆这里建大堆
从数组的n/2-1到0依次调整各个父亲节点
每个父亲节点调整的方式看父亲节点和左右孩子中的最大值进行比较如果比最大值小的话父亲节点的值就和左右孩子中那个较大的那个进行交换然后那个进行交换的孩子节点变为新的父亲节点继续讨论如果新的父亲节点没有左右孩子或者没有发生交换那么结束
2.进行排序
1堆顶元素与末尾元素进行交换
2调整堆顶
调整堆顶的方式和上面的调整方式相同
4.堆排序的代码如下
#includestdio.hvoid adjust(int arr[], int index, int length) {if (index * 2 1 length index * 2 2 length) {return;}int weizhi 0;//看当前节点左孩子和右孩子取它们大的那个int Max 0;//如果有左孩子和右孩子if (index * 2 1 length index * 2 2 length) {if (arr[index * 2 1] arr[index * 2 2]) {Max arr[index * 2 1];weizhi index * 2 1;}else {Max arr[index * 2 2];weizhi index * 2 2;}}//如果只有左孩子if (index * 2 1 length index * 2 2 length) {Max arr[index * 2 1];weizhi index * 2 1;}//看这个值是否比当前节点大大的话进行交换然后讨论交换的那个节点if (Max arr[index]) {arr[index] arr[index] ^ arr[weizhi];arr[weizhi] arr[index] ^ arr[weizhi];arr[index] arr[index] ^ arr[weizhi];adjust(arr, weizhi, length);}}void HeapSort(int arr[],int length) {if (arr NULL || length 0) return;//1.建初始堆for (int i length / 2 - 1; i 0 ; i--) {adjust(arr, i, length);}//2.排序for (int i length-1; i 0; i--) {//进行交换arr[0] arr[0] ^ arr[i];arr[i] arr[0] ^ arr[i];arr[0] arr[0] ^ arr[i];adjust(arr, 0, i );}
}void Print(int a[], int length) {if (a NULL || length 0) return;for (int i 0; i length; i) {printf(%d , a[i]);}printf(\n);
}int main() {int arr[] { 4, 6, 2, 1, 8, 78, 2123, 48, 49, 58, 11, 9 };int length sizeof(arr) / sizeof(arr[0]);HeapSort(arr, length);Print(arr, length);return 0;
}九.桶排序BucketSort
1.桶排序的实现步骤
1.找到这组数据的最大值和最小值
2.确定分组方式
3.申请一个指针数组
4.进行入组头插法放入节点
5.组内进行排序其实是进行单向链表的排序可以使用冒泡排序选择排序插入排序创建链表时使用快速排序归并排序
6.放回到原数组中
7.释放
十.基数排序RadixSort
1.基数排序分为两种
1.MSD高位优先
2.LSD 低位优先
2.基数排序的实现步骤
1.找到这组数据中的最大值
2.计算最大值的位数
3.按位处理这是个循环循环的次数取决于位数这里用的是LSD
1申请组申请10组因为十进制是0~9
2拆位第一次是个位然后十位然后百位…
3数据进行入组操作数据根据 当前拆位个位十位百位等的值进行分组
4将数据放回到原数组中
5释放申请组的空间
十一.关于排序的时间复杂度空间复杂度稳定性
1.排序稳定性
1.稳定性的概念
数值相同的元素在排序前后其相对位置未发生改变
2.关于排序的时间复杂度空间复杂度稳定性的表格如下
