常用的排序算法

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 为整型

//k为keytype型

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