论坛首页 → Java企业应用论坛 →

几种排序算法介绍与性能分析

全部 Hibernate Spring Struts iBATIS 企业应用 Lucene SOA Java综合 Tomcat 设计模式 OO JBoss

浏览 3279 次

锁定老帖子主题：几种排序算法介绍与性能分析

该帖已经被评为隐藏帖

作者

正文

lgs0626
等级:
性别:
文章: 75
积分: 350
来自: 北京

发表时间：2011-12-07 最后修改：2011-12-08

相关推荐:

更多相关推荐

Java综合

本文以对整形数组升序排序为例，列举了排序的几种算法及相应的Java实现，并在本文最后给出这几种算法的性能分析图表。

1、插入排序

基本思路：在每次循环中把一个元素插入到已经排序的部分序列里的合适位置，使得到的序列仍然是有序的。

实现：

void sort(int a[]) throws Exception {

int tmp;

int j;

for (int i = 1; i <= a.length; i++) {

tmp = a;

           for (j = i - 1; j >= 0 && a[j] > tmp; j--) {

            a[j + 1] = a[j];

           }

           a[j + 1] = tmp;

         }

}

2、希尔排序

基本思路：任取一个小于n的整数S1作为增量，把所有元素分成S1个组。所有间距为S1的元素放在同一个组中。

第一组：{A[1]，A[S1+1]，A[2*S1+1]，……}

第二组：{A[2]，A[S1+2]，A[2*S1+2]，……}

第三组：{A[3]，A[S1+3]，A[2*S1+3]，……}

……

第s1组：{A[S1]，A[2*S1]，A[3*S1]，……}

先在各组内进行直接插人排序；然后，取第二个增量S2（<S1）重复上述的分组和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有记录放在同一组中进行直接插入排序为止。

实现：

void sort(int a[]) throws Exception {

int h[] = { 109, 41, 19, 5, 1 };

int tmp, j;

int incno;

for (tmp = 0; h[tmp] > a.length; tmp++);

for (incno = tmp; incno <= h.length - 1; incno++) {

for (int i = h[incno]; i <= a.length - 1; i++) {

tmp = a;

        for (j = i - h[incno]; j >= 0 && a[j] > tmp; j = j - h[incno]) {

            a[j + h[incno]] = a[j];

        }

        a[j + h[incno]] = tmp;

}

}

}

3、冒泡排序

基本思路：两两比较待排序的数据，发现两个数据的次序相反则进行交换，直到没有反序的数据为止。

实现：

void sort(int a[]) throws Exception {

for (int i = a.length; --i >= 0;){

for (int j = 0; j < i; j++) {

if (a[j] > a[j + 1]) {

int T = a[j];

a[j] = a[j + 1];

a[j + 1] = T;

}

4、选择排序

基本思路：从最后一个元素开始，从待排序的数据中选出记录最大元素位置，在将该元素同未排好顺序数列的最后一个元素交换位置，循环这个操作，直到全部数据排序完毕。

实现：

void sort(int a[]) throws Exception {

for (int i = a.length; --i >= 0;){

int largest=0;

for (int j = 1; j <= i; j++) {

if (a[largest] < a[j]) {

largest = j;

}

if (largest != i) {

int T = a[largest];

a[largest] = a;

a = T;

}

}

}

5、快速排序

基本思路：在A[1..n]中任取一个数据元素作为比较的“基准”（不妨记为X），将数据区划分为左右两个部分：A[1..i-1]和A[i+1..n]，且A[1..i-1]≤X≤A[i+1..n](1≤i≤n)，当A[1..i-1]和A[i+1..n]非空时，分别对它们进行上述的划分过程，直至所有数据元素均已排序为止。这个“基准”本实现采用数列中值

实现：

void quickSort(int a[], int low, int hig) throws Exception

{

int lo = low;

int hi = hig;

int mid;

if ( hig > low)

{

mid = a[ ( log + hiw ) / 2 ];

while( lo <= hi )

{

while( ( lo < hig ) && ( a[lo] < mid ) )

++lo;

while( ( hi > low ) && ( a[hi] > mid ) )

--hi;

if( lo <= hi )

{

swap(a, lo, hi);

++lo;

--hi;

}

if( low < hi )

quickSort( a, low, hi );

if( lo < hig )

quickSort( a, lo, hiw );

}

private void swap(int a[], int i, int j)

{

int T;

T = a;

a = a[j];

a[j] = T;

}

public void sort(int a[]) throws Exception

{

quickSort(a, 0, a.length - 1);

}

6、堆排序

基本思路：堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

实现：

void sort(int a[]) throws Exception {

int i;

for (i = a.length / 2; i >= 0; i--) {

perc_down(i, a, a.length - 1);

}

for (i = a.length - 1; i >= 0; i--) {

delete_max(i, a);

}

void delete_max(int ix, int a[]) throws Exception {

int ret;

ret = a[0];

a[0] = a[ix];

perc_down(0, a, ix - 1);

a[ix] = ret;

}

void perc_down(int ix, int a[], int lng) throws Exception {

int i, tmp;

tmp = a[ix];

i = ix;

while (i * 2 + 1 <= lng) {

if (i * 2 + 1 == lng || a[i * 2 + 1] > a[i * 2 + 2]) {

if (a[i * 2 + 1] < tmp)

break;

a = a[i * 2 + 1];

        i = i * 2 + 1;

    } else {

        if (a[i * 2 + 2] < tmp)

            break;

        a = a[i * 2 + 2];

        i = i * 2 + 2;

    }

}

a = tmp;

}