大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 各种排序算法的实现及其比较

各种排序算法的实现及其比较

关键词:排序算法各种排序算法的实现及其比较  阅读(643) 赞(20)

[摘要]本文主要是对各种排序算法的实现及其比较的讲解,希望对大家学习各种排序算法的实现及其比较有所帮助。

  本人介绍的排序算法主要有:插入排序,选择排序,冒泡排序,快速排序,堆排序,归并排序,希尔排序,二叉树排序,桶排序,基数排序(后两者为非比较排序,前面的为比较排序)。

  排序的稳定性和复杂度:

  不稳定:

  选择排序(selection sort)- O(n2)

  快速排序(quicksort)- O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序

  堆排序 (heapsort)- O(nlogn)

  希尔排序 (shell sort)- O(nlogn)

  基数排序(radix sort)- O(n·k); 需要 O(n) 额外存储空间 (K为特征个数)

  稳定:

  插入排序(insertion sort)- O(n2)

  冒泡排序(bubble sort) - O(n2)

  归并排序 (merge sort)- O(nlogn); 需要 O(n) 额外存储空间

  二叉树排序(Binary tree sort) - O(nlogn); 需要 O(n) 额外存储空间

  桶排序 (bucket sort)- O(n); 需要 O(k) 额外存储空间

  1、插入排序

  对于一个序列{a[0]……a[n]},当记录值是第i个元素时,前面i-1个元素已经排好序了,那么这个记录值从第i-1个元素一直往前比较,找到属于它的位置后插进去。

  1 #include <iostream>

  2 using  namespace std;

  3

  4 int main()

  5 {

  6     int a[]={1,99,2,88,3,77,4,66};

  7     int n=sizeof(a)/4;

  8     for(int i=0; i<n; i++)

  9     {

  10         int tp=a[i], j;

  11         for(j=i-1; j>=0&&a[j]>tp; j--) a[j+1]=a[j];

  12         a[j+1]=tp;

  13     }

  14     cout 《 a[0] ;

  15     for(int i=1; i<n; i++) cout 《 " " 《 a[i];

  16     cout 《endl;

  17     return 0;

  18 }

  2、选择排序

  对于一个序列{a[0]……a[n]},前面i-1个元素都是已经排好序的,那么从第i到第n个元素,找到最小值的那个元素,如果下标不是i,则让第i个元素和那个最小的元素位置互换。

  1 #include <iostream>

  2 using  namespace std;

  3

  4 int main()

  5 {

  6     int a[]={1,99,2,88,3,77,4,66};

  7     int n=sizeof(a)/4;

  8     for(int i=0; i<n; i++)

  9     {

  10         int pos=-1, minn=a[i];

  11         for(int j=i+1; j<n; j++)

  12         {

  13             if(a[j]<minn) minn=a[j], pos=j;

  14         }

  15         if(pos!=-1) swap(a[i],a[pos]);

  16     }

  17     cout 《 a[0] ;

  18     for(int i=1; i<n; i++) cout 《 " " 《 a[i];

  19     cout 《endl;

  20     return 0;

  21 }

  3、冒泡排序

  冒泡排序顾名思义就是从最后往前两个元素开始进行两两比较,如果a[i]小于a[i-1],那么让他们互换位置,每比较一轮必有一个最小的元素冒泡到这些所比较元素的前面。

  1 #include <iostream>

  2 using  namespace std;

  3

  4 int main()

  5 {

  6     int a[]={1,99,2,88,3,77,4,66};

  7     int n=sizeof(a)/4;

  8     for(int i=0; i<n; i++)

  9     {

  10         for(int j=n-1; j>i; j--)

  11             if(a[j]<a[j-1]) swap(a[j],a[j-1]);

  12     }

  13     cout 《 a[0] ;

  14     for(int i=1; i<n; i++) cout 《 " " 《 a[i];

  15     cout 《endl;

  16     return 0;

  17 }

  4、快速排序

  基本思想就是取一个数作为中间数(一般是取第一个数作为中间数),小于它的都放到左边,大于它的都放到右边,再对每一边利用同样的思想进行处理。

  1 #include <iostream>

  2 using  namespace std;

  3

  4 void QuickSort(int *a, int l, int r)

  5 {

  6     if(a==NULL||l>=r) return ;

  7

  8     int i=l, j=r, tmp=a[l];

  9     while(i<j)

  10     {

  11         while(j>i&&a[j]>=tmp) j--;

  12         a[i]=a[j];

  13         while(i<j&&a[i]<=tmp) i++;

  14         a[j]=a[i];

  15     }

  16     a[i]=tmp;

  17     QuickSort(a,l,i-1);

  18     QuickSort(a,i+1,r);

  19 }

  20

  21 int main()

  22 {

  23     int a[]= {1,99,2,88,3,77,4,66};

  24     int n=sizeof(a)/4;

  25     QuickSort(a,0,n-1);

  26     cout 《 a[0] ;

  27     for(int i=1; i<n; i++) cout 《 " " 《 a[i];

  28     cout 《endl;

  29     return 0;

  30 }

  5、堆排序

  堆排序其实要利用到二叉堆,二叉堆其实完全可以理解为一颗有限制的完全二叉树。

  二叉堆的定义:二叉堆可以分为最大堆和最小堆。最大堆为对于所有节点它的左右节点权值一定比它小,最小堆为对于所有节点它的左右节点权值一定比它大。

  二叉堆的插入:将一个序列下表从0开始一个一个往堆里插入,因为满足完全二叉树性质,所以这么做是可行的。对于插入的第i个数,那么从下往上,它的父亲节点为(i-1)/2个数,再根据二叉堆的性质进行调整。

 

  25 }

  26

  27 void Printf(Node *rt)

  28 {

  29     if(rt->l!=NULL) Printf(rt->l);

  30     cout 《 rt->key 《 " ";

  31     if(rt->r!=NULL) Printf(rt->r);

  32 }

  33

  34 int main()

  35 {

  36     int a[]= {1,99,2,88,3,77,4,66,123,321,58,324,127,428};

  37     int n=sizeof(a)/4;

  38     Node *root=new Node();

  39     root->key=a[0];

  40     for(int i=1; i<n; i++)

  41     {

  42         Insert(root,a[i]);

  43     }

  44     Printf(root);

  45     cout 《 endl;

  46     return 0;

  47 }

  9、基数排序

  基数是一种不稳定的排序,它的时间复杂度为O(k*n),k表示最大数的位数,所以当一个序列中有一个很大很大的数时,它排序所花费的时间是非常高昂的。

  基数排序的原理是一位一位来排序:先按个位大小排序,再按十位大小排序,接着百位……,一直排到最大位数停止。

  比如这样一个数列排序: 342 ,58, 576, 356

  第一次排序(个位):

  3 4 2

  5 7 6

  3 5 6

  0 5 8

  第二次排序(十位):

  3 4 2

  3 5 6

  0 5 8

  5 7 6

  第三次排序(百位):

  0 5 8

  3 4 2

  3 5 6

  5 7 6

  结果: 58 342 356 576.

  1 #include <iostream>

  2 #include <cstring>

  3 #include <sstream>

  4 #include <algorithm>

  5 using  namespace std;

  6

  7 int maxdigit(int *a, int n) //返回数组中最大数的位数

  8 {

  9     int maxx=0;

  10     for(int i=0; i<n; i++)

  11     {

  12         stringstream sa;

  13         sa《a[i];

  14         string s=sa.str();

  15         maxx=max(maxx,int(s.size()));

  16     }

  17     return maxx;

  18 }

  19

  20 void BaseSort(int *a, int n)

  21 {

  22     int *count=new int[10];

  23     int *tmp=new int[n];

  24     int m=maxdigit(a,n);

  25     int base=1;

  26     for(int i=1; i<=m; i++)

  27     {

  28         for(int j=0; j<10; j++) count[j]=0;

  29         for(int j=0; j<n; j++)

  30         {

  31             int k=a[j]/base%10;

  32             count[k]++;

  33         }

  34         for(int j=1; j<10; j++)

  35                 count[j]+=count[j-1];

  36         for(int j=n-1; j>=0; j--)

  37         {

  38             int k=a[j]/base%10;

  39             count[k]--;

  40             tmp[  count[k] ]=a[j];

  41         }

  42         for(int j=0; j<n; j++)  a[j]=tmp[j];

  43         base*=10;

  44     }

  45     delete[] count;

  46     delete[] tmp;

  47 }

  48

  49 int main()

  50 {

  51     int a[]= {1,99,2,88,3,77,4,66,123,321,58,324,127,428};

  52     int n=sizeof(a)/4;

  53     BaseSort(a,n);

  54     cout 《 a[0] ;

  55     for(int i=1; i<n; i++) cout 《 " " 《 a[i];

  56     cout 《endl;

  57     return 0;

  58 }



相关评论