Java常用排序算法及性能测试集合

现在再回过头理解,结合自己的体会, 选用最佳的方式描述这些算法,以方便理解它们的工作原理和程序设计技巧。本文适合做java面试准备的材料阅读。

先附上一个测试报告:

Array length: 20000
bubbleSort : 766 ms
bubbleSortAdvanced : 662 ms
bubbleSortAdvanced2 : 647 ms
selectSort : 252 ms
insertSort : 218 ms
insertSortAdvanced : 127 ms
insertSortAdvanced2 : 191 ms
binaryTreeSort : 3 ms
shellSort : 2 ms
shellSortAdvanced : 2 ms
shellSortAdvanced2 : 1 ms
mergeSort : 3 ms
quickSort : 1 ms
heapSort : 2 ms

通过测试,可以认为,冒泡排序完全有理由扔进垃圾桶。它存在的唯一理由可能是最好理解。希尔排序的高效性是我没有想到的;堆排序比较难理解和编写,要有宏观的思维。

代码如下:

package algorithm.sort;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Date;

/**
 * Java常用排序算法及性能测试集合
 *
 * 本程序集合涵盖常用排序算法的编写,并在注释中配合极其简单的特例讲解了各种算法的工作原理,以方便理解和吸收;
 * 程序编写过程中吸收了很多维基百科和别人blog上面的例子,并结合自己的思考,选择并改进一个最容易让人理解的写法
 *(尤其是快速排序,我觉得我写的算法最好理解)。
 * 同时包含一个集中式的性能测试和正确性测试方法,方便观测。
 * @author /link.php?url=http://blog.csdn.net/sunxing007
 * 转载请注明来自/link.php?url=http://blog.csdn.net/sunxing007
 */
public class SortUtil {
 // 被测试的方法集合
 static String[] methodNames = new String[]{
  "bubbleSort",
  "bubbleSortAdvanced",
  "bubbleSortAdvanced2",
  "selectSort",
  "insertSort",
  "insertSortAdvanced",
  "insertSortAdvanced2",
  "binaryTreeSort",
  "shellSort",
  "shellSortAdvanced",
  "shellSortAdvanced2",
  "mergeSort",
  "quickSort",
  "heapSort"
 };
    public static void main(String[] args) throws Exception{
     //correctnessTest();
     performanceTest(20000);
    }

/**
     * 正确性测试<br>
     * 简单地测试一下各个算法的正确性<br>
     * 只是为了方便观测新添加的算法是否基本正确;<br>
     * @throws Exception 主要是反射相关的Exception;<br>
     */
    public static void correctnessTest() throws Exception{
     int len = 10;
     int[] a = new int[len];
     for(int i=0; i<methodNames.length; i++){
      for(int j=0; j<a.length; j++){
          a[j] = (int)Math.floor(Math.random()*len*2);
         }
      Method sortMethod = null;
      sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
      Object o = sortMethod.invoke(null, a);
      System.out.print(methodNames[i] + " : ");
      if(o==null){
       System.out.println(Arrays.toString(a));
      }
      else{
       //兼顾mergeSort,它的排序结果以返回值的形式出现;
       System.out.println(Arrays.toString((int[])o));
      }
     }
    }

/**
     * 性能测试<br>
     * 数组长度用参数len传入,每个方法跑20遍取耗时平均值;<br>
     * @param len 数组长度 建议取10000以上,否则有些算法会显示耗时为0;<br>
     * @throws Exception 主要是反射相关的Exception;<br>
     */
    public static void performanceTest(int len) throws Exception{
     int[] a = new int[len];
     int times = 20;

System.out.println("Array length: " + a.length);
     for(int i=0; i<methodNames.length; i++){
      Method sortMethod = null;
      sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
      int totalTime = 0;
      for(int j=0; j<times; j++){
       for(int k=0; k<len; k++){
           a[k] = (int)Math.floor(Math.random()*20000);
          }
       long start = new Date().getTime();
       sortMethod.invoke(null, a);
       long end = new Date().getTime();
       totalTime +=(end-start);
      }
      System.out.println(methodNames[i] + " : " + (totalTime/times) + " ms");
      //System.out.println(Arrays.toString(a));
     }
    }

/**
     * 最原始的冒泡交换排序;<br>
     * 两层遍历,外层控制扫描的次数,内层控制比较的次数;<br>
     * 外层每扫描一次,就有一个最大的元素沉底;所以内层的比较次数将逐渐减小;<br>
     */
    public static void bubbleSort(int[] a){
        for(int i=0; i<a.length; i++){
            for(int j=0; j<a.length-i-1; j++){
                if(a[j]>a[j+1]){
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
    }

/**
     * 改进的冒泡法<br>
     * 改进之处在于:设一个标志位,如果某趟跑下来,没有发生交换,说明已经排好了;<br>
     */
    public static void bubbleSortAdvanced(int[] a){
        int k = a.length-1;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int i=0;i<k;i++){
                if(a[i]>a[i+1]){
                    int tmp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = tmp;
                    //有交换则继续保持标志位;
                    flag = true;
                }
            }
            k--;
        }
    }

/**
     * 改进的冒泡法2<br>
     * 改进之处在于吸收上面的思想(没有交换意味着已经有序),如果局部的已经是有序的,则后续的比较就不需要再比较他们了。<br>
     * 比如:3142 5678,假如刚刚做完了2和4交换之后,发现这趟比较后续再也没有发生交换,则后续的比较只需要比到4即可;<br>
     * 该算法就是用一个标志位记录某趟最后发生比较的地点;<br>
     */
    public static void bubbleSortAdvanced2(int[] a){
        int flag = a.length - 1;
        int k;
        while(flag>0){
            k = flag;
            flag = 0;
            for(int i=0; i<k; i++){
                if(a[i] > a[i+1]){
                    int tmp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = tmp;
                    //有交换则记录该趟最后发生比较的地点;
                    flag = i+1;
                }
            }
        }
    }

/**
     * 插入排序
     *
     * 关于插入排序,这里有几个约定,从而可以快速理解算法:<br>
     * i: 无序表遍历下标;i<n-1;<br>
     * j: 有序表遍历下表;0<=j<i;<br>
     * a[i]:表示当前被拿出来做插入排序的无序表头元素;<br>
     * a[j]:有序表中的任意元素;<br>
     * <br>
     * 算法关键点:把数组分割为a[0~i-1]有序表,a[i~n-1]无序表;每次从无序表头部取一个,<br>
     * 把它插入到有序表适当的位置,直到无序表为空;<br>
     * 初始时,a[0]为有序表,a[1~n-1]为无序表;<br>
     */
    public static void insertSort(int[] a){
        //从无序表头开始遍历;
        for(int i=1; i<a.length; i++){
            int j;
            //拿a[i]和有序表元素依次比较,找到一个恰当的位置;
            for(j=i-1;j>=0; j--){
                if(a[j] < a[i]){
                    break;
                }
            }
            //如果找到恰当的位置,则从该位置开始,把元素朝后移动一格,为插入的元素腾出空间;
            if(j!=(i-1)){
                int tmp = a[i];
                int k;
                for(k = i-1; k>j;k--){
                    a[k+1] = a[k];
                }
                a[k+1] = tmp;
            }
        }
    }

/**
     * 改进的插入排序1
     * 改进的关键在于:首先拿无序表头元素a[i]和有序表尾a[i-1]比较,
     * 如果a[i]<a[i-1],说明需要调整;调整的过程为:
     * 从有序表尾开始,把有序表里面比a[i]大的元素都朝后移动,直到找到恰当的位置;
     */
    public static void insertSortAdvanced(int[] a){
        //遍历无序表;
        for(int i=1; i<a.length; i++){
            //如果无序表头元素小于有序表尾,说明需要调整;
            if(a[i]<a[i-1]){
                int tmp = a[i];
                int j;
                //从有序表尾朝前搜索并比较,并把大于a[i]的元素朝后移动以腾出空间;
                for(j=i-1; j>=0&&a[j]>tmp;j--){
                    a[j+1] = a[j];
                }
                a[j+1] = tmp;
            }
        }
    }

/**
     * 改进的插入排序2
     * 总体思想和上面相似,拿无序表头元素从有序表尾元素开始朝前比较,
     * 如果a[i]比a[i-1]小,则把a[i]从有序表尾用冒泡交换的方式朝前移动,直到到达恰当的位置;
     */
    public static void insertSortAdvanced2(int[] a){
        //遍历无序表
        for(int i=1; i<a.length; i++){
            //拿a[i]从有序表尾开始冒泡;
            for(int j=i-1; j>=0 && a[j] > a[j+1]; j--){//a[j+1]就是a[i]
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }

/**
     * 快速排序<br>
     * 算法的思想在于分而治之:先找一个元素(一般来说都是数组头元素),把比它大的都放到右边,把比它小的都放到左边;<br>
     * 然后再按照这样的思想去处理两个子数组; 下面说的子数组头元素通指用来划分数组的元素;<br>
     * <br>
     * 下面程序关键点就在于!forward, low0++, high0--这些运算; 这三个运算使得a[low0],a[high0]里面总有一个指向子数组头元素; <br>  
     * 可以用极端的情况来方便理解这三个值的运作: <br>
     * 假如我的数列为0123456789, 初始时forward=false,0作为子数组划分依据,很显然第一轮的时候不会发生任何交换,low0一直指向0,<br>
     * high0逐渐下降直到它指向0为止; 同理可思考9876543210这个例子;<br>
     * <br>
     * @param a 待排序数组<br>
     * @param low 子数组开始的下标;<br>
     * @param high 子数组结束的下标;<br>
     */
    public static void quickSort(int[] a, int low, int high){
        if(low>=high){
            return;
        }
        int low0 = low;
        int high0 = high;
        boolean forward = false;
        while(low0!=high0){
            if(a[low0]>a[high0]){
                int tmp = a[low0];
                a[low0] = a[high0];
                a[high0] = tmp;
                forward = !forward;
            }
            if(forward){
                low0++;
            }
            else{
                high0--;
            }
        }
        low0--;
        high0++;
        quickSort(a, low, low0);
        quickSort(a, high0, high);
    }

/**
     * 快速排序的简单调用形式<br>
     * 方便测试和调用<br>
     * @param a
     */
    public static void quickSort(int[] a){
     quickSort(a, 0, a.length-1);
    }

/**
     * 归并排序<br>
     * 所谓归并,就是合并两个有序数组;归并排序也用了分而治之的思想,把一个数组分为若干个子数组;<br>
     * 当子数组的长度为1的时候,则子数组是有序的,于是就可以两两归并了;<br>
     * <br>
     * 由于归并排序需要分配空间来转储归并的结果,为了算法上的方便,归并算法的结果以返回值的形式出现;<br>
     */

/**
     * 合并两个有序数组
     * @param a 有序数组1
     * @param b 有序数组2
     * @return 合并之后的有序数组;
     */
    public static int[] merge(int[] a, int[] b){
     int result[] = new int[a.length+b.length];
     int i=0,j=0,k=0;
     while(i<a.length&&j<b.length){
      if(a[i]<b[j]){
       result[k++] = a[i];
       i++;
      }
      else{
       result[k++] = b[j];
       j++;
      }
     }
     while(i<a.length){
      result[k++] = a[i++];
     }
     while(j<b.length){
      result[k++] = b[j++];
     }
     return result;
    }

/**
     * 归并排序<br>
     * 把数组从中间一分为二,并对左右两部分递归调用,直到数组长度为1的时候,开始两两归并;<br>
     * @param 待排序数组;
     * @return 有序数组;
     */
    public static int[] mergeSort(int[] a){
     if(a.length==1){
      return a;
     }
     int mid = a.length/2;
     int[] leftPart = new int[mid];
     int[] rightPart = new int[a.length-mid];
     System.arraycopy(a, 0, leftPart, 0, leftPart.length);
     System.arraycopy(a, mid, rightPart, 0, rightPart.length);
     leftPart = mergeSort(leftPart);
     rightPart = mergeSort(rightPart);
     return merge(leftPart, rightPart);
    }

/**
     * 选择排序<br>
     * 和插入排序类似,它也把数组分割为有序区和无序区,所不同的是:<br>
     * 插入排序是拿无序区的首元素插入到有序区适当的位置,而<br>
     * 选择排序是从无序区中挑选最小的放到有序区最后;<br>
     * <br>
     * 两层循环,外层控制有序区的队尾,内层用来查找无序区最小元素;<br>
     * @param a
     */
    public static void selectSort(int[] a){
     for(int i=0; i<a.length; i++){
      int minIndex = i;
      for(int j=i+1; j<a.length; j++){
       if(a[j]<a[minIndex]){
        minIndex = j;
       }
      }
      int tmp = a[i];
      a[i] = a[minIndex];
      a[minIndex]= tmp;
     }
    }

/**
     * 希尔排序<br>
     * 其思想是把数组按等步长(/间距)划分为多个子序列,对各个子序列做普通的插入排序,<br>逐次降低步长,直到为1的时候最后再做一次普通的插入排序;
     * 用一个极端的例子作比方,我有数列如下:<br>
     * [1,2,3,4,5,6,7,8,9,10];<br>
     * 初始的时候,步长gap=5;则划分的子数组为[1,6], [2,7], [3,8], [4,9], [5,10];<br>对他们分别排序(当然由于本数组特殊,所以结果是不变的);<br>
     * 然后gap=2=5/2; 子数组为[1,3,5,7,9], [2,4,6,8,10]; <br>
     * 最后gap=1=2/2; 做一次全局排序;<br>
     * <br>
     * 希尔排序克服了插入/冒泡排序的弱点(一次只能把元素移动一个相邻的位置), <br>依靠大步长,可以把元素尽快移动到目标位置(或附近);<br>
     * 希尔排序实际上是插入排序的变种。它适用于:当数组总体有序,个别需要调整的情况;这时候利用插入排序的优势,可以达到O(n)的效率;<br>
     * 影响希尔算法的一个重要的因素是步长选择,一个好步长的优点是:后面的短步长排序不会破坏前面的长步长排序;<br>
     * 怎么理解这种破坏呢?前面的长步长把一个较小的数移到了左面,但是在缩小步长之后有可能又被交换到了右面 (因为它被分到了一个有很多比它更小的组);<br>
     * 关于步长,可以查看http://zh.wikipedia.org上面关于希尔排序的页面;<br>
     * 下面的程序是希尔排序最基础的写法,适合用来理解希尔排序思想;<br>
     */
    public static void shellSort(int[] a){
     // 控制间距;间距逐渐减小,直到为1;
     for(int gap = a.length/2; gap>0; gap/=2){
      // 扫描每个子数组
      for(int i=0; i<gap; i++){
       // 对每个字数组,扫描无序区;注意增量;
       // a[i]是初始有序区;
       for(int j=i+gap; j<a.length; j+=gap){
        // 无序区首元素小于有序区尾元素,说明需要调整
        if(a[j]<a[j-gap]){
         int tmp = a[j];
         int k = j-gap;
         //从有序区尾向前搜索查找适当的位置;
         while(k>=0&&a[k]>tmp){
          a[k+gap] = a[k];
          k-=gap;
         }
         a[k+gap] = tmp;
        }
       }
      }
     }
    }

/**
     * 改进的希尔排序<br>
     * 改进之处在于:上面的写法用一个for循环来区别对待每个字数组;而实际上是不必要的;<br>
     * a[0,1,...gap-1]作为所有子数组的有序区,a[gap,...n-1]作为所有字数组的无序区;<br>
     * <br>
     * 该改进在时间效率上没有改进;只是让程序看起来更简洁;<br>
     * @param a
     */
    public static void shellSortAdvanced(int[] a){
     // 控制步长
     for(int gap = a.length/2; gap>0; gap/=2){
      // 从无序区开始处理,把多个子数组放在一起处理;
      for(int j=gap; j<a.length; j++){
       // 下面的逻辑和上面是一样的;
       if(a[j]<a[j-gap]){
        int tmp = a[j];
        int k = j-gap;
        while(k>=0&&a[k]>tmp){
         a[k+gap] = a[k];
         k-=gap;
        }
        a[k+gap] = tmp;
       }
      }
     }
    }

/**
     * 改进的希尔排序2<br>
     * 在吸收shellSortAdvanced思想的基础上,采用insertAdvanced2的做法;<br>即无序区首元素通过朝前冒泡的形式移动的适当的位置;<br>
     * @param a
     */
    public static void shellSortAdvanced2(int[] a){
     for(int gap = a.length/2; gap>0; gap/=2){
      for(int i=gap; i<a.length; i++){
       if(a[i]<a[i-gap]){
        for(int j=i-gap; j>=0&&a[j+gap]>a[j]; j-=gap){
         int tmp = a[j];
         a[j] = a[j+gap];
         a[j+gap] = tmp;
        }
       }
      }
     }
    }

/**
     * 堆排序<br>
     * 堆的定义:堆是一个完全,或近似完全的二叉树,堆顶元素的值大于左右孩子的值,左右孩子也需要满足这个条件;<br>
     * 按照堆的定义,堆可以是大顶堆(maxHeap),或小顶堆(minHeap);<br>
     * 一般用数组即可模拟二叉树,对于任意元素i,左孩子为2*i+1,右孩子为2*i+2;父节点为(i-1)/2;
     * @param a
     */
    public static void heapSort(int[] a){

// 先从最后一个非叶子节点往上调整,使满足堆结构;
     for(int i=(a.length-2)/2; i>=0; i--){
      maxHeapAdjust(a, i, a.length);
     }
     // 每次拿最后一个节点和第一个交换,然后调整堆;直到堆顶;
     for(int i=a.length-1; i>0; i--){
      int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
      maxHeapAdjust(a, 0, i);
     }
    }

/**
     * 调整堆<br>
     * 把以i为跟节点的二叉树调整为堆;<br>
     * 可以这么来思考这个过程:这个完全二叉树就像一个金字塔,塔顶的小元素沿着树结构,往下沉降;<br>
     * 调整的结果是最大的元素在金字塔顶,然后把它从堆中删除(把它交换到堆尾,然后堆收缩一格);<br>
     * 堆排序快的原因就是根据二叉树的特点,一个节点要沉降到合适的位置,只需要logn步;同时前期调整的结果(大小顺序)会被记录下来,从而加快后续的调整;<br>
     * @param a 待排数组
     * @param i 堆顶
     * @param len 堆长度
     */
    public static void maxHeapAdjust(int[] a, int i, int len){
     int tmp = a[i];
     // j是左孩子节点
     int j = i*2+1;
     //
     while(j<len){
      // 从左右孩子中挑选大的
      // j+1是右孩子节点
      if((j+1)<len && a[j+1]>a[j]){
       j++;
      }
      // 找到恰当的位置就不再找
      if(a[j]<tmp){
       break;
      }
      // 否则把较大者沿着树往上移动;
      a[i] = a[j];
      // i指向刚才的较大的孩子;
      i = j;
      // j指向新的左孩子节点;
      j = 2*i + 1;
     }
     // 把要调整的节点值下沉到适当的位置;
     a[i] = tmp;
    }

/**
     * 二叉树排序<br>
     * 二叉树的定义是嵌套的:<br>节点的值大于左叶子节点的值,小于右叶子节点的值;叶子节点同样满足这个要求;<br>
     * 二叉树的构造过程就是排序的过程:<br>
     * 先构造跟节点,然后调用add方法添加后续节点为跟节点的子孙节点;这个过程也是嵌套的;<br>
     * <br>
     * 中序遍历二叉树即得到有序结果;<br>
     * 二叉树排序用法特殊,使用情形要视情况而定;<br>
     * @param a
     */
    public static void binaryTreeSort(int[] a){
     // 构造一个二叉树节点内部类来实现二叉树排序算法;
     class BinaryNode{
      int value;
      BinaryNode left;
      BinaryNode right;

public BinaryNode(int value){
       this.value = value;
       this.left = null;
       this.right = null;
      }

public void add(int value){
       if(value>this.value){
        if(this.right!=null){
         this.right.add(value);
        }
        else{
         this.right = new BinaryNode(value);
        }
       }
       else{
        if(this.left!=null){
         this.left.add(value);
        }
        else{
         this.left = new BinaryNode(value);
        }
       }
      }
      /**
       * 按中序遍历二叉树,就是有序的。
       */
      public void iterate(){
       if(this.left!=null){
        this.left.iterate();
       }
       // 在测试的时候要把输出关掉,以免影响性能;
       // System.out.print(value + ", ");
       if(this.right!=null){
        this.right.iterate();
       }
      }
     }

BinaryNode root = new BinaryNode(a[0]);
     for(int i=1; i<a.length; i++){
      root.add(a[i]);
     }
     root.iterate();
    }
}

(0)

相关推荐

  • java实现的冒泡排序算法示例

    本文实例讲述了java实现的冒泡排序算法.分享给大家供大家参考,具体如下: public class PaoPaixu { public static void sort(int[] data){ int tmp; for (int i = 0; i < data.length; i++) { for (int j = i+1; j < data.length; j++) { if(data[i]>data[j]){ /*tmp=data[i]; data[i]=data[j]; dat

  • 用java实现冒泡排序算法

    冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止. 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序. 复制代码 代码如下: public class BubbleSort implements SortUtil.Sort{ public void sort(int[] data) { int temp; for(int i=0;i<data.length;i++){ for(int j=data.le

  • java冒泡排序算法代码

    复制代码 代码如下: /** * 原理: * 进行n次循环,每次循环从后往前对相邻两个元素进行比较,小的往前,大的往后 *  * 时间复杂度: * 平均情况:O(n^2) * 最好情况:O(n) * 最坏情况:O(n^2) * * 稳定性:稳定 **/public class 冒泡排序 { public int[] bubbleSort(int[] a, int n) {        for (int i = 0; i < n; i++) {            int flag = 0; 

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • Java实现快速排序算法(Quicktsort)

    快速排序算法介绍快速排序和归并排序都使用分治法来设计算法,区别在于归并排序把数组分为两个基本等长的子数组,分别排好序之后还要进行归并(Merge)操作,而快速排序拆分子数组的时候显得更有艺术,取一个基准元素,拆分之后基准元素左边的元素都比基准元素小,右边的元素都不小于基准元素,这样只需要分别对两个子数组排序即可,不再像归并排序一样需要归并操作.基准元素的选取对算法的效率影响很大,最好的情况是两个子数组大小基本相当.为简单起见,我们选择最后一个元素,更高级的做法可以先找一个中位数并把中位数与最后一

  • 十种JAVA排序算法实例

    排序算法有很多,所以在特定情景中使用哪一种算法很重要.为了选择合适的算法,可以按照建议的顺序考虑以下标准: (1)执行时间 (2)存储空间 (3)编程工作  对于数据量较小的情形,(1)(2)差别不大,主要考虑(3):而对于数据量大的,(1)为首要. 一.冒泡(Bubble)排序 复制代码 代码如下: void BubbleSortArray() {       for(int i=1;i<n;i++)       {         for(int j=0;i<n-i;j++)       

  • Java中常用的6种排序算法详细分解

    排序算法很多地方都会用到,近期又重新看了一遍算法,并自己简单地实现了一遍,特此记录下来,为以后复习留点材料. 废话不多说,下面逐一看看经典的排序算法: 1. 选择排序 选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i-n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换.因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序.举个实例来看看: 初始: [38, 17, 16, 16, 7, 31, 39,

  • java实现折半排序算法

    折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中.由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度. public static void halfSort(int[] array) { int low, high, mid; int tmp, j; for (int i = 1; i < array.length; i++) { tm

  • java实现归并排序算法

    归并排序算法思想: 分而治之(divide - conquer);每个递归过程涉及三个步骤 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作 第三, 合并: 合并两个排好序的子序列,生成排序结果. public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < righ

  • JAVA简单选择排序算法原理及实现

    简单选择排序:(选出最小值,放在第一位,然后第一位向后推移,如此循环)第一位与后面每一个逐个比较,每次都使最小的置顶,第一位向后推进(即刚选定的第一位是最小值,不再参与比较,比较次数减1) 复杂度: 所需进行记录移动的操作次数较少 0--3(n-1) ,无论记录的初始排列如何,所需的关键字间的比较次数相同,均为n(n-1)/2,总的时间复杂度为O(n2):空间复杂度 O(1) 算法改进:每次对比,都是为了将最小的值放到第一位,所以可以一比到底,找出最小值,直接放到第一位,省去无意义的调换移动操作

  • java实现快速排序算法

    1.算法概念. 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出. 2.算法思想. 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3.实现思路. ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,-,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于

  • 浅析java 希尔排序(Shell)算法

    先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<:-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. 该方法实质上是一种分组插入方法. 原理图: 源代码 复制代码 代码如下: package com.zc.manythread; /**  *  * @author 偶my耶  *  *

  • 快速排序算法原理及java递归实现

    快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序.使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好.就平均时间而言,是目前被认为最好的一种内部排序方法 基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指

随机推荐