长沙网站推广合作,百度网盘怎么找资源,wordpress滑动图片轮播,html5餐饮美食订餐微官网wap手机网站模板整站下载目录
1.内部排序
1.5选择排序
1.5.1简单选择排序
1.5.2树形选择排序
1.6堆排序
1.7归并排序
1.7.1递归归并
1.7.2非递归归并
1.8计数排序
1.9基数排序
常见内部排序的总结#xff1a; 1.内部排序
1.5选择排序 选择排序#xff08;Selection Sort#xff09;的基…目录
1.内部排序
1.5选择排序
1.5.1简单选择排序
1.5.2树形选择排序
1.6堆排序
1.7归并排序
1.7.1递归归并
1.7.2非递归归并
1.8计数排序
1.9基数排序
常见内部排序的总结 1.内部排序
1.5选择排序 选择排序Selection Sort的基本思想是每一趟在n-i1i12⋯n-1个记录中选取关键字最小的记录作为有序序列中第i个记录。其中最简单且为读者最熟悉的是简单选择排序Simple Selection Sort。 1.5.1简单选择排序 一趟简单选择排序的操作为通过n-i次关键字间的比较从n-i1个记录中选出关键字最小的记录并和第i1≤i≤n个记录交换之。 显然对L.r1..n中记录进行简单选择排序的算法为令i从1至n-1进行n-1趟选择操作容易看出简单选择排序过程中所需进行记录移动的操作次数较少其最小值为“0”最大值为3n-1。然而无论记录的初始排列如何所需进行的关键字间的比较次数相同均为nn-1/2。因此总的时间复杂度也是On^2。
具体过程太过于抽象我们来看看选择排序的动图加以理解 步骤及思路按照升序排序
1.设置外层循环将循环次数设置为0-n-2次因为我们还需要留出最后一个数进行比较
2.设置内层循环从当前下标的下一个元素开始寻找比这个元素小的元素
3.如果较小元素与参照元素下标不相同就进行交换
下面是代码实现
void SelectSort1(int* arr, int n)
{int i 0;for (i 0; i n - 1; i){int min i;int j 0;for (j i 1; j n; j){if (arr[j] arr[min]){min j;}}if (min ! i){int tmp arr[min];arr[min] arr[i];arr[i] tmp;}}
} 那么能否加以改进呢 从上述可见选择排序的主要操作是进行关键字间的比较因此改进简单选择排序应从如何减少“比较”出发考虑。显然在n个关键字中选出最小值至少进行n-1次比较然而继续在剩余的n-1个关键字中选择次小值就并非一定要进行n-2次比较若能利用前n-1次比较所得信息则可减少以后各趟选择排序中所用的比较次数。因此我们来介绍一下树形选择排序。
1.5.2树形选择排序 树形选择排序Tree Selection Sort又称锦标赛排序Tournament Sort是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较然后在其中[n/2]个较小者之间再进行两两比较如此重复直至选出最小关键字的记录为止这个过程可用一棵有n个叶子结点的完全二叉树表示。例如图10.9a中的二叉树表示从8个关键字中选出最小关键字的过程。8个叶子节点依次存放排序之前的8个关键字每个非终端结点中的关键字均等于其左、右孩子结点中较小的关键字则根结点中的关键字即为叶子节点中的最小关键字。在输出最小关键字之后根据关系的可传递性欲选出次小关键字仅需将叶子结点中的最小关键字13改为“最大值”然后从该叶子结点开始。和其左或右兄弟的关键字进行比紋修改从叶子节点到根的路径各个结点的关键字则根结点的关键字即为次小关键字。同理可依次选出从小到大的所有关键字参见图10.9b和c。由于含有n个叶子结点的完全二叉树的深度为[logn]1则在树形选择排序中除了最小关键字之外每选择一个次小关键字仅需进行[logn]次比较因此它的时间复杂度为O(nlogn)。但是这种排序方法尚有辅助存储空间较多、和“最大值”进行多余的比较等缺点。为了弥补威洛姆斯J.willioms在1964年提出了另一种形式的选择排序堆排序。
1.6堆排序 堆排序Heap Sort只需要一个记录大小的辅助空间每个待排序的记录仅占有一个存储空间。 什么是堆堆的定义如下n个元素的序列{k₁k₂…kₙ}当且仅当满足下关系时称之为堆。
若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树则堆的含义表明完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k₁,k₂,…, kn} 是堆则堆顶元素(或完全二叉树的根)必为序列中 n个元素的最小值(或最大值)。例如下列两个序列为堆对应的完全二叉树如图10.10所示。 若在输出堆顶的最小值之后使得剩余n-1个元素的序列重又建成一个堆则得到n个元素中的次小值。如此反复执行便能得到一个有序序列这个过程称之为堆排序。由此实现堆排序需要解决两个问题
(1)如何由一个无序序列建成一个堆?
(2)如何在输出堆顶元素之后调整剩余元素成为一个新的堆?
下面先讨论第二个问题。例如图10.11(a)是个堆假设输出堆顶元素之后以堆中最后一个元素替代之如图10.11(b)所示。此时根结点的左、右子树均为堆则仅需自上至下进行调整即可。首先以堆顶元素和其左、右子树根结点的值比较之由于右子树根结点的值小于左子树根结点的值且小于根结点的值则将27和97交换之由于97 替代了27之后破坏了右子树的“堆”则需进行和上述相同的调整直至叶子结点调整后的状态如图10.11(c)所示此时堆顶为 n-1个元素中的最小值。重复上述过程将堆顶元素27和堆中最后一个元素97 交换且调整得到如图10.11(d)所示新的堆。
我们称这个自堆顶至叶子的调整过程为“筛选”。
从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树则最后一个非终端结点是第[n/2]个元素由此“筛选”只需从第[n/2]个元素开始。例如图10.12(a)中的二叉树表示一个有8个元素的无序序列
{49,38,65,97,76,13,27,49}
则筛选从第 4个元素开始再于9749则交换之交换后的序列如图10.12b所示同理、在第3个元素65被筛选之后序列的状态如图10.12c所示由于第2个元素38不大于其左、右子树根的值则筛选后的序列不变。图10.12e所示 筛选根元素49之后建成的堆 步骤及思路按照升序排序
1.我们先来进行建堆的操作我们有两种方法可以选择向上建堆和向下建堆
2.然后我们可以定义end来代表数组最后一个元素的下标在end1的条件下设置循环
3.循环内部先交换数组第一个元素和最后一个元素因为第一个元素是堆中最大的元素将则个元素放到最后一个再重新建堆就可以形成升序数组重复这个过程就可以完成排序
向上和向下建堆
1.向上建堆传入孩子结点的下标根据父亲结点孩子结点-1/2我们将父亲结点与孩子结点进行比较如果父亲结点小于孩子结点交换他们将父亲结点作为新的孩子结点继续比较直到不再小于孩子结点为止。
2.向下建堆传入父亲结点的下标和数组的总元素个数根据左孩子结点父亲结点*21我们先将左孩子结点与右孩子结点的数据进行比较选出较大的孩子结点与父亲结点比较同样如果父亲结点小于孩子结点交换他们将孩子结点作为新的父亲结点继续比较直到不再小于孩子结点为止或是孩子结点的下标大于元素个数为止。
下面是代码实现
void AdjustUp(int* arr, int child)
{int parent (child - 1) / 2;while (child 0){if (arr[child] arr[parent]){swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
void AdjustDown(int* arr, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){swap(arr[parent], arr[child]);parent child;child parent * 2 1;}else{break;}}
}
//最坏onlogn
void HeapSort(int* arr, int n)
{int i 0;for (i 0; i n; i){AdjustUp(arr, i);}int end n - 1;while (end 0){//将最大值与最后一个交换一下end--继续排前面的元素swap(arr[0], arr[end]);AdjustDown(arr, end, 0);end--;}
}
堆排序对记录数较少的文件并不值得提倡但对n较大的文件还是很有效的因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上由此堆排序在最坏的情况下其时间的复杂度为O(nlogn),相对于快速排序来说这是堆排序的最大优点此外堆排序仅需一个记录大小供交换用的辅助空间。
1.7归并排序 归并排序(Merging Sort)是又一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。它的实现方法早已为读者所熟悉无论是顺序存储结构还是链表存储结构都可在(的时间量级上实现。利用归并的思想容易实现排序。 假设初始序列含有n个记录则可看成是n个有序的子序列每个子序列的长度为1然后两两归并得到 个长度为2 或1的有序子序列再两两归并……如此重复直至得到一个长度为n的有序序列为止这种排序方法称为2-路归并排序。例如图10.13为2-路归并排序的一个例子。 1.7.1递归归并
步骤及实现按照升序排序
1.先开辟一个与原数组所占空间相同的新数组建议使用malloc函数传入第一个元素下标left最后一个元素下标right
2.取数组的中间下标数mid调用递归将left和mid传入再次调用递归传入mid和right
3.类似于后序遍历先调用递归两次再进行归并将数组划分为begin和midmid1和end其中beginleftendrightbegin和mid作为第一个归并数组的begin1和end1mid1和end作为第二个归并数组的begin2和end2
4.在begin1end1begin2end2的条件下归并之后再分别合并
5.使用memcpy将排好序的数据拷贝回原数组
下面是代码实现
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;int end1 mid;int begin2 mid 1;int end2 right;int i left;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else if (arr[begin1] arr[begin2]){tmp[i] arr[begin2];}else{tmp[i] arr[begin1];tmp[i] arr[begin2];}}while (begin1 end1){tmp[i] arr[begin1];}while (begin2 end2){tmp[i] arr[begin2];}memcpy(arr left, tmp left, sizeof(int) * (right - left 1));
}
//N*logN
void MergeSort(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);return;}_MergeSort(arr, 0, n - 1,tmp);free(tmp);tmp NULL;
}
1.7.2非递归归并
步骤及思路按照升序排序
1.还是先开辟出一块空间与原数组空间大小相同做好拷贝排序好的数据的准备
2.设置一个gap使gap的初始值为1每次循环后*2这样就可以实现从小区间归并到大区间归并
3.设置内层循环设置两个归并数组的begin和end分别为i和igap-1igap和i2*gap-1,这里我们对边界值进行一些处理如果end1或者begin2越界就退出循环不进行拷贝如果是end2越界就修改为n-1再进行与递归归并相同的操作
4.将有序的数据拷贝回原数组
下面是代码实现
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc failed);return; }int gap 1;while (gap n){int i 0;for (i 0; i n; i 2 * gap){int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;int j i;//画图理解边界值的处理if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[j] arr[begin1];}else if (arr[begin1] arr[begin2]){tmp[j] arr[begin2];}else{tmp[j] arr[begin1];tmp[j] arr[begin2];}}while (begin1 end1){tmp[j] arr[begin1];}while (begin2 end2){tmp[j] arr[begin2];}memcpy(arr i , tmp i, sizeof(int) * (end2-i1));//这里排完数据就拷贝不要到时候一把梭哈}gap * 2;}free(tmp);tmp NULL;
}
1.8计数排序
步骤及思路按照升序排序
1.这里我们先遍历一遍数组选出最大值和最小值
2.通过最大值和最小值开辟出范围数组
3.再次遍历原数组采用相对映射将数组中的数据-最小值对应的下标这样新开辟的数组记录的是相对映射数据出现的次数
4.遍历新数组对原数组进行还原
下面是代码实现
void CountSort(int* arr, int n)
{int max arr[0];int min arr[0];int i 0;for (i 0; i n; i){if (arr[i] max){max arr[i];}if (arr[i] min){min arr[i];}}int range max - min 1;int* countA (int*)calloc(1,sizeof(int) * (range));if (countA NULL){perror(malloc failed);return;}for (i 0; i n; i){countA[(arr[i] - min)];}int j 0;for (i 0; i range; i){while (countA[i] 0){arr[j] i min;countA[i]--;}}free(countA);countA NULL;
}
1.9基数排序 基数排序Radix Sorting是和前面所述各类排序方法完全不相同的一种排序方法。 从前几节的讨论可见实现排序主要是通过关键字间的比较和移动记录这两种操作而实现基数排序不需要进行记录关键字间的比较。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
书上对于多关键字的排序介绍 有点抽象我们直接来看例子 步骤及实现
1.这里需要用到队列这一数据结构由于已经介绍过这里就直接引用我们建立一个队列数组队列数组的下标就代表每一次基数排序的关键字
2.先将队列数组初始化先统计数据分别入队列注意这里循环的次数是按照数据的最高位的位数来确定的使用collect和destribute分别来收集分发数据
3.按照最低位优先原则使用GetKey函数来获得数据指定位数的数字来入对应数字的队列
4.分发数据完成第一次基数排序重复这个过程
下面来看代码实现
int Getkey(int num, int index)
{int ret 0;while (index 0){ret num % 10;num / 10;index--;}return ret;
}
void Collect(Queue* quarr, int* arr, int index, int sz)
{int i 0;for (i 0; i sz; i){int judge Getkey(arr[i], index);QueuePush((quarr[judge]), arr[i]);}
}
void Destribute(Queue* quarr, int* arr, int sz)
{int i 0;for (i 0; i sz; i){int j 0;int put 0;for (j 0; j 10; j){if (!QueueEmpty(quarr[j])){put QueueFront(quarr[j]);QueuePop(quarr[j]);break;}}arr[i] put;}
}
//基数排序按个位十位百位分别入队列出队列循环排序
void RadixSort(int* arr, int n)
{Queue quarr[10];int i 0;for (i 0; i 10; i){QueueInit(quarr[i]);}for (i 1; i 3; i){Collect(quarr, arr, i, n);//统计数据分别入队列Destribute(quarr, arr, n);//按照队列标号从小到大依次出队列直到队列为空}for (i 0; i 10; i){QueueDestroy(quarr[i]);}
}
常见内部排序的总结 1从平均时间性能而言快速排序最佳其所需时间最省但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是在n较大时归并排序所需时间较堆排序省但它所需的辅助存储量最多。 2上表中的“简单排序”包括除希尔排序之外的所有插人排序起泡排序和简单选择排序其中以直接插入排序为最简单当序列中的记录“基本有序”或n值较小时它是最佳的排序方法因此常将它和其他的排序方法诸如快速排序、归并排序等结合在一起使用。 3基数排序的时间复杂度也可写成Od•n。因此它最适用于n值很大而关键宇较小的序列。若关键字也很大而序列中大多数记录的“最高位关键字”均不同则亦可先按“最高位关键字”不同将序列分成若干“小”的子序列而后进行直接插入排序。 4从方法的稳定性来比较基数排序是稳定的内排方法所有时间复杂度为On^2的简单排序法也是稳定的然而快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。一般来说排序过程中的“比较”是在“相邻的两个记录关键字”间进行的排序方法是稳定的。值得提出的是稳定性是由方法本身决定的对不稳定的排序方法而言不管其描述形式如何总能举出一个说明不稳定的实例来。反之对稳定的排序方法总能找到一种不引起不稳定的描述形式。由于大多数情况下排序是按记录的主关键字进行的则所用的排序方法是否稳定无关紧要。若排序按记录的次关键字进行则应根据问题所需慎重选择排序方法及其描述算法。 1.稳定的排序方法有冒泡排序直接插入排序归并排序其他都是不稳定的如选择排序525...........2会将2的顺序颠倒希尔排序相同数值的数据可能会被分到不同组堆排序堆顶元素会被换到数组末尾顺序颠倒快速排序key的元素会和left的元素交换有可能会颠倒顺序
2.在数组接近有序的时候这时最最有效的排序方法是直接插入排序快速排序会退化成O(n^2)
3.在空间复杂度中归并排序需要O(n)的辅助空间来用开辟新数组来拷贝排序好的数据快速排序需要一个栈空间如果对数组进行相对有序的划分时则需要logn的辅助空间而关键字为第一个元素或者为最后一个元素时则需要n的辅助空间其他排序方法都只需要单个辅助空间即可。
