冒泡排序：
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换，提前退出
}
}
第一，冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
第二，冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
第三，冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
插入排序：
将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
//数组小于等于一直接跳出
if (n <= 1) return;
for(i=1;i<n;i++){
//拿到当前下表元素
int value=a[i];
//指定当前元素前的已排序区间的最后一个
int j=i-1;
//循环已排序区间,查找插入位置
for(;j>=0;--j){
//当j位置的元素大于要插入的元素时，j位置的元素向后移
if(a[j]>value){
//向后移一位
a[j+1]=a[j];
}else{
//找到了合适的插入位置，跳出循环
break;
}
}
//将元素插入
//当前的j已经是--后的，
a[j+1]=value;
}
}
第一，插入排序是原地排序算法吗？
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。
第二，插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
第三，插入排序的时间复杂度是多少？
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2)。插入一个数据的平均时间复杂度是 O(n)。对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n2)。
选择排序：
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
// 选择排序，a表示数组，n表示数组大小
public void selectSort(int[] a, int n) {
if (n <= 1) return;
int temp=0;
for(int i=0;i<n-1;i++){
int min=i;
for(int j=i,j<n-1;j++){
//找到最小值
if(a[j]<a[min]){
min=j;
}
}
//将最小元素放到排序区间末尾
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}
第一，选择排序是原地排序算法吗？
选择排序空间复杂度为 O(1)，是一种原地排序算法。
第二，插入排序是稳定的排序算法吗？
选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。
第三，插入排序的时间复杂度是多少？
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。
解答
泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？
前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个：
//冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
//插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
归并排序：
归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
public void mergeSort(int[] a, int n) {
//递归调用分为前后两部分排序并且合并为有序数组
merge_sort(a,0,n-1)
}
//分为两部分分别排序
private int[] merge_sort(int[] a,int p,int r){
//递归终止条件
if(p>=r) return;
int q=p+(r-p)/2;
//字数组分割排序,递归调用
int[] p2q = merge_sort(a,p,q);
int[] q2r = merge_sort(a,q+1,r);
//分组排序后归并为一个数组
return merge(a,p,q,p2q,q+1,r,q2r);
}
//将分数组合并
private int[] merge(int[] a,int p,int q,int[] p2q,int q1,int r,int[] q2r){
//设置一个临时数组，大小为p到r的长度
int[] merge=new int[r-p];
//分别定义两个子数组和合并数组的游标i,j,k;
int i=0,j=0,k=0;
//创建一个带哨兵的临时数组，把两个子数组的元素添加到临时数组里面
int[] p2qTemp=new int(q-p+1);
int[] q2rTemp=new int(r-q1+1);
//这里的addAll是伪代码，因为数组没有addAll方法
p2qTemp.addAll(p2q);
q2rTemp.addAll(q2r);
//数组最后设置哨兵,设置了哨兵就不需要判断哪个子数组中有剩余的数据
//短的数组才设置哨兵
if(p2q.size>q2r.size){
q2rTemp[q2r.size]=int.MaxValue;
}else{
p2qTemp[p2q.size]=int.MaxValue;
}
//比较大小放入合并数组中
//如果短的到了最后一个也就是哨兵元素
//长的剩余元素会根据大小判断一直放入到合并数组中
//就不需要判断那个子数组中有剩余数据了
for(;k<=r-p,k++){
//这里要设置为 <= ,如果单单是 < 就失去了稳定性
if(p2qTemp[i]<=q2rTemp[j]){
merge[k]=p2qTemp[i];
i++;
}else{
merge[k]=q2rTemp[j];
j++
}
}
return merge;
}
第一，归并排序是稳定的排序算法吗？
结归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p...q]和 A[q+1...r]之间有值相同的元素，那我们可以像伪代码中那样，先把 A[p...q]中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
第二，归并排序的时间复杂度是多少？
归并排序涉及递归，时间复杂度的分析稍微有点复杂。递归的适用场景是，一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，再把 b、c 的结果合并成 a 的结果。如果定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那就可以得到这样的递推关系式：
T(a) = T(b) + T(c) + K
其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。
从刚刚的分析，可以得到一个重要的结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
套用这个公式，来分析一下归并排序的时间复杂度。
假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n；
n>1通过这个公式，再进一步分解一下计算过程。
T(n) = 2*T(n/2) + n = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n ......
通过这样一步一步分解推导，可以得到 T(n) = 2kT(n/2k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，得到 k=log2n 。将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。从原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
第三，归并排序的空间复杂度是多少？
归并排序的时间复杂度任何情况下都是 O(nlogn)，但是，归并排序并没有像快排那样，应用广泛，因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。这一点你应该很容易理解。并排序的空间复杂度到底是多少呢？是 O(n)，还是 O(nlogn)，应该如何分析呢？如果继续按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是 O(nlogn)。不过，类似分析时间复杂度那样来分析空间复杂度，这个思路对吗？实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚遗漏了最重要的一点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
快速排序
快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
根据分治、递归的处理思想，可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
public void quickSort(int[] a, int n) {
//递归调用分为pivot左边和右边
quick_sort(a,0,n-1)
}
//快速排序分离左边，右边和分区点pivot
private void quick_sort(int[] a,int p,int r){
if(p>=r) return;
//获取分区点并进行分区
int q=partition(A, p, r);
//子数组分离
quick_sort(a,p,q);
quick_sort(a,q+1,r);
}
private int patition(int[] a,int p,int r){
//设置分区点为数组最后一项
int pivot = a[r];
//定义游标
int i=p;
//i为已处理好区间的游标，j为遍历未处理好区间的游标
for(j=p;p<r-1;j++){
if(a[j]<pivot){
//如果小于区分点的值，i和j进行交换，也就代表小的值放到了已处理好的区间
int temp=a[i];
int a[i]=a[j];
a[j]=temp;
//交换后i的值加1，代表已经区分好的游标指向下一个
i=+1；
}
}
//循环结束，处理完成，i的值即代表中间 pivot 应该的位置，也就是分区点。
//进行交换，交换到分区位置
int temp = a[i];
a[i] = pivot;
a[r] = temp;
return i;
}
第一，快速排序是稳定的排序算法吗？
快排是一种原地、不稳定的排序算法。因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
第二，快速排序的时间复杂度是多少？
快排也是用递归来实现的。对于递归代码的时间复杂度，前面总结的公式，这里也还是适用的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。
但是，公式成立的前提是每次分区操作，我们选择的 pivot 都很合适，正好能将大区间对等地一分为二。但实际上这种情况是很难实现的。T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。
第三，归并排序的空间复杂度是多少？
首先使用就地快速排序使用的空间是O(1)的，也就是个常数级。而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据。最优的情况下空间复杂度为：O(logn) ，最差的情况下空间复杂度为：O( n ) 。
解答
快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
桶排序、计数排序、基数排序待续...
网友评论