几种排序算法效率的比较

1、1.稳定性比较插入排序、冒泡排序、二叉树排序、双向合并排序和其他线性排序都是稳定的选择排序、希尔排序、快速排序和堆排序不稳定2.时间复杂性比较插入排序、气泡排序和选择排序的时间复杂度为0(N2)其他非线性排序的时间复杂度为0(nlog2n)线性排序的时间复杂度为0(n)；3.辅助空间的比较线性排序和双向合并排序的辅助空间为0(n)，其他排序的辅助空间为0(1)；4.其他比较插入和气泡排序的速度很慢，但是当参与排序的序列被局部或全局排序时，排序可以达到更快的速度。相反，在这种情况下，快速排序很慢。当n小时，当不需要稳定性时，使用选择性排序，当需要稳定性时，使用插入或气泡排序。如果要排序的记录的关

2、键字在明显有限的范围内，并且空间允许按桶排序。当n较大时，关键元素更随机，所以稳定性不需要快速排序。当n较大时，当需要稳定性且空间允许时，关键字元素本身可能看起来是有序的。使用合并排序是合适的。当n较大时，关键字元素本身看起来可能是有序的，并且堆排序对于稳定性来说不是必需的。* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

3、* *重温经典排序思想一个解决C语言常见排序问题的完整方案/*=相关知识介绍(所有定义仅帮助读者理解相关概念，未严格定义):1.稳定分拣和不稳定分拣简而言之，所有相等的数字在排序之前仍然可以保持它们的相对顺序，所以我们将表示这种方法是稳定的。相反，它是不稳定的。例如，一组数字是排序前的a1、a2、a3、a4、a5，其中a2=a4，排序后的a1、a2、a4、a3、a5。然后我们说这种排序是稳定的，因为a2在a4之前，在排序之后它仍然在a4之前。如果它变成a1，a4，A2、A3和A5不稳定。2.内部排序和外部排序在排序过程中，所有需要排序的数字都在内存中，它们的存储顺序在内存中进行调整，这称为内部

4、排序。在排序过程中，只有部分数字被转移到内存中，在外部内存中有内存调整数的存储顺序排序方法称为外部排序。3.算法的时间复杂度和空间复杂度所谓算法的时间复杂度是指执行算法所需的计算量。算法的空间复杂度通常指执行算法所需的内存空间。=*/*=功能：选择排序输入：数组名(即数组头地址)，数组中的元素数=*/*=算法思想的简单描述：在要排序的一组数字中，选择最小的数字与第一个位置的数字交换；然后在剩余的数字中找出最小的数字，与第二个位置的数字交换，依此类推直到倒数第二个数字与最后一个数字相比较。选择排序不稳定。算法复杂性O(N2)-N的平方=*/void select_sort(int *x，int

5、n)I，j，min，t；对于(I=0；号码已经在第行了按照良好的顺序，现在我们必须将第n个数字插入到前一个有序数字中，以便第n个数字它也很好。重复这一循环，直到一切就绪。直接插入排序是稳定的。算法时间复杂度O(N2)-N的平方=*/void insert_sort(int *x，int n)I，j，t；对于(I=1；I=0t *(x j)；J-)/*注：j=i-1，J-，这是带下标I的数字，找到它前面序列中的插入位置。*/*(x j 1)=*(x j)；/*如果条件满足，请后退。最坏的情况是t小于下标为0的数。它应该放在前面，j=-1，退出循环*/*(x1)=t；/*用下标I *找到数字的放置

6、位置/*=功能：气泡分类输入：数组名(即数组头地址)，数组中的元素数=*/*=算法思想的简单描述：在一组要排序的数字中，范围内所有未排序的数字都从上到下排序但是，接下来的两个相邻的数字会依次进行比较和调整，这样，较大的数字会下沉，较小的数字会下沉较小的一个上升。也就是说，每当比较两个相邻的数字时，就会发现它们的排序和排序需要当寻找相反的东西时，交换它们。下面是一个改进的冒泡算法，它记录了每次扫描后的最终下沉数位置K，可以减少外层循环扫描的次数。气泡分选稳定。算法时间复杂度O(N2)-N的平方=*/void bubble_sort(int *x，int n)int j，k，h，t；对于(h=n-

7、1；h0；H=k) /*循环至无比较范围*/对于(j=0，k=0；J *(x j 1) /*大的在后面，小的在前面*/t=*(x j)；*(x j)=*(x j 1)；*(x1)=t；/*交易完成*/k=j。/*保存最后下沉的位置。这样，k之后的都是按顺序排列的。*/*=功能：希尔排序输入：数组名(即数组头地址)，数组中的元素数=*/*=算法思想的简单描述：在直接插入排序算法中，一次插入一个数字，使有序序列只增加一个节点。并且不为插入下一个号码提供任何帮助。如果比较相隔很远(称为Increment)数字，这样数字可以在多个元素之间移动，然后可以消除比较多元素交换。1959年，以他的名字命名的排

8、序算法实现了D.L.shell。这个想法实现了。该算法首先将一组待排序的数字按照一定的增量d分成若干组，在每组中记录的下标相差d。对每个组中的所有元素进行排序，然后使用较小的增量。它在每个组中排序。当增量减少到1时，要排序的整个数字被分成一组，排序完成。下面的函数是希尔排序算法的实现，第一次将序列的一半作为增量。每过一半，直到增量为1。希尔的排名不稳定。=*/void shell_sort(int *x，int n)int h，j，k，t；对于(h=n/2；h0；H=h/2) /*控制增量*/对于(j=h；j=0t *(x k)；k-=h)*(x k h)=*(x k)；*(x k h)=t；

9、/*=功能：快速排序输入：数组名(即数组头地址)和数组中开始和结束元素的下标=*/*=算法思想的简单描述：快速分类是对气泡分类的一个重要改进。它的基本思想是经历一次旅行扫描后，测序序列的长度可以大大缩短。在泡泡排序中，一次扫描只能确保最大值的数量移动到正确的位置，而要排序的序列长度只能减少1。快速排序可以通过一次扫描确保某个数字(以此为参考点)。左边的每个数字都比它小，右边的每个数字都比它大。然后以同样的方式对待它。其左侧和右侧的数量，直到参考点的左侧和右侧只有一个元素。它是由C.霍尔于1962年提出。显然，快速排序可以通过递归实现，当然，它也可以通过堆栈解析递归实现。在下面函数是递归实现的，感兴趣的朋友可以改为非递归。快速排序是不稳定的。最佳情况算法和最坏情况算法的时间复杂度O(nlog2n)。=*/void quick_sort(int *x，int low，int high)I，j，t；如果(低高)/*要排序的元素的开始和结束下标，确保小下标在左边，大下标在右边。这里，以下标记为低的元素是参考点*/i=低；j=高。t=*(x低)；/*临时基准点的数量