网站调用wordpress,建设网站需要注册证书吗,万网域名解析,摄影设计说明模板目录 排序排序的相关概念冒泡排序插入排序选择排序堆排序快速排序归并排序 内排序和外排序非比较排序稳定性稳定性 完 排序
排序的相关概念
排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起… 目录 排序排序的相关概念冒泡排序插入排序选择排序堆排序快速排序归并排序 内排序和外排序非比较排序稳定性稳定性 完 排序
排序的相关概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 在接下来的学习过程中我们将会遇到许多排序算法这些排序算法各有各的优缺点也因此应用于不同的场景。
冒泡排序
冒泡排序将数组分为两个部分比较区和保护区。比较区负责存储将要比较的数据保护区负责存储已经排完序的数据。比较区的每轮比较将会从数组首元素开始接着将两两相邻元素进行比较从而将比较区的极值移至比较区末尾在比较区比完一轮后比较区的最后一个元素就会并入保护区随后进行下一轮比较。
如果某轮比较区的比较都是合法的符合相对大小则证明此时比较区已经有序不需要再进行比较比较区就会整体并入保护区。 思路明白之后写代码就不难了
typedef int SortData, * pSortData;bool compare(SortData val1, SortData val2)
{if (val1 val2)return true;elsereturn false;
}void Swap(pSortData p1, pSortData p2)
{SortData transitory *p1;*p1 *p2;*p2 transitory;
}void Bubble_sort(pSortData pArray, int Size)
{int i 0;int j 0;for (i 0; i Size - 1; i){bool falg true;for (j 0; j Size - i - 1; j){if (compare(pArray[j], pArray[j 1])){Swap(pArray[j], pArray[j 1]);falg false;}}if (falg)break;}
}为了提高排序算法对不同数据类型的适用性我们使用compare来定义比较元素的相对大小关系后续排序算法中若涉及到对元素的比较则全部通过调用该函数实现。另外考虑到后续算法可能经常遇到数据交换问题所以交换函数也专门写出。
为了对冒泡排序进行测试还需要定义一些外围函数。
pSortData BulidArray(int Size)
{pSortData pArray (pSortData)malloc(sizeof(SortData)* Size);if (pArray NULL){perror(BulidArray malloc fail);return NULL;}int circuit 0;for (; circuit Size; circuit){pArray[circuit] rand();}return pArray;
}void pArrayPrintf(pSortData pArray, int Size)
{int circuit 0;for (; circuit Size; circuit){printf(%d ,pArray[circuit]);}printf(\n);
}测试为了让程序以最优性能运行请将版本改为Release
void test1()
{int Size 10;pSortData pArray BulidArray(Size);int circuit 0;printf(The contents of the original array:\n);pArrayPrintf(pArray, Size);Bubble_sort(pArray, Size);printf(\nThe contents of the sorted array:\n);pArrayPrintf(pArray, Size);free(pArray);pArray NULL;
}int main()
{ srand((unsigned int)time(NULL));test1();return 0;
}可以看到测试是通过的。
后续还会对其它排序算法进行测试测试的大致思路都和test1()相同只不过调用的排序算法不同这就会使得test系列函数过于重复冗余。为此我们可以用宏定义的方式生成对应的排序算法测试函数。
#define PerformanceTesting(NumSize, Proceedings) \void test_##Proceedings() \{ \printf(The test begins.\n); \printf(The subroutine tested is #Proceedings .\n); \printf(The number of array members is #NumSize .\n); \srand((unsigned int)time(NULL)); \int Size NumSize; \pSortData pArray BulidArray(Size); \int circuit 0; \printf(\nThe contents of the original array:\n); \pArrayPrintf(pArray, Size); \clock_t begin clock(); \Proceedings(pArray, Size); \clock_t end clock(); \printf(\nThe contents of the sorted array:\n); \pArrayPrintf(pArray, Size); \free(pArray); \pArray NULL; \printf(\nEnd of test.\n); \printf(The #Proceedings runtime is %dms.\n, end-begin); \} 这个宏定义生成的测试函数将会打印测试的相关信息。clock()用于获取从程序启动到clock()执行的间隔时间单位为毫秒它的返回值为clock_t(long)类型两个clock_t一减就会粗略获得排序算法的运行时间。
PerformanceTesting(10, Bubble_sort)int main()
{ test_Bubble_sort();return 0;
}这里显示0毫秒是因为单位的精确度不够数组成员的个数过少可以换个数。
PerformanceTesting(10000, Bubble_sort)int main()
{ test_Bubble_sort();return 0;
}插入排序
插入排序的主题思想是将要排序的值依据相对大小关系插入到一个已经有序的结构中。由于单个元素是无法比较的所以单个成员就可以视为有序的结构所以插入排序最开始是将首元素作为那个有序结构随后在此基础上对剩余元素逐个插入。插入排序分为两种连续型和离散型。
我们先说连续型也叫直接插入排序。 实际代码与动图并不完全相同实际代码是将对比区的首元素临时拷贝一份这里的删除实际是覆写但为了更好理解动图忽略了这些细节。
当对比区首元素与保护区的元素逐个对比时会出现三种情况
符合排序规则那就将拷贝数据写入保护区对比元素之后不符合排序规则那就将保护区对比元素向后挪一位不符合排序规则且保护区里的元素全部都比完了就把拷贝数据写入保护区首元素
因此最初的代码大概是这样的
void Insert_sort(pSortData pArray, int Size)
{int compare_begin, protection_compare;SortData temporary_storage;for (compare_begin 1; compare_begin Size; compare_begin){temporary_storage pArray[compare_begin];for (protection_compare compare_begin - 1; protection_compare 0; protection_compare--){if (compare(pArray[protection_compare], temporary_storage)){pArray[protection_compare 1] pArray[protection_compare];}else{pArray[protection_compare 1] temporary_storage;break;}}if(protection_compare -1){pArray[protection_compare 1] temporary_storage;}}
}当遇到第一种情况时也就是符合规则的情况时由于循环是break出的所以protection_compare并不会改变因此后面的if(protection_compare -1)其实也不用写于是第一种和第三种情况就可以共用一份代码
void Insert_sort(pSortData pArray, int Size)
{int compare_begin, protection_compare;SortData temporary_storage;for (compare_begin 1; compare_begin Size; compare_begin){temporary_storage pArray[compare_begin];for (protection_compare compare_begin - 1; protection_compare 0; protection_compare--){if (compare(pArray[protection_compare], temporary_storage)){pArray[protection_compare 1] pArray[protection_compare];}else{break;}}pArray[protection_compare 1] temporary_storage;}
}让我们来测试一下
PerformanceTesting(10, Insert_sort)int main()
{ test_Insert_sort();return 0;
}直接插入排序的时间复杂度是标准的等差数列所以时间复杂度就不细说了就是 0 ( N 2 ) 0(N^2) 0(N2)。不过对于直接插入排序来说不太容易真的出现 N 2 N^2 N2级别的时间复杂度出现 N 2 N^2 N2级别的时间复杂度意味着每次比较都是第三种情况此时的数据其实就是逆序结构。比如在上面的例子中直接排序会把输入的数组转化为升序数组如果出现 N 2 N^2 N2级别的时间复杂度那就意味着输入的数组就是降序数组。
所以对于直接插入排序来说除了要知道我们通常说的最坏情况的时间复杂度之外还要知道最好情况的复杂度什么时候复杂度最好呢观看上面的动图你可以发现有些首元素被拷贝之后直接就被放回了原位如果每次比较都是这种情况那就是最好情况。此时直接插入排序的时间复杂度就为 O ( N ) O(N) O(N)和最坏情况一样这种级别的复杂度也很难遇到遇到这种级别的复杂度意味着输入的数组就是顺序数组。
虽然冒泡排序和直接插入排序的时间复杂度通常说的那个时间复杂度都是 O ( N 2 ) O(N^2) O(N2)但直接插入排序优于冒泡排序。设想这样一种场景现在需要将输入的数组转化为升序数组但恰巧数组第一个元素就是最大值很明显要把这个最大的元素移到最后一位。对于这种数组直接插入每轮比较都顺手把这个最大的值向后移动一位每轮比较都是有配合的而对于冒泡排序来说各轮比较像是各干各的每轮比较只负责把极值推到最后。 接下来我们学习离散式插入排序更多人将其称为希尔排序。
从前面的过程中我们可以看到无论是冒泡排序还是直接插入排序某个数据到达它应有的位置都必须一步一步地移动最起码在逻辑层面上数据都是连续移动的这正是“连续”的一种体现
有没有少走两步的方法呢当然是有的这就引申出了“预排序”的概念。预排序的目的是让数组接近有序大体上有序之后再进行一次直接插入排序从而减少直接插入排序的移动次数。
预排序的具体做法是将原先排序的数组分为独立的几个部分这几个独立数组中的成员在原先数组中并不是连续的而是相隔一定单位的随后在对这些独立的数组分别进行直接插入。
这里我们暂且将“一定单位”设为3。 经过预排序的数组相比未经过预排序的数组相比在进行直接插入排序时会出现更多每轮比较只进行一次的情况算法的时间复杂度将更加靠近 O ( N ) O(N) O(N)。
不过在实际代码中并不是真的把这一个数组分成独立的几个小数组。而是让下标由每次加一变成每次加一定单位。
void Shell_sort(pSortData pArray, int Size)
{//preorderint intervals 3;int initial, compare_begin, protection_compare;SortData replica;for (initial 0; initial intervals; initial){for (compare_begin initial intervals; compare_begin Size; compare_begin intervals){replica pArray[compare_begin];for (protection_compare compare_begin - intervals; protection_compare 0; protection_compare - intervals){if (compare(pArray[protection_compare], replica)){pArray[protection_compare intervals] pArray[protection_compare];}else{break;}}pArray[protection_compare intervals] replica;}}//direct
}不过更常用的是这种
void Shell_sort(pSortData pArray, int Size)
{//preorderint intervals 3;int initial, compare_begin, protection_compare;SortData replica;initial 0;for (compare_begin initial intervals; compare_begin Size; compare_begin){replica pArray[compare_begin];for (protection_compare compare_begin - intervals; protection_compare 0; protection_compare - intervals){if (compare(pArray[protection_compare], replica)){pArray[protection_compare intervals] pArray[protection_compare];}else{break;}}pArray[protection_compare intervals] replica;}//direct
}只用两层循环但实际还是一样的不同的是只有两层循环实际上是先把第一个独立数组比较一轮再把第二个独立数组比较一轮接着把第三个独立数组比较一轮然后再让第一个独立数组比较一轮······
三层循环则是先把第一个独立数组完全比完再去比较第二个独立数组和第三个独立数组。可以这样认为三层循环的代码是三个独立数组异步走而只有二层循环的代码是三个独立数组同步走。
它们效率实际上是完全一样的只不过两层循环看上去比三层循环更好看所以常见的还是用两层循环。
好的让我们先不写后续的直接插入直接先测试一下
PerformanceTesting(10, Shell_sort)int main()
{ test_Shell_sort();return 0;
}我们把intervals改成1试试 我们发现此时输出的数组就是有序的为什么呢因为间隔为1时每个独立数组其实就只有一个成员或者说间隔为1的时候独立数组只有一个那就是输入数组本身。也就是说直接插入排序或者说连续式插入排序其实就是希尔排序或者说离散式排序的一种特例它们之间是被包含与包含的关系。
或者也可以说间隔intervals决定了输出数组的有序度。intervals越大当然是合法的越大输出数组的有序度就越小而当intervals为1时输出数组就是完全有序的。
于是我们就可以改变intervals的值让数组进行多次希尔排序每次排序都可以被视为后一个排序的预排序最后让intervals等于1即可。intervals就用数组成员个数来初始化。
void Shell_sort(pSortData pArray, int Size)
{int intervals Size;int compare_begin, protection_compare, initial 0;SortData replica;while (intervals 1){intervals intervals / 3 1;for (compare_begin initial intervals; compare_begin Size; compare_begin){replica pArray[compare_begin];for (protection_compare compare_begin - intervals; protection_compare 0; protection_compare - intervals){if (compare(pArray[protection_compare], replica)){pArray[protection_compare intervals] pArray[protection_compare];}else{break;}}pArray[protection_compare intervals] replica;}}
}intervals在其中的迭代公式为intervals intervals / 3 1;它的思路是通过不断地整除三让intervals变小最终让intervals小于三此时加一就发挥了作用它会使得intervals最终变成一在执行完间隔为1的希尔排序后借由while (intervals 1)跳出循环完成排序。
有人可能会问while (intervals 1)能不能带等于号答案是不行的。
第一个原因不算致命问题。从代码中可以看出它的逻辑是先判断intervals再调整intervals然后再进行一次希尔排序。如果intervals已经为1了则意味着上一次希尔排序间隔就为1为什么还要再排一次呢
第二个原因是致命问题。当intervals为1之后它的值就永远为1了如果加上等号程序就会陷入死循环。
除此之外另一种主流的迭代公式为intervals intervals / 2;。这是什么思路呢数可以被分为奇数偶数如果intervals最初是偶数那intervals最终必会等于1然后由while (intervals 1)跳出循环如果intervals最初是奇数由于这里是整除所以和偶数是一样的。
希尔排序的间隔公式还有其它版本。只要你数学好能推导出满足要求的公式那就可以用。
PerformanceTesting(10, Shell_sort)int main()
{ test_Shell_sort();return 0;
}希尔排序的效率远高于直接插入排序。甚至可以直接与快排和堆排序一较高下。
下面我们来浅谈一下希尔排序的时间复杂度。为什么是浅谈呢因为我数学不好希尔排序的时间复杂度推导超出了我的数学知识水平。等我学了相关数学知识后再把没说的细节补上。 好的让我们先看最外层的循环也就是while (intervals 1)如果以intervals intervals / 3 1;来看的话复杂度就为 l o g 3 N log_3N log3N由于时间复杂度是粗略计算所以后面的那个“1”就忽略了。
从第二层循环开始这就超出了我的知识水平。由于intervals是在变化的所以非常难计算。我们只能粗略算一下怎么算呢
我们从intervals的两个极端入手。
当intervals很大时比如说 S i z e 3 \frac{Size}{3} 3Size此时粗略来讲将会有 S i z e 3 \frac{Size}{3} 3Size个独立数组每个数组有三个成员前面说过直接插入排序的时间复杂度是个标准的等差数列所以对于单个独立数组来说它的具体复杂度就是123等于6那有多少个独立数组呢一共有 S i z e 3 \frac{Size}{3} 3Size个独立数组所以此时的时间复杂度就为 S i z e 3 ∗ 6 2 S i z e \frac{Size}{3}*62Size 3Size∗62Size也就是说这是 O ( N ) O(N) O(N)级别的。
当intervals很小时经过前面的预排序之后此时原数组已经几乎是有序了。所以此时的复杂度就是前面说的最好情况O(N)。
所以说单从intervals的两个极端来说它的复杂度都是 O ( N ) O(N) O(N)。
据说当intervals又不大又不小的时候时间复杂度会增加。所以intervals从大到小其复杂度的变化过程应该是先上升再下降。
上面说的这些是让大家明白非常粗略地来讲即使是对复杂度来说也是过于粗略的不能真的作为复杂度的。它的复杂度是 O ( N ∗ l o g 2 N ) O(N*log_2N) O(N∗log2N)这个级别的复杂度差不多能赶上堆排序和快排了。所以说希尔排序的效率远远高于直接插入排序。
至于希尔排序的具体时间复杂度就不说了一方面是这和intervals的迭代公式有关另一方面这真的很难算。
那到底多少呢我也是听别人说的大概是 O ( N 1.25 ) O(N^{1.25}) O(N1.25)到 O ( 1.6 N 1.25 ) O(1.6N^{1.25}) O(1.6N1.25)。非要给具体值就是 O ( N 1.3 ) O(N^{1.3}) O(N1.3)。
选择排序
选择排序非常简单。但效率太低了。它的思想是从数组中找出一个极值把它放到应有的位置上然后从剩余部分再找极值依次类推。
我们稍微优化一下每轮比较把最大值和最小值都找出来。我们通过交换把这两个极值放在合适的位置上 大概是这个意思不得不说选择排序效率太低了我画图都画了很长时间画完没有细看是不是完全对的。
不过若是还这样写还不行
void Select_sort(pSortData pArray, int Size)
{int pend_begin, pend_end;int max, min, current;for (pend_begin 0, pend_end Size - 1; pend_begin pend_end; pend_begin, pend_end--){max pend_end;min pend_begin;for (current pend_begin; current pend_end 1; current){if (compare(pArray[current], pArray[max])){max current;}if (compare(pArray[min], pArray[current])){min current;}}Swap((pArray[pend_begin]), (pArray[min]));Swap((pArray[pend_end]), (pArray[max]));}
}在交换成员时有时会出现一种情况这种情况在动画中并没有体现出来。如果pend_begin恰好就和max相同时在进行第一次交换后原先选出的最大数就会跑到min的位置上从而出现问题。所以还要略微修改。
void Select_sort(pSortData pArray, int Size)
{int pend_begin, pend_end;int max, min, current;for (pend_begin 0, pend_end Size - 1; pend_begin pend_end; pend_begin, pend_end--){max pend_end;min pend_begin;for (current pend_begin; current pend_end 1; current){if (compare(pArray[current], pArray[max])){max current;}if (compare(pArray[min], pArray[current])){min current;}}Swap((pArray[pend_begin]), (pArray[min]));if (pend_begin max){max min;}Swap((pArray[pend_end]), (pArray[max]));}
}PerformanceTesting(10, Select_sort)int main()
{ test_Select_sort();return 0;
}堆排序
之前说过堆排序就在《二叉树和堆》那个项目下这里再简单地回顾一下。
堆排序利用的是堆根节点是堆中成员极值的性质。先将输入的数组通过调整算法调整为堆再把根节点数值与数组尾元素数值进行交换接着再把剩余部分调整为堆不断循环最后得出有序数组。
示意图在《二叉树和堆》文档中已经给出在此不做赘述。
static int FindFristChild(int parent, int Size)
{int child parent * 2 1;if (child Size){return child;}else{return -1;}
}static int FindSecondChild(int parent, int Size)
{int child parent * 2 2;if (child Size){return child;}else{return -1;}
}static void DownwardAdjustment(pSortData pArray, int Size, int start)
{int parent start;int child;while (parent Size){int first_child FindFristChild(parent, Size);int second_child FindSecondChild(parent, Size);if (first_child -1 second_child -1){break;}else{child first_child;if (second_child ! -1){if (compare(pArray[second_child], pArray[first_child])){child second_child;}}}if (compare(pArray[child], pArray[parent])){Swap((pArray[child]), (pArray[parent]));}parent child;}
}void Heap_sort(pSortData pArray, int Size)
{int parent ((Size - 1) - 1) / 2;for (; parent 0; parent--){DownwardAdjustment(pArray, Size, parent);}int end;for (end Size - 1; end 0; end--){Swap((pArray[0]), (pArray[end]));DownwardAdjustment(pArray, end, 0);}
}PerformanceTesting(10, Heap_sort)int main()
{ test_Heap_sort();return 0;
}快速排序
快速排序采用分治的思想。它先在待排数组中任取一成员作为基准值随后依据该值将数组分为两个子部分分别存放大于和小于基准值的成员随后再将这两个子部分视为新的待排数组重复上述步骤。
因为快速排序使用递归结构所以要先实现单轮排序。单轮排序一共有三种实现方式。
第一种Hoare法。Hoare正是快速排序的提出者此种方法也是快速排序的原生思路。
在Hoare法中默认选择待排序数组的第一个成员作为基准值随后创建两个指针最开始分别指向待排数组的第一个成员和最后一个成员为了方便叙述下面将这两个指针依据其相对方位分别命名为left和right;left的职责是寻找大于基准值的数而right于此正好相反这两个指针找到各自的目标后会对所指向的数组成员进行数值交换然后重复上述过程直到两个指针指向同一个数组成员这个成员所处的位置正是基准值应该处于的位置此时对该成员与数组第一个成员也就是基准值进行数值交换单轮排序就结束了。
这两个指针采取“异步”的方式寻找目标即某个指针比如A找到目标后再让另一个指针B寻找自己的目标在交换数值后另一个指针A再寻找目标。指针最初的移动顺序也有讲究。当要生成升序数组时由于基准值最后是通过与相遇位置成员进行数值交换才来到应有位置的而基准值又默认为第一个成员的数值所以必须要确保被基准值交换的成员数值是小于基准值的为此必须先让right指针先进行移动当left与right相遇时由于right先进行移动所以绝大多数情况下都是right先找到目标然后left在寻找自己对应目标的过程中与right相遇这意味这相遇位置的成员数值必然是小于基准值的。同理若将基准值设置为最后一个成员则必须先让left先走以确保相遇位置的数值大于基准值。也就是说两指针的移动顺序与基准值的位置有关。
除此之外另一种特殊情况先行指针在遍历完整个选中数组后仍没有找到目标此时两指针直接在基准值相遇但由于指针相遇位置与基准值位置相同所以数值交换不会产生有效影响。
对于和基准值相同的数值成员两指针不会进行任何响应不视为目标而是交由后续轮次排序处理。
以下动画展现的是基于Hoare法单轮排序的整体过程而非单轮排序过程。 static int Hoare_mode(pSortData pArray, int left, int right)
{int key left;while (left right){while (left right !compare(pArray[key], pArray[right])){right--;}while (left right !compare(pArray[left], pArray[key])){left;}Swap((pArray[left]), (pArray[right]));}Swap((pArray[right]), (pArray[key]));return right;
}tatic void _Quick_sort_root(pSortData pArray, int left, int right)
{if (left right)return;int key Hoare_mode(pArray, left, right);_Quick_sort_root(pArray, left, key - 1);_Quick_sort_root(pArray, key 1, right);
}void Quick_sort(pSortData pArray, int Size)
{_Quick_sort_root(pArray, 0, Size - 1);
}在实际写代码时要特别注意两指针找目标的循环条件。前面的left right防止跑出数组后面的大小比较一定要带等于号试想一下这种情况当数组中除基准值时还含有两个和基准值相同的成员而指针循环条件没带等号时
while (left right pArray[right] pArray[key])
{right--;
}
while (left right pArray[key] pArray[left])
{left;
}这两个指针就会把与基准值相等的那两个值分别选为目标交换之后两个指针的指向内容依旧与基准值相等所以依旧不会进入循环两指针不会发生变化于是它们就会再交换一下于是就死循环了。
erformanceTesting(10, Quick_sort)int main()
{ test_Quick_sort();return 0;
}第二种填坑法。
从上面的学习中可以看到霍尔法有很多坑于是就有人以霍尔法的思想为指导创造出了填坑法。
填坑法与霍尔法的主要区别就是数据的传递方式的不同。霍尔法的数据传递方式是交换而填坑法的数据传递是覆写。
和霍尔法类似我们先默认基准值是数组第一个成员。在确定基准值之后对基准值进行拷贝由于拥有备份所以基准值在数组中的原位置就可以随意处理了此时它就变成了一个坑可以写入数组中的其它数据。然后就要寻找填入坑的数据由于坑最开始位于数组的第一个成员处所以想要找数据自然是要从数组最后一个成员处开始寻找。于是right指针就登场了它会寻找比基准值小的数找到之后就把自己指向的数据写入坑里此时right指向的数据也有了拷贝于是right就成为了新的坑有新的坑就要寻找新的数据由于此时的坑在右侧所以想要找新的数据自然是要从数组左侧开始找起于是left就登场了它会寻找大于基准值的数据找到之后填入坑里于是它指向的地方就成为了新坑right就会找数据用来填入新坑重复上述过程当两指针相遇后它们指向的位置就是基准值应处于的位置于是把之前拷贝的基准值写入这个位置。 static int FillGap_mode(pSortData pArray, int left, int right)
{SortData key pArray[left];int gap left;while (left right){while (left right !compare(key, pArray[right])){right--;}pArray[gap] pArray[right];gap right;while (left right !compare(pArray[left], key)){left;}pArray[gap] pArray[left];gap left;}pArray[gap] key;return gap;
}static void _Quick_sort_root(pSortData pArray, int left, int right)
{if (left right)return;int key FillGap_mode(pArray, left, right);_Quick_sort_root(pArray, left, key - 1);_Quick_sort_root(pArray, key 1, right);
}void Quick_sort(pSortData pArray, int Size)
{_Quick_sort_root(pArray, 0, Size - 1);
}当然此时仍需要注意循环变量的等于号。
PerformanceTesting(100000, Quick_sort)int main()
{ test_Quick_sort();return 0;
}第三种方法没有统一的命名依据思路要不叫它“跟屁虫法”或者“搜索法”
在搜索法中同样有两个指针一个指针负责搜索目标另一个指针负责尾随前一个指针。还是以数组首元素为基准值搜索指针会寻找比基准值小的数据找到一个尾随指针就会向后移动一位然后这两个指针指向的内存块就会交换数值当搜索指针跑出数组后尾随指针指向的内存块就会和基准值交换。 static int Search_mode(pSortData pArray, int left, int right)
{int key left;int prev left;int curr left;while (curr right){if (compare(pArray[key], pArray[curr])){Swap((pArray[prev]), (pArray[curr]));}curr;}Swap((pArray[prev]), (pArray[key]));return prev;
}static void _Quick_sort_root(pSortData pArray, int left, int right)
{if (left right)return;int key Search_mode(pArray, left, right);_Quick_sort_root(pArray, left, key - 1);_Quick_sort_root(pArray, key 1, right);
}void Quick_sort(pSortData pArray, int Size)
{_Quick_sort_root(pArray, 0, Size - 1);
}PerformanceTesting(100000, Quick_sort)int main()
{ test_Quick_sort();return 0;
}也还可以优化优化
static int Search_mode(pSortData pArray, int left, int right)
{int key left;int prev left;int curr left;while (curr right){if (compare(pArray[key], pArray[curr]) prev ! cur){Swap((pArray[prev]), (pArray[curr]));}curr;}Swap((pArray[prev]), (pArray[key]));return prev;
}就是加加后还等于搜索指针就不交换了。其实优不化优化都行的。 接下来我们看看快速排序的时间复杂度当基准值恰好为选中数组的中位数时快速排序效率达到最高此时快速排序的结构与二叉树类似 每个节点就可以被视为一个函数栈帧一共有 l o g 2 N log_2N log2N层每一层所选中数组部分合在一块就相等于整个数组所以每层都是 N N N再乘一下于是就得到时间复杂度 O ( N ∗ l o g 2 N ) O(N*log_2N) O(N∗log2N)。
最坏情况是什么呢那就是每次选中的基准值都恰好是极值此时的函数栈帧更像是链表而非树每层的复杂度仍是 N N N但此时深度已经变成了 N N N所以复杂度就变成了 O ( N 2 ) O(N^2) O(N2)。
前面说过基准值实际是可以任意选择的所以为了避免出现最坏情况就可以对快速排序进一步优化
我们先挑出三个预选值分别是数组末尾开头中间然后选择中间的那一个。但如果直接在单轮排序上修改就太麻烦了所以我们的实际操作是先把三个数中间的那个数找出来然后让它与数组首元素进行数值交换。
int middle_of_three(pSortData pArray, int left, int right)
{int mid (left right) / 2;if (compare(pArray[left], pArray[mid])){if (compare(pArray[mid], pArray[right])){return mid;}else{if (compare(pArray[left], pArray[right])){return right;}elsereturn left;}}else{if (compare(pArray[right], pArray[mid])){return mid;}else{if (compare(pArray[left], pArray[right])){return left;}elsereturn right;}}
}为了观察三数选中的效果我们先修改一下数组构建函数
pSortData BulidArray(int Size)
{pSortData pArray (pSortData)malloc(sizeof(SortData) * Size);if (pArray NULL){perror(BulidArray malloc fail);return NULL;}int circuit 0;for (; circuit Size; circuit){pArray[circuit] circuit;}return pArray;
}现在单次排序没有三数选中让我们看看效率
PerformanceTesting(100000, Quick_sort)int main()
{ test_Quick_sort();return 0;
}看样子是函数栈帧层数过多栈溢出了。
换一下
PerformanceTesting(3000, Quick_sort)int main()
{ test_Quick_sort();return 0;
}现在加上三数选中再来一次。 差别不是很明显这应该是我电脑性能不行参数设大一些就栈溢出了理论上来说参数越大差别就应该越明显。等会以非递归实现快排之后再试一试。 刚刚我们就看到了递归的缺点当递归过深后就容易出现栈溢出所以接下来我们要以非递归的方式实现快速排序。
先让我们想一想当初为什么偏要用递归的方式去实现快排。其实很简单就是利用递归把函数栈帧以树状的形式组织起来然后用单轮排序返回的下标值把它们联系起来。
还是回到霍尔法以动图中的数组[ 6,1,2,7,9,3,4,7,10,8 ]为例。图中蓝色文本数字表示数组下标蓝红色序列号表示先后顺序。 从这张图中我们可以看到下标数据遵循着“先进后出”的性质哪种数据结构有“先进后出”的性质呢那就是栈。注意这里说的“栈”是数据结构的栈而不是内存的那个栈。我们自己开辟的栈是建立在内存的堆上的堆的大小远大于栈内存所以就不会像递归那么容易出现栈溢出。
void Quick_sort_NonR(pSortData pArray, int Size)
{PST pStack STInit();STPush(pStack, Size - 1);STPush(pStack, 0);while (!STEmpty(pStack)){int left STPop(pStack);int right STPop(pStack);int key Hoare_mode(pArray, left, right);if (key 1 right){STPush(pStack, right);STPush(pStack, key 1);}if (left key - 1){STPush(pStack, key - 1);STPush(pStack, left);}}STDestroy(pStack);
}注栈的相关文件请参考《栈和队列》。
PerformanceTesting(100000, Quick_sort_NonR)int main()
{ test_Quick_sort_NonR();return 0;
}看即使是这样大的数据个数也不会栈溢出。
好的上面的是带有三数选中的让我们先把数组构造函数换成最坏情况的那种然后再对比一下三数选中有无的效果。
PerformanceTesting(10000000, Quick_sort_NonR)int main()
{ test_Quick_sort_NonR();return 0;
}含有三数选中时的结果 现在我们把三数选中去掉为了节约时间就不打印了。
好的最起码运行了15分钟然后我受不了了关掉了。
除了栈之外队列也可以实现快速排序的非递归版本只不过此时它的遍历次序已经和递归完全不同了。此时它应该先把0,9压入队列再弹出0,9随后压入0,4和6,9然后弹出0,4压入0,1和3,4然后弹出6,9压入6,7和9······也就是说它是层序遍历树的。这里就不详细说了。 在某些极端情况下上述三种的快速排序可能会全部失效。什么情况呢那就是整个数组的所有成员的数值都相同。此时比如说right就会去寻找比基准值小的数可是很明显它找不到于是它就越界了。
为此就有了“三路划分”。三路划分和以往的三套方法相比有些根本上的不同。三路划分不像上述三套方法一样对等于基准值的数值视而不见而是想办法把这些数值移到中间。于是在经过一轮排序之后数组就可以被分成三个部分左边的部分存放着比基准值小的数值中间的部分存放着和基准值相同的数值右边的部分存放着比基准值大的值。
在三路划分中将会有三个指针left right curr。left和right的初始位置仍然在数组两端依旧把数组首元素视为基准值curr最开始将会位于第二个成员处。之后curr将会对数组成员进行遍历对于小于基准值的成员将会与left指向的成员进行数值交换这样做有两个目的一是把比基准值小的数移到左边二是把比基准值相同的数值往中间移在进行完数值交换之后left和curr都会向下移动一位对于等于基准值的数curr会直接移到下一位将这些与基准值相同的成员交给left日后处理如果成员大于基准值curr指向的成员就会与right指向的成员进行数值交换这样比基准值大的数值就被移到了右边不过由于不知道从right那边移过来的数值到底是什么情况所以curr不会向后移一位当然right确实会向前移一位当curr到达right的右边时就意味着整个数组的全部成员都已经被curr遍历比较过了于是这轮比较就结束了。
为了方便起见下面的动图没有考虑三数取中。 static void _Quick_sort_root_particularly(pSortData pArray, int left, int right)
{if (left right)return;SortData key pArray[left];int begin left;int current begin 1;int end right;while (current end){if (pArray[current] key){Swap((pArray[begin]), (pArray[current]));}else if (pArray[current] key){current;}else if (pArray[current] key){Swap((pArray[end--]), (pArray[current]));}}_Quick_sort_root_particularly(pArray, left, begin - 1);_Quick_sort_root_particularly(pArray, end 1, right);
}void Quick_sort_particularly(pSortData pArray, int Size)
{_Quick_sort_root_particularly(pArray, 0, Size - 1);
}PerformanceTesting(10, Quick_sort_particularly)int main()
{ test_Quick_sort_particularly();return 0;
}当然可以看到我们之前写的比较函数还不够好应该用整型或者其它类型布尔值只有两个选项而大小有三种可能大于小于等于。应该用整型大于0的代表大于等于0的代表等于小于0的代表小于。比较函数的缺陷之后我们还会再说。 一般来说这种级别的快排就没有什么问题了。但在某些在线编程测试平台上即使是这种级别的快排依旧无法通过无法通过的原因是因为上面的代码没有三数选中所以效率有些低但是即使加上之前那三个方法的三数选中依旧无法通过因为快排被这个平台恶意针对了它的测试用例恰好是左中右就是极值所以让三数选中失效了。
不过我们也有对策。解决方案是不把选中数组中间的成员作为三数中中间的那个数而是从选中数组中随机找一个成员作为中间的值。
int middle_of_three(pSortData pArray, int left, int right)
{srand((unsigned int)time(NULL));int mid left (rand() % (right - left));if (compare(pArray[left], pArray[mid])){if (compare(pArray[mid], pArray[right])){return mid;}else{if (compare(pArray[left], pArray[right])){return right;}elsereturn left;}}else{if (compare(pArray[right], pArray[mid])){return mid;}else{if (compare(pArray[left], pArray[right])){return left;}elsereturn right;}}
}不过日常情况下用不着使用这种级别的快排上面三种就够用了当然更可以直接使用标准库里的快排。
归并排序
归并排序使用的仍是分治的思想它先将整个数组分成若干个子数组然后再将这些子数组作进一步的拆分直到拆分出的子数组一定是有序的。什么叫“一定有序”很简单拆的只剩一个成员它不就自然有序了。比如对于一个有10个成员的数组来说它先把这10个数组拆分成2个大小为5的子数组下标分别是0到4, 5到9然后再进一步拆分拆成4个数组下标分别是0到2, 3到45到7, 8到9,随后再拆分变成下标为0到1 1到2 3, 4 5到6, 6到7, 8, 9········
拆成1个成员怎么办呢比如现在已经有两个已经“被迫”就一个成员吗有序的数组了第一个数组有一个成员是4第二个数组是1,归并归并就是归档合并于是我们先把这两个数组的首元素比较一下我们发现1是更小的于是就把1拷贝到一个暂时的空间然后第二个数组遍历完了于是就把第一个数组剩下的部分也就是那个6拷贝到暂存空间中然后再拷贝回去这样原数组的这两个子数组合并完了于是此时原数组的那个地方就变成了1,6好的现在已经有两个数组这两个数组都有两个成员第一个数组是1,6第二个数组是3,8然后呢我们把这两个数组的首元素比较一下我们发现1更小是吧就把1拷贝到暂存空间中然后对比一下第一个数组的第二成员和第二个数组的第一个成员我们发现3更小是吧那就把3拷贝到暂存空间然后再比较一下第一个数组和第二个成员的第二成员我们发现6更小于是拷贝到暂存空间然后第一个数组没成员了于是就把第二个数组的剩下部分再拷贝到暂存空间此时暂存空间的这个地方就是1,3,6,8了再把这地方拷贝会原数组的地方就行了。 因为某些不可抗拒因素可能有些帧没有被成功录入。
void _Merge_sort_root(pSortData pArray, int left, int right, pSortData p_Temporary_Storage)
{if (left right)return;int mid (left right) / 2;_Merge_sort_root(pArray, left, mid, p_Temporary_Storage);_Merge_sort_root(pArray, mid 1, right, p_Temporary_Storage);int begin1 left, end1 mid;int begin2 mid 1, end2 right;int begin left;while (begin1 end1 begin2 end2){if (compare(pArray[begin1], pArray[begin2])){p_Temporary_Storage[begin] pArray[begin2];}else{p_Temporary_Storage[begin] pArray[begin1];}}while (begin1 end1){p_Temporary_Storage[begin] pArray[begin1];}while (begin2 end2){p_Temporary_Storage[begin] pArray[begin2];}memcpy(pArray left, p_Temporary_Storage left, sizeof(SortData) * (right - left 1));
}void Merge_sort(pSortData pArray, int Size)
{pSortData pTS (pSortData)malloc(sizeof(SortData) * Size);if (pTS NULL){perror(Merge_sort pTS fail);return; }_Merge_sort_root(pArray, 0, Size - 1, pTS);free(pTS);
}PerformanceTesting(10, Merge_sort)int main()
{ test_Merge_sort();return 0;
}归并排序的递归写法还有一些地方可以再优化优化。我们知道递归其实就是把函数栈帧以树的形式组织起来。当归并排序输入的数据量过大时这棵树就会有太多的细小分支这些细小分支中的数组个数都很小没必要让它再继续分支下去。于是我们就可以设计一种机制当数组的成员个数小到一定程度时调用其他排序算法对这个小数组进行排序这样的话这个小数组其实也算是被迫有序了就可以参与到后续的合并过程中。而且由于树结构的特点比如现在假设归并排序的递归版本所运行的栈帧树就是一棵标准的满二叉树这样的话每个栈帧都可以被视为一个节点此时这棵树一共有 2 H − 1 2^H-1 2H−1个节点最后一层的节点数就是 2 H − 1 2^{H - 1} 2H−1,倒数第二层就是 2 H − 2 2^{H - 2} 2H−2,也就是说最后一层大概占总结点数的50%倒数第二层大概占总结点数的25.5%而末端优化优化的正是这些更深处的层于是归并排序的总递归次数就少了不小。
那到底该选择什么排序呢我这里用的是插入排序毕竟这里要排的数组只是一个小数组罢了用不着快排堆排希尔之类再加上插入排序并不会破坏归并排序的稳定性后面会说的所以还是用它。
具体改起来很简单
void _Merge_sort_root(pSortData pArray, int left, int right, pSortData p_Temporary_Storage)
{if (left right)return;if (right - left 1 10){Insert_sort(pArray left, right - left 1);return;}int mid (left right) / 2;_Merge_sort_root(pArray, left, mid, p_Temporary_Storage);_Merge_sort_root(pArray, mid 1, right, p_Temporary_Storage);int begin1 left, end1 mid;int begin2 mid 1, end2 right;int begin left;while (begin1 end1 begin2 end2){if (compare(pArray[begin1], pArray[begin2])){p_Temporary_Storage[begin] pArray[begin2];}else{p_Temporary_Storage[begin] pArray[begin1];}}while (begin1 end1){p_Temporary_Storage[begin] pArray[begin1];}while (begin2 end2){p_Temporary_Storage[begin] pArray[begin2];}memcpy(pArray left, p_Temporary_Storage left, sizeof(SortData) * (right - left 1));
}接下来我们说一说归并排序的非递归。
上面我们说过当数组只有一个成员时它就自然而言地有序了所以我们就先把数组中的相邻成员直接两两分组每组排一下然后每小组两个成员就有序了然后再把相邻的两个小组进行合并以此类推当然可以预见到这种方法肯定会有很多越界错误所以我们要做的就是把这些错误找出来针对这些错误对代码进行不断优化。
void Merge_sort_NonR(pSortData pArray, int Size)
{pSortData pTS (pSortData)malloc(sizeof(SortData) * Size);if (pTS NULL){perror(Merge_sort pTS fail);return;}int gap;for (gap 1; gap Size; gap * 2){// The variable “begin” changes itself when it is written to the staging array, // eliminating the need to manually control the iteration.int begin 0;while (begin Size){// The variable “start” is used to control the starting position of the data copy.int start begin;int begin1 begin, end1 begin1 gap - 1;int begin2 end1 1, end2 begin2 gap - 1;// The three conditional statements along with // the outer loop condition prevent the variable from going out of bounds.if (end1 Size){end1 Size - 1;end2 Size - 1;begin2 end2 1;}if (begin2 Size){end2 Size - 1;begin2 end2 1;}if (end2 Size){end2 Size - 1;}while (begin1 end1 begin2 end2){if (compare(pArray[begin1], pArray[begin2])){pTS[begin] pArray[begin2];}else{pTS[begin] pArray[begin1];}}while (begin1 end1){pTS[begin] pArray[begin1];}while (begin2 end2){pTS[begin] pArray[begin2];}memcpy(pArray start, pTS start, sizeof(SortData) * (end2 - start 1));}}free(pTS);
}其中条件语句的下标调整故意使得begin2end2从而不进入下面的第一个循环。
PerformanceTesting(10, Merge_sort_NonR)int main()
{ test_Merge_sort_NonR();return 0;
}还有一种方法实现归并排序的非递归与上面的思想大致相同主要区别是这种写法的是一层一层地覆写回原数组的而上面的写法是一对一对地覆写回原数组了。
为什么说是“一层一层”呢这是从归并排序的递归角度来说的很明显在递归过程中函数栈帧就像一棵树一样展开这棵树的每一层都是把数组分成间隔不同的子数组然后再逐个排序
void Merge_sort_NonR1(pSortData pArray, int Size)
{pSortData pTS (pSortData)malloc(sizeof(SortData) * Size);if (pTS NULL){perror(Merge_sort pTS fail);return;}int gap;for (gap 1; gap Size; gap * 2){int begin 0;while (begin Size){int begin1 begin, end1 begin1 gap - 1;int begin2 end1 1, end2 begin2 gap - 1;if (end1 Size){end1 Size - 1;end2 Size - 1;begin2 end2 1;}if (begin2 Size){end2 Size - 1;begin2 end2 1;}if (end2 Size){end2 Size - 1;}while (begin1 end1 begin2 end2){if (compare(pArray[begin1], pArray[begin2])){pTS[begin] pArray[begin2];}else{pTS[begin] pArray[begin1];}}while (begin1 end1){pTS[begin] pArray[begin1];}while (begin2 end2){pTS[begin] pArray[begin2];}}memcpy(pArray, pTS, sizeof(SortData) * Size);}free(pTS);
}差不多这两种的关键都是控制下标不要越界。
PerformanceTesting(10, Merge_sort_NonR1)int main()
{ test_Merge_sort_NonR1();return 0;
}内排序和外排序
之前我们在堆的章节说过当数据量过大时就无法将全部数据一次性压入内存。上面我们说的排序代码都是内排序接下来我们将会学习外排序。所谓内排序就是在内存中对数据进行排序外排序就是在外存主要是硬盘中对数据进行排序。
那外排序到底怎么排的呢实际上我们用的仍然是归并排序的思想所以我在上文说“排序代码”而不是“排序”它的思想是把大文件分成一个个小文件小到其中的数据已经放得下内存里了然后使用内排序对这些数据进行排序然后再写回到文件的原位置处之后以文件访问的方式打开这些子文件使用文件指针对其中的成员逐个访问依次类推。
由于时间关系在此我们先只说思想。
非比较排序
上面我们说的排序都是比较排序接下来我们说一说非比较排序这种排序在日常生活中基本不会用到主要是了解一下。
非比较排序分为基数排序和计数排序。基数排序用的就是学前班数学的思路有两个数怎么比较大小先看一下它们的位数都一样的那就比一下最高位谁最高位大谁就大一样就比较下一位它真的没什么用。
计数排序虽然在日常生活中也不会用到但它具有很深的教育启蒙意义往深了说它是对哈希直接定址法的变形应用这是C里的我就不深入讲了。
计数排序具体怎么做呢
它首先会将要排序的数组遍历一遍从而确定要排序数据的大致范围然后依据这个范围开辟一个数组接着再次遍历排序数组对这些数据进行计数遍历完后对开辟数组的计数进行展开就能得到有序数组好吧还是看动图吧。 绝对映射就是1就对应下标1,2就对应下标2,3就对应下标3,100000就对应100000那种。如果这样映射就要建13个成员的数组了。
void count_sort(int* pArray, int Size)
{int min pArray[0], max pArray[0];int current;for (current 0; current Size; current){if (min pArray[current]){min pArray[current];}if (max pArray[current]){max pArray[current];}}int temSize max - min 1;int* p_tem (int*)calloc(temSize, sizeof(int));if (p_tem NULL){perror(count_sort malloc fail);return;}for (current 0; current Size; current){p_tem[pArray[current] - min];}int i 0;for (current 0; current temSize; current){while (p_tem[current]){pArray[i] current min;p_tem[current]--;}}free(p_tem);
}int main()
{int arr[] { 4,7,15,6,7,8,9,5,6,15,13 };int sz sizeof(arr) / sizeof(arr[0]);count_sort(arr, sz);int i;for (i 0; i sz; i){printf(%d ,arr[i]);}printf(\n);return 0;
}很明显计数排序很受数组数据范围的影响所以不能使用通用测试模块另外你可能注意到计数排序的数据类型用的全是原生类型因为计数排序只能对整型或者说整数进行排序它的数据类型是被定死的。 稳定性
什么叫稳定性可能有些人会将稳定性误以为是性能的稳定性其实不是。在排序过程中可能会有相同的数值成员为了方便我们就认为有两个相同的值 A 1 A_1 A1和 A 2 A_2 A2如果在排序之前 A 1 A_1 A1在 A 2 A_2 A2的前面排完序后 A 1 A_1 A1依旧在 A 2 A_2 A2的前面那这种算法就是稳定的否则就是不稳定的。
这是有实际应用价值的。描述某个事物可能要不止一个数据比如它可能是个结构体此时就要进行多次排序优先级高的先排序然后对于数值相同的我们需要进行下一轮排序此时的参考项就是优先级低一层的。
比如对于某场考试它可能由多场科目构成比如说有科目ABC优先级依次降低我先比一下总分然后再比一下A科再比一下B科接着是C科此时的排序算法就必须是稳定的才行。
冒泡是稳定的对于相同的数值不会进行交换直接插入排序是稳定的对于数值相同的项我们是写在有序区后一位的希尔排序只能保证子数组的稳定性但整体稳定性就无法保证了选择排序我就不分析了直接举个反例已知在数组中现有四个数 A 1 A 2 ; B 1 B 2 A_1 A_2; B_1 B_2 A1A2;B1B2,已知 A B AB AB其中 A 1 A_1 A1是数组首元素 A 2 A_2 A2夹在 B 1 B_1 B1和 A 1 A_1 A1之间 A 2 A_2 A2在 A 1 A_1 A1之后为了方便考虑我们每轮就找一个极值最小值现在假设 B B B恰好即使是最小的那个值于是在第一轮寻找中 A 1 A_1 A1就会和 B 1 B_1 B1交换位置这样 A 1 A_1 A1就会在 A 2 A_2 A2后了换言之稳定性被破坏了堆排序也不稳定比如现在要建一个小堆根节点和左节点数值相同根节点大于右节点这样一交换稳定性就被破坏了快排不稳定即使不考虑三数取中它也是不稳的当有两个比基准值大的相同值时就不稳定了归并要看具体代码比如在上面的代码中如果等于先写入的确实是begin1所以是稳定的如果else分支里写的是begin2那就不稳了此时若要稳定就需要在条件判断里加个等于号不过由于这里的比较函数设计有缺陷所以要仿照霍尔排序的那种取反来写。
urrent 0; current Size; current) { p_tem[pArray[current] - min]; } int i 0; for (current 0; current temSize; current) { while (p_tem[current]) { pArray[i] current min; p_tem[current]–; } } free(p_tem); } c
int main()
{int arr[] { 4,7,15,6,7,8,9,5,6,15,13 };int sz sizeof(arr) / sizeof(arr[0]);count_sort(arr, sz);int i;for (i 0; i sz; i){printf(%d ,arr[i]);}printf(\n);return 0;
}很明显计数排序很受数组数据范围的影响所以不能使用通用测试模块另外你可能注意到计数排序的数据类型用的全是原生类型因为计数排序只能对整型或者说整数进行排序它的数据类型是被定死的。
[外链图片转存中…(img-Qzr03ymo-1726732666915)]
稳定性
什么叫稳定性可能有些人会将稳定性误以为是性能的稳定性其实不是。在排序过程中可能会有相同的数值成员为了方便我们就认为有两个相同的值 A 1 A_1 A1和 A 2 A_2 A2如果在排序之前 A 1 A_1 A1在 A 2 A_2 A2的前面排完序后 A 1 A_1 A1依旧在 A 2 A_2 A2的前面那这种算法就是稳定的否则就是不稳定的。
这是有实际应用价值的。描述某个事物可能要不止一个数据比如它可能是个结构体此时就要进行多次排序优先级高的先排序然后对于数值相同的我们需要进行下一轮排序此时的参考项就是优先级低一层的。
比如对于某场考试它可能由多场科目构成比如说有科目ABC优先级依次降低我先比一下总分然后再比一下A科再比一下B科接着是C科此时的排序算法就必须是稳定的才行。
冒泡是稳定的对于相同的数值不会进行交换直接插入排序是稳定的对于数值相同的项我们是写在有序区后一位的希尔排序只能保证子数组的稳定性但整体稳定性就无法保证了选择排序我就不分析了直接举个反例已知在数组中现有四个数 A 1 A 2 ; B 1 B 2 A_1 A_2; B_1 B_2 A1A2;B1B2,已知 A B AB AB其中 A 1 A_1 A1是数组首元素 A 2 A_2 A2夹在 B 1 B_1 B1和 A 1 A_1 A1之间 A 2 A_2 A2在 A 1 A_1 A1之后为了方便考虑我们每轮就找一个极值最小值现在假设 B B B恰好即使是最小的那个值于是在第一轮寻找中 A 1 A_1 A1就会和 B 1 B_1 B1交换位置这样 A 1 A_1 A1就会在 A 2 A_2 A2后了换言之稳定性被破坏了堆排序也不稳定比如现在要建一个小堆根节点和左节点数值相同根节点大于右节点这样一交换稳定性就被破坏了快排不稳定即使不考虑三数取中它也是不稳的当有两个比基准值大的相同值时就不稳定了归并要看具体代码比如在上面的代码中如果等于先写入的确实是begin1所以是稳定的如果else分支里写的是begin2那就不稳了此时若要稳定就需要在条件判断里加个等于号不过由于这里的比较函数设计有缺陷所以要仿照霍尔排序的那种取反来写。
完
