- 合并排序与快速排序
- 一、合并排序
- 1.基本思想
- 2.代码
- 3.时间复杂度
- 二、快速排序
- 1.基本思想
- 2.步骤
- 3.时间复杂度
- 总结
一、合并排序
合并排序算法又叫归并排序,是用分治策略实现对n个元素进行排序的算法
1.基本思想将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成所要求的排好序的集合。
合并方法是循环的将两个有序子序列当前的首元素进行比较,较小的元素取出,置入合并序列的左边空置位,直至其中一个子序列的最后一个元素置入合并序列中。最后将另一个子序列的剩余元素按顺序逐个置入合并序列尾部即可完成排序。(二分法)
由于排序问题的计算下界为Ω(nlog n),所以合并排序是一个渐进最优算法
代码
#include#include #define maxx 105 int a[maxx]; int merge[maxx]; //合并两个有序子序列 void Merge(int merge[],int a[],int left,int right,int middle){ int i=left,j=middle+1; int k=left; while(i<=middle&&j<=right){ if(a[i]<=a[j]){ merge[k++]=a[i++]; }else{ merge[k++]=a[j++]; } } while(i<=middle)merge[k++]=a[i++]; while(j<=right)merge[k++]=a[j++]; i=0; for(i=left;i<=right;i++)a[i]=merge[i]; } //合并排序算法 void Mergesort(int a[],int left,int right){ if(left int middle=(left+right)>>1; Mergesort(a,left,middle); Mergesort(a,middle+1,right); Merge(merge,a,left,right,middle); } } int main(){ int n; while(scanf("%d",&n)!=EOF){ int i; for(i=0;i scanf("%d",&a[i]); } Mergesort(a,0,n-1); i=0; for(i=0;i printf("%d ",a[i]); } } return 0; }
3.时间复杂度
1)最好时间复杂度:O(log n)
2)最坏时间复杂度:O(n*log n)
最坏情况T(n)=O(1) ,n<=1
T(n)=2T(n/2)+O(n),n>1
3)空间复杂度O(n)
基于分治策略的另一种排序,是性能最好的排序方式
1.基本思想选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以达到全部数据变成有序。
2.步骤(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边),在这个分区退出之后,该基准就处于数列的中间位置。
(3) 递归地把基准值前面的子数列和基准值后面的子数列进行排序。
代码如下(示例):
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序结果:" + Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 获取枢纽值,并将其放在当前待处理序列末尾
dealPivot(arr, left, right);
// 枢纽值被放在序列末尾
int pivot = right - 1;
int i = left; // 左指针
int j = right - 1; // 右指针
while (true) {
while (arr[++i] < arr[pivot]) {
}
while (j > left && arr[--j] > arr[pivot]) {
}
if (i < j) {
swap(arr, i, j);
} else {
break;
}
}
if (i < right) {
swap(arr, i, right - 1);
}
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
}
public static void dealPivot(int[] arr, int left, int right) {
int mid = (left + right) / 2;
if (arr[left] > arr[mid]) {
swap(arr, left, mid);
}
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
if (arr[right] < arr[mid]) {
swap(arr, right, mid);
}
swap(arr, right - 1, mid);
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
3.时间复杂度
以减少排序过程中的比较次数,
1)它的最好情况为O(nlogn),
每一次划分都正好将数组分成长度相等的两半
T(n)=2T(n/2)+O(n)
=2(2T(n/4)+O(n/2))+O(n)=4T(n/4)+2O(n/2)+O(n)
=8T(n/8)+4O(n/4)+2O(n/2)+O(n)
….
=nT(n/n)+….+2O(n/2)+O(n)
=nT(1)+….+2O(n/2)+O(n)
=nT(1)+lognO(n)
=O(n+nlogn)=O(nlogn)
其空间复杂度也就为O(logn)
2)最坏情况为O(n2),
即每一次划分都将数组分成了0和n-1两部分
T(n)=T(n-1)+O(n)
=T(n-2)+O(n-1)+O(n)
=T(n-3)+O(n-2)+O(n-1)+O(n)
…
=O(n)+O(n-1)+…+O(n-2)+O(n-1)+O(n)
=O(n(n-1)/2)=O(n2)
n‐1次递归调用
其空间复杂度为O(n),
3)平均时间复杂度为O(nlogn)。
在平均情况下,即轴枢在第K位置,
平均情况,空间复杂度也为O(logn)
总结快速排序不稳定,性能好坏取决于划分的对称性



