惯用排序算法-java实现（插入，快排）

常用排序算法-java实现（插入，快排）
1、插入排序算法

/** Simple insertion sort.* @param a an array of Comparable items.*/public static void insertionSort(Comparable[] a){    for(int p=1; p < a.length ;p++){        Comparable tmp = a[p];//临时变量        int j = p;        for(; j>0 && tmp.compareTo(a[j-1])< 0; j--)              a[j] = a[j-1];        a[j] = tmp;    }}

时间复杂度是：O(N*N)，如果输入被预先排序，运行时间将是O(N)。
算法思路：首先将需要插入排序的元素放入临时变量，然后将所有比它大的元素都向右移动一个位置，最后将临时变量复制进腾出的位置上。

2、快速排序

/**  Quicksort algorithm(driver).*/public static void quicksort( Comparable[] a ){     quicksort(a,0,a.length-1);}/** Internal quicksort method that makes recursive calls.* Uses median-of-three partitioning and a cutoff.* 使用三者取中拆分和小数组截断点的快速排序*/private static void quicksort(Comparable[] a , int low, int high){   if(low + CUTOFF > high )         insertionSort(a,low,high);//测试小数组，当问题小于CUTOFF给出特定值时用插                                   //入排序   else{       //对low, middle, high位置处的元素进行排序，然后将它们放在合适的位置。       int middle = ( low + high )/2;       if(a[middle].compareTo(a[low]) < 0 )           swap(a, low, middle);//交换low与middle的值       if(a[high].compareTo(a[low]) < 0 )           swap(a, low, high);       if(a[high].compareTo(a[middle]) < 0 )           swap(a, middle, high);       swap(a, middle , high-1);       Comparable pivot = a[high - 1];//支点的设置              int i,j;       for(i=low, j = high-1; ;){           while( a[++i].compareTo( pivot ) < 0 )             ;           while( pivot.compareTo( a[--j]) < 0 )             ;           if( i >= j)              break;           swap(a, i , j);       }        swap(a, i ,high-1);//确定支点的位置               quicksort(a, low, i-1);       quicksort(a, i+1, high);   }}

平均时间复杂度为O(N logN)

查看更多 下一篇