常见排序算法以及对应的时间复杂度和空间复杂度
排序 ：将杂乱无章的数据，按照一定的方法进行排列的过程叫做排序。
排序大的分类可分为 内排序 和 外排序 ，不需要访问外存就能进行排序的叫做内排序。
排序也可以分为 稳定排序 和 不稳定排序
稳定排序 ：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，经过排序后 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、归并排序，基数排序都是稳定排序。
不稳定排序 ：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。
以升序为例，比较相邻的元素，如果***个比第二个大，则交换他们两个。如果两个元素一样大，则继续比较下一对。所以冒泡排序是一种稳定排序。
选择一个基准元素,通常选择***个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序是不稳定排序。
将序列分为两个部分{{有序序列},{无序}}，每次处理就是将无序数列的***个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。如果碰到相等的元素，就会把它插入到想等元素后面，顺序不会改变，所以直接插入排序是稳定排序。
在直接插入排序的基础上，对有序序列进行划分。例如：序列为 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 为有序序列，取 a[(i-1)/2] ，将其与 a[i] 比较，即可确定 a[i] 的范围 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然后继续在已确定的范围内进行二分。范围依次缩小为： 1/2、1/4、1/8、1/16...... 可快速确定a[i]应该插入的位置。二分插入排序也是稳定排序。
将整个序列分割成若干个小的子序列，每个子序列内分别进行插入排序。一般情况下步长取n/2。直到最后一次步长为1，即所有元素在一个组中进行排序。由于希尔排序是先将整个序列划分为多个子序列进行排序，相同的元素顺序在这个过程中顺序可能会被打乱，所以希尔排序是不稳定排序。
从待排序的数据元素中，选出最小或***的元素与序列***个数交换。直到所有数据排完。直接选择排序是不稳定排序。例如： {3，3，1} ，***次排序就将1和***个3交换，想等元素的顺序改变了。
以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
***堆:每个节点的值都大于等于它的孩子节点。
最小堆:每个节点的值都小于等于它的孩子节点。
***堆第0个数据是***数，最小堆第0个数据是最小数。
堆排序是不稳定排序
思想
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
如何将两个有序序列合并？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]a[0] ，取 b[0] 放入数组 c 中，然后继续比较数组 a 和 b 中的***个元素，直到数组 a 和 b 中最后一对元素比较完成。
思想
将数组分成二组 a , b 如果这二组组内的数据都是有序的，那么就可以按照上述方法对这二组数据进行排序。如果这二组数据是无序的？
可以将 a , b 组各自再分成二组。递归操作，直到每个小组只有一个数据，每个小组只有一个元素所以我们可以认为它已经是有序序列，然后进行合并。
先分解后合并。
归并排序是稳定排序
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。从***位起从0-9依次扫描序列，一边扫描一边将扫描到的数据加到新的序列中，得到一个序列。然后比较高一位，重复上述操作，直到***位排序完成。数列就变成一个有序序列。基数排序是稳定排序。
以全是二位数的序列举例
无限猴子定理 :指一只猴子随机在打字机键盘上按键，最后必然可以打出法国国家图书馆的每本图书。
时间复杂度***1次，***可执行到世界的尽头。。。
c++ sort()是稳定排序吗?
c++sort不是稳定排序，stl中stable_sort才是稳定排序。
稳定排序的概念：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
排序稳定性是什么？
排序的稳定性,就是指,在对a关键字排序后会不会改变其他关键字的顺序。
比如排序（2，3，1（***个），1（第二个），5，6）
不稳定的排序，可能会排出
（1（第二个），1（***个），2，3，5，6）；
而稳定的排序则不会，在比较的关键字相同的情况下，稳定的排序会将较早出现的元素排在前面。
冒泡排序是不是稳定排序,求算法
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
# include stdio.h
void bu***leSort(int arr[],int n)
{
int i,j,t;
for(i=0;in-1;i++)
{
for(j=0;jn-i-1;j++)
{
if(arr[j+1]arr[j])
{
t=arr[j+1];
arr[j+1]=arr[j];
arr[j]=t;
}
}
}
}
void print(int arr[],int n) //打印数组
{
int i=0;
for(;in;i++)
{
printf("%d ",arr[i]);
}
printf("n");
}
int main(void)
{
int arr[]={49,15,52,64,98}; //测试数据
print(arr,5);
bu***leSort(arr,5);
printf("排序后的结果：n");
print(arr,5);
return 0;
}
哪些排序是稳定的
希尔排序、堆排序: 就地的不稳定排序
快速排序: 非就地的不稳定排序
选择排序: 不稳定排序
插入排序: 稳定排序
关于稳定排序和稳定排序算法有哪些的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。