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

本文以对整形数组升序排序为例，列举了排序的几种算法及相应的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;

}

 

7、归并排序

基本思路：设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。

为了减少数据移动次数，不妨采用一个临时工作数组C，将中间排序结果暂时保存在C数组中，等归并结束后，再将C数组值复制给A。

实现：

void sort(int a[]) throws Exception {

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

}

 

private void merge(int a[], int begin, int m, int end) throws Exception {

int i = begin, j = m + 1, k = 0;

int[] tmp = new int[end - begin + 1];

while (i <= m && j <= end) {           

    if (a > a[j]) {

        tmp[k++] = a[j++];

    } else {

        tmp[k++] = a[i++];

    }

}

if (i == m + 1) {

    for (; j <= end; j++) {            

        tmp[k++] = a[j];

    }

} else {

    for (; i <= m; i++) {              

        tmp[k++] = a;

    }

}

for (k = 0; k < tmp.length; k++) {

    a[begin + k] = tmp[k];

}

}

 

private void mergesort(int a[], int begin, int end) throws Exception {

if (end - begin > 0) {

    int m = (end - begin) / 2;

    mergesort(a, begin, begin + m);

    mergesort(a, begin + m + 1, end);

    merge(a, begin, begin + m, end);

}

}

 

 

性能比较

		时间复杂度	空间复杂度	稳定
1	插入排序	O(n2)	1	√
2	希尔排序	O(n2)	1	×
3	冒泡排序	O(n2)	1	√
4	选择排序	O(n2)	1	×
5	快速排序	O(Nlogn)	O(logn)	×
6	堆排序	O(Nlogn)	1	×
7	归并排序	O(Nlogn)	O(n)	√