本文共 1340 字，大约阅读时间需要 4 分钟。

排序（一）

简介

在实际应用当中，我们经常会用到数组这个结构。而我们经常使用的是数字的数组，而他确实经常乱序。所以我们如何使得我们的数组有序呢？这就运用到我们的排序算法。

插入排序

插入排序是最简单的排序算法，他的时间复杂度是n²。

它的基本思想是保证从位置0到位置p的数字已经是已排序状态。

算法实现：

public class insertSort
   
    > {
       public insertSort(AnyType[] a){
           int j;        for (int i = 1; i 
    
     0&&temp.compareTo(a[j-1])<0;j--)                a[j]=a[j-1];            a[j]=temp;        }    }}
    
   

堆排序

像我们之间讲堆的时候，我们建立一个堆花费n的时间，然后我们执行n次deleteMin方法，再将其进行拷贝得到N个元素。deleteMin花费的时间是logN，所以他们一组合就是N logN

二叉堆点

代码实现

public ArrayList
   
     heapSort(){
           ArrayList
    
      list=new ArrayList<>();        while (!isEmpty())            list.add(deleteMin());        return list;    }
    
   

归并排序

归并排序也就是合并两个已排序的表，花费的最坏时间是N logN。看图

我们可以把最后要合并的两个有序表使用递归实现，递归到最后发现是俩个开始比较然后顺序放置，再与下一个开始比较合并直至最后整的合并。

就像这个图，我们要实现这几个数字的归并排序，我们把他拆分为两个以中间为准，分而治之。

下一个也一样，就看左半部分5，4，22，他要开始归并也是从中间划分，左半部分5，4和右半部分22分开进行。进入5，4这个，4比5小则在暂时的表当中放置4，然后再放置5，再返回到上面，放入22.依次返回。 算法实现

public class MergeSort {
       private int[] myArray;    private int[] tempArray;    public MergeSort(int[] a){
           this.myArray=a;        this.tempArray=new int[a.length];    }    public int[] getSort(){
           mergeSort(0,myArray.length-1);        return myArray;}    //递归实现归并，运用分治的思想进行    private void mergeSort(int left,int right){
           int center=(left+right)/2;//获得中间位置        if(left

转载地址：http://wgqai.baihongyu.com/