排序算法集锦分析

排序算法汇总分析

插入排序
插入排序是一种通过不断地把新元素插入到已排好序的数据中的排序算法，常用的插入排序算法包括直接插入排序和shell排序，直接插入排序实现比较简单，时间复杂度是O（n），但是直接插入没有充分的利用已插入的数据已经排序这个事实，因此有很多针对直接插入排序改进的算法，例如折半插入排序等，下边是直接插入排序的Java实现：

public static void insertSort(int[] elements){        for(int i = 1;i <elements.length; i++){            int j = -1;            while(j <= i && elements[i] > elements[++j]);//找到element[i]应该摆放的位置，此处可以利用查找算法进行优化            if(j < i){                //将j之后的数据移动一位，然后把elements[i]移动到j处                int temp = elements[i];                for(int k = i-1;k >= j;k--){                    elements[k+1] = elements[k];                }                elements[j] = temp;            }        }}

　　另一种常用的插入排序算法：Shell排序也是对直接插入排序算法的一种优化，因此可以说直接插入排序是一种特殊的Shell排序，Shell排序对直接插入排序的优化主要体现在，Shell排序通过使用一个增量序列（递减），每次把要排序的数组分成几个子数组，然后对子数组进行插入排序，这样可以减少比较和移动数据的次数，Shell排序是一种非常高效的排序算法，该算法的思想是：
　　1.以h（h一般取n/2）为间隔将n个元素列分为几个小组，在每个小组内按直接插入法排序
　　2.令h=h/2，重复第1步
　　3.当h=1时，排序结束（此时相当于直接插入排序，不过由于数据已经基本排好序，因此比较次数和移动次数比直接插入排序少很多）
　　Shell排序的Java实现如下：

public static void shellSort(int[] elements){        for(int h = elements.length/2;h > 0;h /= 2){                         for(int i = h;i < elements.length; i++){                int j = i % h;                while(j <= i && elements[i] > elements[j]) j += h;//找到element[i]应该摆放的位置                if(j < i){                    //将j之后的数据移动h位，然后把elements[i]移动到j处                    int temp = elements[i];                    for(int k = i-h;k >= j;k -= h){                        elements[k+h] = elements[k];                    }                    elements[j] = temp;                }            }                     }}

快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2)，最好情况时间复杂度为O(nlog2n)。

package src;public class QSort {/** * @param args */public static void main(String[] args) {// TODO 自动生成方法存根quicksort qs = new quicksort();int data[] = {44,22,2,32,54,22,88,77,99,11};qs.data = data;qs.sort(0, qs.data.length-1);qs.display();}}class quicksort{public int data[];private int partition(int sortArray[],int low,int hight){int key = sortArray[low];while(low<hight){while(low<hight && sortArray[hight]>=key)hight--;sortArray[low] = sortArray[hight];while(low<hight && sortArray[low]<=key)low++;sortArray[hight] = sortArray[low];}sortArray[low] = key;return low;}public void sort(int low,int hight){if(low<hight){int result = partition(data,low,hight);sort(low,result-1);sort(result+1,hight);}}public void display(){for(int i=0;i<data.length;i++){System.out.print(data[i]);System.out.print(" ");}}}

查看更多 下一篇