`
liss
  • 浏览: 842655 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

常用的排序算法

阅读更多

1选择排序

先在整个序列中选出关键字值最小的元素,如果它不是第一个元素,则将它和第一个元素交换;然后在除一个除第一个位置上的元素以外的其余元素中再选出关键值次最小的元素,如果它不在第二个位置,则和第二个位置上的元素进行交换;依次类推,直至所有元素排序完成.

该算法是不稳定的.[1]

 

算法: 选择排序

Algorithm select_sort(s[ ])

       //s[ ] sortseq型排序表,n为整型常量

       //i, j, k为整型

       //t为元素类型

{

       For (i = 1; i <= n-1; ++i){

              k = I;

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

                     if (s[j].key < s[k],key)

                     k = j;

              if ( k != i){

                     t = s[i];

                     s[i] = s[k];

                     s[k] = t;

        }

       }

}

2插入排序

1) 直接插入排序

       先将第一个元素看成是一个有序序列;然后将第二个元素的关键字与第一个元素进行比较,若第二个元素关键字值小于第一个元素关键字值,则将第一个元素右移一个位置,第二个元素插入到第一个元素的位置,否则第二个元素仍然插在原位置;再将第三个元素的关键字与第二个元素进行比较,根据比较结果或将第二个元素右移一个位置,进而再与第一个元素比较,或插在原位置,用类似的比较过程将第三个元素插入到有序序列中;依次类推,将所有元素按关键字值大小插入到已排好序的有序序列中,直至全部插完.该算法是稳定的

算法;直接插入排序

Algorithm insert_sort(s[ ])

//s[] sortseq型排序表,n 为整型常量

//i, j为整型

{

       for (i = 2; i <= n; ++i){

              s[0] = s[i];

              for (j = i – 1; s[j].key > s[0].key; --j)

                     s[j+1] = s[j];

              s[j+1] = s[0];

       }

}

2)对半插入排序

       直接插入排序中,将查找第i个元素插入位置的方法改用对半法进行关键字间的比较,便得到对半插入排序.为了用对半法查找插入位置,待排序的n个元素序列的存储结构须采用顺序存储方式.该算法是稳定的.

算法:对半插入排序

algoreithm bin_sort(s[ ])

{

       for (i = 2; i <= n; ++i){

              s[0] = s[i];

              L = 1;

              h = i – L;

              while ( L <= h){

                     m = (L+h)/2;

                     if (s[m].key > s[0].key)

                            h = m – 1;

                     else L = m + 1;

              }

              for (j = i – 1; j >= 1; --j)

                     s[j+1] = s[j];

              s[L] = [0];

       }

}

: 本文用大写L以区别小写l与数字1的区别

3冒泡排序

先将第一个元素的关键字和第二个元素的关键字进行比较,若不满足顺序要求,则将两个元素进行交换;然后比较第二个和第三个元素的关键字并作同样处理;依次类推,直至第n-1个元素的位置和第n个元素进行比较并处理完.这时关键字值最大的元素被交换到最后一个元素的位置上,这是一趟排序过程.重复执行这种运算过程,不过第2趟只需对前n-1个元素进行排序,3趟只需对前n-2个元素进行排序,如此下去,直至在一趟排序中没有元素进行过交换或最多进行了n-1趟排序为止.

算法:冒泡排序

algorithm bubble_sort([])

//s[ ]sortseq型排序表,n为整型常量

//i, j, done为整型

//temp为元素类型

{

       i = 1;

       done = 0;

       while ( i <= n – 1 && !done){

              done = 1;

              for ( j = 1; j <= n – i; ++j)

                     if (s[j].key > s[j+1].key){

                            done = 0;

                            temp = s[j];

                            s[j] = s[j+1];

                            s[j+1] = tem[;

                     }

              ++i;

       }
}

 

4快速排序

从排序过程来看,快速排序与冒泡排序一样,也是通过元素交换方式来进行排序的.

快速排序方法的基本思想是:在待排序的元素序列中任取一个元素(例如取第一个元素),通过一趟排序,以该元素的关键字为标准,将待排元素序列分成两部分,所有关键不大于该元素关键字的元素排在它的位置之前(即左边),所有关键字不小于该元素关键字的元素排在它的位置之后(即右边),把该元素排在这两部分的中间,这就是该元素最终排序的位置.然后分别对这两部分重复上述排序,直至所有的元素都排到序列的相应位置上为止.

该算法是不稳定的

算法: 快速排序.

algorithm quick_sort(s[ ], L , r)

//s[]sortseq型排序表

//L, j,r 为整型

//kkeytype

//temp 为元素型

{

       if (L < r){

              i = L;

              j = r;

              k = s[i].key;

              temp = s[i];

              while ( i < j){

                     while (s[j].key >= k && i<j)

                            --j;

                     if ( i > j){

                            s[i++] = s[j];

                            while (s[i].key <= k && i < j)

                                   ++i;

                            if (i < j)

                                   s[j--] = s[i];

                     }

              }

              s[i] = temp;

              quick_sort ( s, L, i-1);

              quick_sort (s, i+1, r);

       }

}

[1] 如果待排的元素序列中含有两个或两个以上关键字值相等的元素,经过排序后这些元素的前后次序保持不变,则这种排序方法是稳定的,否则是不稳定的.

功能:希尔排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
一组,排序完成。

下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。

希尔排序是不稳定的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;

for (h=n/2; h>0; h=h/2) /*控制增量*/
{
   for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/
   {
    t = *(x+j);
    for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
    {
     *(x+k+h) = *(x+k);
    }
    *(x+k+h) = t;
   }
}
}
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当
满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。

由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,
使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点
的堆,并对它们作交换,最后得到有n个节点的有序序列。

从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数
实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

*/
/*
功能:渗透建堆
输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;

t = *(x+s); /*暂存开始元素*/
k = s;   /*开始元素下标*/
j = 2*k + 1; /*右子树元素下标*/

while (j<n)
{
   if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件:满足就继续下一轮比较,否则调整。*/
   {
    j++;
   }

   if (t<*(x+j)) /*调整*/
   {
    *(x+k) = *(x+j);
    k = j; /*调整后,开始元素也随之调整*/
    j = 2*k + 1;
   }
   else /*没有需要调整了,已经是个堆了,退出循环。*/
   {
    break;
   }
}

*(x+k) = t; /*开始元素放到它正确位置*/
}


/*
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;

for (i=n/2-1; i>=0; i--)
{
   sift(x,n,i); /*初始建堆*/
}

for (k=n-1; k>=1; k--)
{
   t = *(x+0); /*堆顶放到最后*/
   *(x+0) = *(x+k);
   *(x+k) = t;
   sift(x,k,0); /*剩下的数再建堆*/
}
}


void main()
{
#define MAX 4
int *p, i, a[MAX];

/*录入测试数据*/
p = a;
printf("Input %d number for sorting :\n",MAX);
for (i=0; i<MAX; i++)
{
   scanf("%d",p++);
}
printf("\n");

/*测试选择排序*/


p = a;
select_sort(p,MAX);
/**/


/*测试直接插入排序*/

/*
p = a;
insert_sort(p,MAX);
*/


/*测试冒泡排序*/

/*
p = a;
insert_sort(p,MAX);
*/

/*测试快速排序*/

/*
p = a;
quick_sort(p,0,MAX-1);
*/

/*测试堆排序*/

/*
p = a;
heap_sort(p,MAX);
*/

for (p=a, i=0; i<MAX; i++)
{
   printf("%d ",*p++);
}

printf("\n");

}
以上都是比较排序算法,也就是通过元素间的比较来决定各元素的位置以完成排序的算法。
可以证明,比较排序算法的时间复杂度在最好情况下最多只能达到Ω(n lg n),
证明过程大致描述如下(详见《算法导论》8.1节):对任一序列,我们可以为其构造一棵决策树如下:
每个节点代表某两个元素的比较,左右子树分别代表比较两个元素a、b的两种结果——左子树a<b,
右子树a≥b,直到最后的叶子节点得到原序列的一个有序排列。每个叶子节点都对应了原序列各元素的
一种相对位置情况,而中间的整个比较过程就代表了一种比较排序算法,层数最多的那个子节点就代表
了最坏的情况下,那个节点所在的层数也是整个决策树的高度。假设我们得到的决策树高度为h,共有L个
叶子节点,因为长度为n的序列有P(n,n) = n!种排列方式,所以有L≥n!;又因为高为h的二叉树最
多有2 ^ h个叶子节点,所以有L≤2 ^ h,于是得到n!≤2 ^ h,h≥lg(n!) = Ω(n lg n)
(最后这个等式的证明见《算法导论》3.18节),即一个比较排序算法在最好情况下完成排序至少需要n lg n数量级的时间复杂度。



那么,我们有没有什么办法突破这个限制呢?有,当然有,只不过我们要受到一些别的限制。
下面我们就一起来看看这些有趣的东东吧^_^(这些算法由于针对性太强,不具备很好的通用性,
实现代码就不再是泛型的了)。

当需要排序的序列的取值范围是一个元素个数很小的有限集合,并且集合中有哪些元素我们事先可以知道时,我们可以采用counting sort这种排序算法。这个算法就象其名字所说描述的,其实就是数出每个取值在序列中的个数,然后据此找出每个元素“应该在的位置”,之后直接将其放到它该在的位置上即可,比如对一个所含元素为0~k的整数的序列我们可以写出排序代码如下:

void CountingSort(int *_F, int *_L, int k)
{
//建立临时数组并初始化为全0
int *temp = new int[k + 1];
memset(temp,0,(k+1)*sizeof(int));
//分配输出数组空间
int *b = new int[_L - _F];
//数出每个可能取值的元素的个数存在临时数组中
for(ptrdiff_t i = 0; i < _L - _F; ++i)
{
++temp[_F[i]];
}
//算出可能取值元素个数的累加和
for(int i = 1; i <= k; ++i)
{
temp[i] += temp[i-1];
}
//将元素写出到输出数组
for(ptrdiff_t i = _L-_F-1; i >= 0;--i)
{
b[--temp[_F[i]]] = _F[i];
}
//结果写回原数组
for(ptrdiff_t i = 0; i < _L - _F; ++i)
{
_F[i] = b[i];
}
delete[] temp;
delete[] b;
}



Counting sort由于避免了比较,也就不再受比较排序算法时间复杂度的限制,那么它的时间复杂度到底是哪个级数呢?我们可以看出上述代码第一个循环执行Θ(k)次,第二个执行Θ(n)次(n为元素个数),第三个执行Θ(k)次,最后两个执行Θ(n)次,所以总的时间复杂度为Θ(k+n),又因为我们使用counting sort时必然有k = O(n),于是总的时间复杂度就是Θ(n)了,也就是说counting sort具有线性的时间复杂度,而其空间复杂度为Θ(k)。Counting sort很少被单独使用,由于它具有稳定性速度快这样的优良性质,一般被用作radix sort的子排序过程。

Radix sort是一个很古老的算法了,曾用在古董级的计算机中用来对卡带排序。
其基本思想大致描述如下:对一个用来排序的key域——比如一个3位整数——我们可以把它分成3个子域,每个子域1位,再从最后一个子域到第一个子域依次对每个子域进行排序,这里就是从个位到百位依次排序,每个域排完了整个key域也就排完了,这里要注意顺序,应该是权值越高的域越后排。可以看出,要这个算法正确执行必须要求对每个子域排序的排序子过程是稳定的。而且每个子域取值范围很小,事先可以确定,正是counting sort发挥的大好时机^_^ 针对计算机数,我们可以4bits一组进行分组,然后用counting sort对每组排序,于是可以对一个32bits无符号整数写出排序代码如下:
//特殊版counting sort,最后一个参数为排序元素右移的位数
void CountingSort(unsigned *_F, unsigned *_L, unsigned k)
{
ptrdiff_t length = _L-_F;
unsigned *temp = new unsigned[0xf+1];
memset(temp,0,(0xf+1)*sizeof(unsigned));
int *b = new int[length];
for(ptrdiff_t i = 0; i < length; ++i)
{
++temp[((_F[i]>>k)&0xf)];
}
for(int i = 1; i <= 0xf; ++i)
{
temp[i] += temp[i-1];
}
for(ptrdiff_t i = length-1; i >= 0;--i)
{
b[--temp[((_F[i]>>k)&0xf)]] = _F[i];
}
for(ptrdiff_t i = 0; i < length; ++i)
{
_F[i] = b[i];
}
delete[] b;
delete[] temp;
}

void RadixSort(unsigned *_F, unsigned *_L)
{
ptrdiff_t length = _L-_F;
//分为4bits一个域以counting sort为子过程进行radix sort
for(unsigned i = 0;i < 32; i+=4)
{
CountingSort(_F,_L,i);
}
}



可以证明,对n个值排序,每个值分为d个子域,每个子域有k个可能取值时,radix sort时间复杂度为Θ(d (n+k))(证明过程见《算法导论》8.3节),特定算法d、k为常数,所以radix sort时间复杂度为Θ(n)。其空间复杂度为Θ(n)。

最后讨论的一个算法是所谓的bucket sort,它针对均匀分布在范围[0,1)上的序列,以Θ(n)的时间复杂度进行排序。算法大致描述如下:假如要排序的序列有n个元素,则建立一个n元素的链表数组,遍历待排序序列,将每一个元素a加到第n*a个链表中,最后对每个链表用插入排序算法进行排序(也可在加入时按顺序加入),最后再将元素按顺序写回即可。代码如下:

void BucketSort(float *_F, float *_L)
{
ptrdiff_t length = _L-_F;
//分配一个list数组
list<float> *bucket = new list<float>[length];
//将各元素放到其该在的list
for(int i=0;i<length;i++)
{
bucket[int(_F[i]*length)].push_back(_F[i]);
}
//对各list排序
for(ptrdiff_t i=0;i<length;i++)
{
bucket[i].sort();
}
//将排序结果写回原数组
for(ptrdiff_t i=length-1,j=length-1;i>=0&&j>=0;--i)
{
while(!bucket[i].empty())
{
_F[j--]=*(--bucket[i].end());
bucket[i].pop_back();
}
}
delete[] bucket;
}



这个算法最重要的条件就是要求元素的均匀分布,每个链表最后只能分配到少数几个元素,这样才不会在最后的排序上花费太多时间,以保证Θ(n)的时间复杂度,以及Θ(n)的空间复杂度。

可以看出,上述时间复杂度为Θ(n)的排序算法都有一些比较特殊的要求,并且都具有线性的空间复杂度。其思想都是将一些其它的信息转化为元素的位置信息,以避免直接的比较,而在采用这些信息时都不可避免会付出空间上的代价。我们在遇到一些对速度要求特别高的特殊问题时,也可以从这个角度进行考虑,以找到符合具体问题的最优解决方案。

分享到:
评论

相关推荐

    python常用排序算法汇总

    该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...

    常用排序算法总结 常用排序算法总结 常用排序算法总结

    常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结

    浅析基于C语言的常用排序算法比较.pdf

    插入排序算法同样是基于C语言的一种常用排序算法。插入排序的基本思想是:把待排序的序列分为已排序和未排序两部分,每次将一个未排序的元素,按照其大小插入到已排序序列中的适当位置,直到所有元素都被插入。插入...

    《常用排序算法的比较》PDF格式论文

    ### 常用排序算法的比较 #### 引言 排序是计算机科学中一项非常重要的基本操作,它涉及将一组数据元素(或记录)按照特定的顺序(通常是递增或递减)重新排列。排序的目的通常是为了提高后续操作如搜索等的效率。...

    常用排序算法java演示

    本文将深入探讨标题"常用排序算法java演示"中涉及的知识点,包括排序算法的原理、Java实现方式以及其在实际应用中的图形演示。 首先,让我们逐一了解几种常见的排序算法: 1. **冒泡排序(Bubble Sort)**:这是一...

    常用排序算法的动态演示系统

    常用排序算法的动态演示系统 在本系统中,我们主要实现了五种常用的排序算法:冒泡排序法、快速排序法、直接插入排序法、折半插入排序法和树形选择排序法。这些算法都是在计算机科学中最基本和最重要的排序算法,...

    实验六 常用排序算法的对比分析

    石家庄铁道大学 刘立嘉 算法与数据结构 实验六 常用排序算法的对比分析

    几种常用排序算法的C语言实现

    一些常用排序算法的C语言实现,包括直接选择排序,希尔排序,直接插入排序,快速排序,归并排序,冒泡排序,堆排序

    常用排序算法介绍_源码.rar|排序算法_源码.rar

    常用排序算法示例程序,内含TChart8控件。 示例程序涉及15种排序算法,使用C++代码实现,包含每种算法核心思想的介绍;可设置排序的数据个数、数据刷新显示时间等;使用TChart控件显示数据,显示界面可缩放。

    常用排序算法源码

    在编程领域,排序算法是计算机科学中的核心概念,它们用于对数据进行有序排列。这里我们主要探讨五种常见的排序算法,这些算法的源码你可以在提供的压缩包文件中找到:MergeSort(归并排序)、RadixSort(基数排序)...

    golang实现的常用排序算法

    golang实现的常用排序算法 golang实现的常用排序算法 golang实现的常用排序算法

    各种常用排序算法的C语言实现

    本资源提供了各种常用排序算法的C语言实现,源自严蔚敏的经典教材《数据结构》。下面将详细介绍这些排序算法及其在C语言中的实现原理。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序方法,通过不断交换相邻...

    常用排序算法介绍_示例程序|排序算法_程序.rar

    本资源"常用排序算法介绍_示例程序"提供了一个深入理解这些算法的平台,结合了理论与实践,帮助开发者直观地看到各种排序算法的工作过程。 首先,让我们逐一探讨这些排序算法的核心思想: 1. **冒泡排序**:通过...

    C++常用排序算法(C++)

    【C++常用排序算法】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。C++作为一种强大的编程语言,提供了多种实现排序的方法。本文将详细介绍C++中常用的几种排序算法及其实现。 1. **冒泡排序** 冒泡...

    Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找

    本资料包聚焦于"Java常用排序算法"和"程序员必须掌握的8大排序算法",并深入探讨了"二分法查找"这一高效搜索技术。 首先,我们来看八大排序算法。这些算法包括: 1. **冒泡排序**:最简单的排序方法,通过不断交换...

    C++ 常用排序算法

    以下是对C++中几种常用排序算法的详细说明: 1. **选择排序(Selection Sort)**: 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始...

    8大常用排序算法实现

    本文将详细解析八大常用排序算法的实现,帮助你更好地理解和测试这些算法。 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换,使得每次遍历都将最大(或最小)的元素“冒...

    常用排序算法,括交换法,冒泡法等

    ### 常用排序算法详解 #### 一、引言 排序算法作为计算机科学中的基础且重要的组成部分,在现实生活中有着广泛的应用。随着数据量的不断增大,如何高效地进行排序成为了一个亟需解决的问题。本篇文章将从简单排序...

    C语言常用排序算法

    C语言常用排序算法 在计算机科学中,排序算法是指将一组无序的数据按照某种顺序排列的方法。排序算法是编程语言中非常重要的一部分,特别是在C语言中。下面将介绍几种常用的排序算法,包括选择排序、插入排序等。 ...

Global site tag (gtag.js) - Google Analytics