免费网站建设步骤,定制虚拟偶像app,WordPress留言提取,学校网站怎么做的好坏排序算法可以分为内部排序和外部排序#xff0c;内部排序是数据记录在内存中进行排序#xff0c;而外部排序是因排序的数据很大#xff0c;一次不能容纳全部的排序记录#xff0c;在排序过程中需要访问外存
内部排序算法有#xff1a;直接插入排序#xff0c;折半插入排…排序算法可以分为内部排序和外部排序内部排序是数据记录在内存中进行排序而外部排序是因排序的数据很大一次不能容纳全部的排序记录在排序过程中需要访问外存
内部排序算法有直接插入排序折半插入排序希尔排序选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。详细如何划分在文章中的叙述会有体现字母为大类排序方法。
本文将依次介绍上述排序算法。
A、插入排序
一、直接插入排序。
直接插入排序是一种最简单直观的排序算法它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。 算法步骤
1将第一待排序序列第一个元素看做一个有序序列把第二个元素到最后一个元素当成是未排序序列。
2从头到尾依次扫描未排序序列将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等则将待插入元素插入到相等元素的后面。
代码实现
void insert_sort(int array[],unsignedint n)
{int i,j;int temp;for(i 1;i n;i){temp array[i];for(j i;j 0 array[j - 1] temp;j--){array[j] array[j - 1];}array[j] temp;}
} 适用情况
直接插入排序适用于顺序存储和链式存储的线性表。当为链式存储时可以从前往后查照指定元素的位置。注意大部分排序算法都仅适用于顺序存储的线性表。是一个稳定的排序方法
二、折半插入排序
在直接插入排序的基础上得出折半插入排序。将直接插入排序的比较和移动分离。
算法步骤
与直接插入排序类似在此就不再叙述。
代码实现
void binary_insertion_sort(int arr[], int len)
{int i, j, temp, m, low, high;for (i 1; i len; i){temp arr[i];low 0; high i-1;while (low high){m (low high) / 2;if(arr[m] temp)high m-1;elselow m1;}}for (j i-1; jhigh1; j--)arr[j1] arr[j];arr[j1] temp;
}排序过程 适用情况
适用于顺序存储的线性表是稳定的排序。
三、希尔排序
也称递减增量排序方法是插入排序的一种更高效的改进版本。但希尔排序是非稳定的排序。其基本思想先将整个待排序的记录序列分割成若干子序列并分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行依次直接插入排序。
算法步骤
先取一个小于n的步长d1把表中全部记录分成d1个组所有距离为d1的倍数的记录放在同一个分组中在各分组中进行直接插入排序然后取第二个步长d2d1,重复上述过程直到所取的dt1即所有记录都放在同一分组里再进行直接插入排序由于此时已经具有较好的局部有序性故很快得到最终结果。到目前为止尚未求得一个最好的增量序列希尔提出的方法是d1n/2d11di/2向下取并且最后一个增量等于1。
代码实现
#includestdio.h
#includemath.h#define MAXNUM 10void main()
{void shellSort(int array[],int n,int t);//t为排序趟数int array[MAXNUM],i;for(i 0;i MAXNUM;i)scanf(%d,array[i]);shellSort(array,MAXNUM,int(log(MAXNUM 1) / log(2)));//排序趟数应为log2(n1)的整数部分for(i 0;i MAXNUM;i)printf(%d ,array[i]);printf(\n);
}//根据当前增量进行插入排序
void shellInsert(int array[],int n,int dk)
{int i,j,temp;for(i dk;i n;i)//分别向每组的有序区域插入{temp array[i];for(j i-dk;(j i % dk) array[j] temp;j - dk)//比较与记录后移同时进行array[j dk] array[j];if(j ! i - dk)array[j dk] temp;//插入}
}//计算Hibbard增量
int dkHibbard(int t,int k)
{return int(pow(2,t - k 1) - 1);
}//希尔排序
void shellSort(int array[],int n,int t)
{void shellInsert(int array[],int n,int dk);int i;for(i 1;i t;i)shellInsert(array,n,dkHibbard(t,i));
}//此写法便于理解实际应用时应将上述三个函数写成一个函数。 适用情况
仅适用于当线性表为顺序存储的情况非稳定排序。 希尔排序举例
待排序数组 {6, 5, 3, 1, 8, 7, 2, 4, 9, 0} 第一次步长h4, 那么数组按照步长可以拆分成4个小数组[0]6的意思是下标[0]的值为6 {[0]6, [4]8, [8]9} {[1]5, [5]7, [9]0} {[2]3, [6]2} {[3]1, [7]4} 对这4个小数组分别进行插入排序后4个小数组变成 {[0]6, [4]8, [8]9} {[1]0, [5]5, [9]7} {[2]2, [6]3} {[3]1, [7]4} 合并起来就是{6, 0, 2, 1, 8, 5, 3, 4, 9, 7} 第二次步长h1, 那么数组按照步长只有1个数组了 {6, 0, 2, 1, 8, 5, 3, 4, 9, 7} 对这个数组进行一次插入排序后最终顺序就成为 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
B、交换排序
基于交换排序的排序方法有很多主要并且常见的是冒泡排序和快速排序。
一、冒泡排序
也是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤
1比较相邻的元素。如果第一个比第二个大就交换他们两个。
2对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。
3针对所有的元素重复以上的步骤除了最后一个。
4持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
代码实现
void bubble_sort(int a[], int n)
{int i, j, temp;for (j 0;j n - 1;j)for (i 0;i n - 1 - j;i){if(a[i] a[i 1]){temp a[i];a[i] a[i 1];a[i 1] temp;}}
} 适用情况
是一个稳定的排序方法最坏的情况下时间复杂度就是ON^2,平均时间复杂度ON^2)。
二、快速排序
是对冒泡排序的一种改进。其基本思想是基于分治法的在待排序表L[1...n]中任取一个元素pivot作为基准通过一趟排序将待排序表划分为独立的两部分L[1...K-1]和L[K1....n]使得L[1......K-1]中所有元素小于pivotL[k1....n]中所有元素大于或等于pivot则pivot放在了其最终位置L[K]上这个过程称作一趟快速排序。而后分别递归地对两个子表重复上述过程直至每部分内只有一个元素或空为止即所有元素放在了其最终位置。
算法步骤
1 从数列中挑出一个元素称为 “基准”pivot
2 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作。
3 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形是数列的大小是零或一也就是永远都已经被排序好了。虽然一直递归下去但是这个算法总会退出因为在每次的迭代iteration中它至少会把一个元素摆到它最后的位置去。
代码实现
void Qsort(int a[], int low, int high)
{if(low high){return;}int first low;int last high;int key a[first];/*用字表的第一个记录作为枢轴*/while(first last){while(first last a[last] key){--last;}a[first] a[last];/*将比第一个小的移到低端*/while(first last a[first] key){first;}a[last] a[first];
/*将比第一个大的移到高端*/}a[first] key;/*枢轴记录到位*/Qsort(a, low, first-1);Qsort(a, first1, high);
}
考研的数据结构的快排代码是以严版教材为准看自己总结的黑色笔记本。 适用情况
快速排序是不稳定的排序最好的情况下时间复杂度为Ο(n log n) 最差时为n^2。快速排序是所有内部排序算法中平均性能最优的排序算法。
C、选择排序
选择排序的基本思想是每一趟例如第i趟在后面n-i1(i1,2,3...n-1)个待排序元素中选取关键字最小的元素作为有序子序列的第i个元素直到第n-1趟做完待排序元素只剩下一个就不用再选了。
一、简单选择排序
是一种简单直观的排序方法
算法步骤
1.首先在未排序序列中找到最小大元素存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。
3.重复第2步直到所有元素均排序完毕。
代码实现
void select_sort(int *a,int n)
{register int i,j,min,t;for(i 0;i n-1;i){min i;//查找最小值for(j i 1;j n;j)if(a[min] a[j])min j;//交换if(min ! i){t a[min];a[min] a[i];a[i] t;}}
}
*register是做声明的为了提高效率。C语言允许将局部变量的值放在CPU中的寄存器中这种变量叫寄存器变量。定义这个变量适用于频繁使用某个变量以加快运行速度因为保存在寄存器中省去了从内存中调用要注意定义了这个变量后不能取地址就是不能使用符号 适用情况
是一种不稳定的排序算法时间复杂度是O(n^2)。
二、堆排序
是指利用“堆”这种数据结构所设计的一种排序方法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。其平均时间复杂度为Ο(nlogn) 。
算法步骤
1.创建一个堆H[0...n-1]
2.把堆首最大值和堆尾交换。建立小根堆 若把堆首最小值和堆尾交换则是建立大根堆。
详细n个结点的完全二叉树最后一个结点是第[n/2](向下取整个结点的孩子。对第[n/2](向下取整个结点为根的子树筛选对于大根堆若根结点的关键字小于左右子女中关键字较大者则交换使该子树成为堆。之后向前依次对各结点[n/2]-1~1)(n/2向下取整)为根的子树进行筛选看该结点值是否大于其左右子结点的值若不是将左右子结点中较大值与之交换交换后可能会破坏下一级的堆于是继续采用上述方法构造下一级的堆直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆。
代码实现
//array是待调整的堆数组i是待调整的数组元素的位置nlength是数组的长度
//本函数功能是根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength)
{int nChild;int nTemp;for(; 2 * i 1 nLength;i nChild){//子结点的位置2*父结点位置1nChild 2 * i 1;//得到子结点中较大的结点if(nChild nLength - 1 array[nChild 1] array[nChild]) nChild;//如果较大的子结点大于父结点那么把较大的子结点往上移动替换它的父结点if(array[i] array[nChild]){nTemp array[i];array[i] array[nChild];array[nChild] nTemp; }else break; //否则退出循环}
}
//堆排序算法
void HeapSort(int array[],int length)
{int i;//调整序列的前半部分元素调整完之后第一个元素是序列的最大的元素//length/2-1是最后一个非叶节点此处/为整除for(i length / 2 - 1;i 0;--i)HeapAdjust(array,i,length);//从最后一个元素开始对序列进行调整不断的缩小调整的范围直到第一个元素for(i length - 1;i 0;--i){//把第一个元素和当前的最后一个元素交换//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的array[i] array[0] ^ array[i];array[0] array[0] ^ array[i];array[i] array[0] ^ array[i];//不断缩小调整heap的范围每一次调整完毕保证第一个元素是当前序列的最大值HeapAdjust(array,0,i);}
} 适用情况
是一种不稳定的排序方法平均时间复杂度O(nlogn)。 *1.插入排序耗时主要在有序表中选择排序在无序表中。 2.看其算法步骤即可得出二者区别。 D、其他排序
一、归并排序
是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。
算法步骤
1. 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列
2. 设定两个指针最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
代码实现
#include stdlib.h
#include stdio.hvoid Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{int i startIndex, jmidIndex1, k startIndex;while(i ! midIndex 1 j ! endIndex 1){if(sourceArr[i] sourceArr[j])tempArr[k] sourceArr[j];elsetempArr[k] sourceArr[i];}while(i ! midIndex1)tempArr[k] sourceArr[i];while(j ! endIndex1)tempArr[k] sourceArr[j];for(i startIndex; i endIndex; i)sourceArr[i] tempArr[i];
}//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{int midIndex;if(startIndex endIndex){midIndex (startIndex endIndex) / 2;MergeSort(sourceArr, tempArr, startIndex, midIndex);MergeSort(sourceArr, tempArr, midIndex1, endIndex);Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);}
}适用情况
是一种稳定的排序方法时间复杂度未O(nlogn)。
二、基数排序
是一种很特别的排序方法它不是基于比较进行排序的而是采用多关键字排序思想即基于关键字各位的大小进行排序的借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先MSD排序和最低位优先LSD排序。
算法步骤
1.算出要排序的数中的最大位数设置一个定量的数组当作空桶子桶的容量即为前面算得的最大位数桶的序号为0~9十个位置。
2.对要排列的数据从个位开始根据其大小放入对应的序号的桶中按照从左往右从下往上的顺序例如:756个位是6所以在第一趟中放入序号为6的桶中。收集时也是同样的顺序。这样排序的结果为从小到大
3.一直进行第二步直到把所有的位数遍历完最后一次收集到的数据即是从小到大排好的顺序。
代码实现
int maxbit(int data[], int n) //辅助函数求数据的最大位数
{int d 1; //保存最大的位数int p 10;for(int i 0; i n; i){while(data[i] p){p * 10;d;}}return d;
}
void radixsort(int data[], int n) //基数排序
{int d maxbit(data, n);int *tmp newint[n];int *count newint[10]; //计数器int i, j, k;int radix 1;for(i 1; i d; i) //进行d次排序{for(j 0; j 10; j)count[j] 0; //每次分配前清空计数器for(j 0; j n; j){k (data[j] / radix) % 10; //统计每个桶中的记录数count[k];}for(j 1; j 10; j)count[j] count[j - 1] count[j]; //将tmp中的位置依次分配给每个桶for(j n - 1; j 0; j--) //将所有桶中记录依次收集到tmp中{k (data[j] / radix) % 10;tmp[count[k] - 1] data[j];count[k]--;}for(j 0; j n; j) //将临时数组的内容复制到data中data[j] tmp[j];radix radix * 10;}delete[]tmp;delete[]count;
} 详细的例题可以查看有关数据结构的参考书。
适用情况
稳定的排序方法时间复杂度为O(n)。
*缺点
1首先是空间复杂度比较高需要的额外开销大。排序有两个数组的空间开销一个存放待排序数组一个就是所谓的桶比如待排序值是从0到m-1那就需要m个桶这个桶数组就要至少m个空间。
2其次待排序的元素都要在一定的范围内等等。 总结
各种排序的稳定性时间复杂度、空间复杂度、稳定性总结如下图 不稳定的排序算法有快、希、选、堆------“快些选一堆”
注排序的稳定性是这样定义的
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
