归并排序

动画过程演示

MergeSort.gif

算法的基本实现

使用递归的方式，将数据进行分割分割

图解

图解

代码实现

private void MergeSortFunc(Comparable[] array, int l, int r) {
    //递归首先要考虑归并到底的情况
  if (l>=r){
        return;
  }
    int mid=(l+r)/2;          //如果l和r都是比较大的话，会产生溢出
  MergeSortFunc(array,l,mid);
  MergeSortFunc(array,mid+1,r);
}

向上进行归并(也就是把当前区间里的数据按照从大到小或者从小到大的顺序进行排列)

图解

图解

代码实现

//array[l,mid]和array[mid,r]两部分进行归并
private void mergeFunc(Comparable[] array, int l, int mid, int r) {
    Comparable[] aux = Arrays.copyOfRange(array,l,r+1); //声明一个用来归并的数组
 int i=l,j=mid+1;
 for (int k = l; k <= r; k++) {
        if (i>mid){       //i大于mid，说明左边的已经完成填充，这时只需要填充右边的数据
            array[k]=aux[j-l];
            j++;
         }else if (j>r){   //右边填充完成
            array[k]=aux[i-l];
            i++;
       }else if (aux[i-l].compareTo(aux[j-l])<0){
            array[k]=aux[i-l];
            i++;
       }else {
            array[k]=aux[j-l];
            j++;
       }
    }

}

算法的优化

• 如果面对的数据是相对有序的时候，有时候在MergeSortFunc加一个判断可以带来性能上的轻微提高。
• 原理是十分简单的，因为i到mid是有序的，mid+1到r是有序的，那么如果mid<mid+1 则表示本身就是有序的

 if( arr[mid].compareTo(arr[mid+1]) > 0 )
        merge(arr, l, mid, r);

---

快速排序

动画过程演示

QuickSort.gif

算法的基本实现

确定一个基值，如图中我们将第一个数字作为基础值

Comparable v=array[l];

将把比基值大的全部放在一边，把比基值小的放在另一边

int j=l;
 for (int i = l+1; i <=r ; i++) {
            if (array[i].compareTo(v)<0){
                j++;
  Utils.swap(array,j,i);
  }
// 更加优雅的写法
//            if (array[i].compareTo(v)<0){
//                Utils.swap(array,++j,i);
//            }
  }

将基值放在正确的位置

Utils.swap(array,l,j);
return j; //为p值，用来对当前数组进行分割使用

将比基值大的数据和比基值小的数据，再次进行快速排序

private void quickSort(Comparable[] array, int l, int r) {
        //递归到底
        if (l>=r){
            return;
        }

  int p=partition(array,l,r);    //这个值就是上面返回的索引值
  quickSort(array,l,p-1);
  quickSort(array,p+1,r);
  }

全部代码

public class QuickSort implements ISortAlg{
  @Override
  public void Sort(Comparable[] array) {
        quickSort(array,0,array.length-1);
  }

    private void quickSort(Comparable[] array, int l, int r) {
        //递归到底
        if (l>=r){
            return;
        }

  int p=partition(array,l,r);
  quickSort(array,l,p-1);
  quickSort(array,p+1,r);
  }

  private int partition(Comparable[] array, int l, int r) {
  Comparable v=array[l];
  //array[l+1...j]<v;array[j+1...i)>v
  int j=l;
 for (int i = l+1; i <=r ; i++) {
        if (array[i].compareTo(v)<0){
                j++;
                Utils.swap(array,j,i);
           }
  }
Utils.swap(array,l,j);
 return j; //为p
  }

优化

1.当递归快要结束的时候，也就是说快要排序完成的时候，采用插入排序法效率更高。在quickSort中加入如下代码

if(r-l<=15) {
    BatterInstallSortAlg.batterSort(array, l, r);
    return;
 }

2.当需要排序的数组是趋近于有序的时候，快速排序的速度明显慢于归并排序，原因是因为快速排序递归调用分开的数据是十分不平衡的，导致排序算法的退化。解决方法是随机取得基值.在partition加入如下代码

Random random=new Random();
Utils.swap(array,l,random.nextInt(r-l+1)+l);

3.当数组出现大量相同的数据，快排也会退化成n^2级别的算法，解决方法是将等于基值的数据，分在大于基值和等于基值两边。改写partition

while (true){
    while (i<=r && array[i].compareTo(v)<0) i++;
    while (j>=l+1 && array[j].compareTo(v)>0) j--;
    if (j<i)
        break;
     Utils.swap(array,i,j);
      i++;
      j--;
}

4.另一种解决方法就是将算法写成三路排序（一路是大于基值，一路小于基值，另一路是等于基值）

实现

public void Sort(Comparable[] array) {
    Random random=new Random(47);
  quickSortThreeWay(array,0,array.length-1);
}

private void quickSortThreeWay(Comparable[] array, int l, int r) {
    if (r-l<=15) {
        BatterInstallSortAlg.batterSort(array, l, r);
 return;  }
    int lt=l;//[l+1,lt]<v
  int gt=r+1;//[gt,r]>v
  int i=l+1;//[l+1,i]==v
  Comparable v=array[l];
 while (i<gt){
        if (array[i].compareTo(v)<0){
            Utils.swap(array,i,lt+1);
            lt++;
            i++;
         }else if (array[i].compareTo(v)>0){
            Utils.swap(array,i,gt-1);
            gt--;
           }else {
            i++;
          }
    }
    Utils.swap(array,l,lt);
    quickSortThreeWay(array,l,lt-1);
    quickSortThreeWay(array,gt,r);
}

小结

• 快速排序相对与归并排序在大多数场合速度更快
• 快速排序在一些特殊场合速度，需要特殊优化