算法排序总结
排序算法总结
算法的稳定性:如果待排序表中有两个元素Ri、Rj，其对应的关键字Ki=Kj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
首先，需要用到的一些公共函数，放在一个抽象父类里面
public abstract class BaseSort {//可传入任何实现Comparable接口的数据类型public abstract void sort(Comparable[] a);//判断两者大小protected boolean less(Comparable v, Comparable w){return v.compareTo(w)<0;}//交换值protected void exch(Comparable[] a, int i, int j){Comparable temp = a[i];a[i] = a[j];a[j] = temp;}protected void show(Comparable[] a){for(int i = 0; i < a.length;i++){StdOut.print(a[i]+"");}StdOut.println();}//判断是否已经排序public boolean isSorted(Comparable[] a){for(int i = 1; i< a.length;i++){if(less(a[i],a[i-1]))return false;}return true;}
}1、冒泡排序
public class BubbleSort extends BaseSort {boolean isSwap;@Overridepublic void sort(Comparable[] a) {//注意这里是i < a.length-1isSwap = false;for(int i = 0; i < a.length-1; i++){//已经冒泡到最后面的，就不要再比较了。所有j < a.length-1-ifor(int j = 0;j < a.length-1-i;j++){if(less(a[j+1],a[j])){exch(a,j,j+1);isSwap = true;}}if(!isSwap) //如果没有发生交换,则表明有序return;} }}性能分析:
空间复杂度: O(1)
最坏情况时间复杂度:O(n^2)
最好情况时间复杂度:O(n)
平均时间复杂度:O(n^2)
稳定的排序方法
冒泡排序中产生的有序子序列一定是全局有序的,也就是说每一趟排序会将一个元素放置到最终的位置上
2、插入排序
原理：将每一个值插入到已经有序的序列中的适当位置
public class InsertionSort extends BaseSort{@Overridepublic void sort(Comparable[] a) {int N = a.length;for(int i = 0; i < N; i++){//循环跟前面的值比较，把小的插到前面去for(int j = i; j>0;j--){if(less(a[j],a[j-1])){exch(a,j,j-1);}}} }}性能分析:
空间复杂度:O(1)
最坏情况时间复杂度:O(n^2)
最好情况时间复杂度:O(n)
平均时间复杂度:O(n^2)
稳定的排序方法
3、选择排序
原理：1、找到数组中最小的元素
2、将它和数组的第一个元素交换，如果是自己则不交换
3、在剩下的元素中找到最小的元素，将它与数组的第二个元素交换
4、如此反复，直到将整个数组排序
public class SelectionSort extends BaseSort{@Overridepublic void sort(Comparable[] a) {int N = a.length;for(int i = 0; i < N-1; i++){//mim作为最小值的索引int min = i;//找出最小值for(int j = i+1; j < N; j++){if(less(a[j],a[min])){min = j;}}//和最小值交换if（min!=i)exch(a,i,min);} }
}性能分析:
空间复杂度:O(1)
最坏情况时间复杂度:O(n^2)
最好情况时间复杂度:O(n^2)
平均时间复杂度:O(n^2)
不稳定的排序方法
- 运行时间与输入无关。元素比较的次数与序列的初始状态无关，始终是n(n-1)/2。
- 每一趟排序会将一个元素放置到最终的位置上。
- 数据移动是最少的。
4、快速排序
public class QuickSort extends BaseSort {@Overridepublic void sort(Comparable[] a) {sort(a,0,a.length-1);}private void sort(Comparable[] a, int lo, int hi){if(hi<=lo)return;int j = partition(a,lo,hi); //切分元素sort(a,lo,j-1); //对左半部分切分sort(a,j+1,hi); //对右半部分切分}private int partition(Comparable[] a, int lo, int hi) {int i = lo, j = hi+1; //左右扫描指针Comparable v = a[lo]; //第一个作为切分元素while(true){//找到左边比切分元素大的while(less(a[++i],v))if(i==hi)break;//找到右边比切分元素小的while(less(v,a[--j]))if(j==lo)break;if(i>=j)break;//交换他们的值exch(a,i,j);}//最后把切分元素放到中间exch(a,lo,j);return j;}
}性能分析:
空间复杂度:O(k)
最坏情况时间复杂度:O(n^2)
最好情况时间复杂度:O(nlogn)
平均时间复杂度:O(nlogn)
不稳定的排序方法
优化:
- 在递归的过程中划分得到的子序列规模较小的时候采用插入排序进行后续的排序工作
- 尽量选取一改可以将数据中分的元素。从序列的头尾以及中间选取三个元素，再取三个元素的中间值或者随机从当前表中选取元素。
快速排序是所以内部排序算法中平均性能最优的排序算法。
5、堆排序
public class PQSort extends BaseSort {@Overridepublic void sort(Comparable[] a) {int N = a.length-1;//构造一个堆for(int k = N/2; k >= 1; k--)sink(a,k,N);//下沉排序while(N>1){exch(a,1,N--);//找到最大值，放最后面sink(a,1,N); //重新恢复堆的有序性}}private void sink(Comparable[] a, int k, int N) {//若k*2大于N则跳出循环，证明已经没有左右子树了while(k*2<=N){int j = k*2;//找到最大的左右子结点if(j1]))j++;//如果比左右结点都大，则跳出循环if(!less(a[k],a[j]))break;//交换结点exch(a,k,j);k = j;} }
} 优先队列
| 数据结构 | 插入元素 | 删除最大元素 |
|---|---|---|
| 有序数组 | N | 1 |
| 无序数组 | 1 | N |
| 堆 | logN | logN |
6、归并排序
public class MergeSort extends BaseSort {private static Comparable[] aux; //归并所需的辅助数组@Overridepublic void sort(Comparable[] a) {// TODO Auto-generated method stub aux = new Comparable[a.length];sort(a,0,a.length-1);}private void sort(Comparable[] a, int lo, int hi){if(hi<=lo)return;int mid = lo+(hi-lo)/2;//先把左半部分排好序sort(a,lo,mid);//先把右半部分排好序sort(a,mid+1,hi);//归并merge(a,lo,mid,hi);}//归并前，左半部分和右半部分都要是有序的private void merge(Comparable[] a, int lo, int mid, int hi){int i = lo;int j = mid+1;//复制到另一个数组for(int k = lo; k <= hi; k++){aux[k] = a[k];}for(int k = lo;k<=hi;k++){//左边用尽，取右边的元素if(i>mid)a[k]=aux[j++];//右边用尽，去左边的元素else if(i>hi)a[k] = aux[i++];//去较小的那一边的元素else if(less(aux[j],aux[i]))a[k] = aux[j++];elsea[k] = aux[i++];}}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！