八大排序算法总结

1.直接插入排序

原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。

要点：设立哨兵，作为临时存储和判断数组边界之用。

实现：

void insertsort(node l[],int length)

{

int i,j;//分别为有序区和无序区指针

for(i=1;i<length;i++)//逐步扩大有序区

j=i+1;

if(l[j]<l[i])

l[0]=l[j];//存储待排序元素

while(l[0]<l[i])//查找在有序区中的插入位置，同时移动元素

l[i+1]=l[i];//移动

i--;//查找

}

l[i+1]=l[0];//将元素插入

i=j-1;//还原有序区指针

2.希尔排序

原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。

要点：增量的选择以及排序最终以1为增量进行排序结束。

void shellsort(node l[],int d)

while(d>=1)//直到增量缩小为1

shell(l,d);

d=d/2;//缩小增量

void shell(node l[],int d)

int i,j;

for(i=d+1;i<length;i++)

if(l[i]<l[i-d])

l[0]=l[i];

j=i-d;

while(j>0&&l[j]>l[0])

l[j+d]=l[j];//移动

j=j-d;//查找

l[j+d]=l[0];

交换排序

1.冒泡排序

原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。

要点：设计交换判断条件，提前结束以排好序的序列循环。

void bubblesort(node l[])

int i ,j;

bool ischanged;//设计跳出条件

for(j=n;j<0;j--)

ischanged =false;

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

if(l[i]>l[i+1])//如果发现较重元素就向后移动

int temp=l[i];

l[i]=l[i+1];

l[i+1]=temp;

ischanged =true;

if(!ischanged)//若没有移动则说明序列已经有序，直接跳出

break;

2.快速排序

原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。

要点：递归、分治

<a href="http://b25.photo.store.qq.com/http_imgload.cgi?/rurl4_b=1ea94769d009bfaa1e6c7ee9a771782623731b741f656064f967567197aef25824d4b762b69953f911cc0f755975b3fde599b29f7df7d5b32b5fb6ae5ab3b2b105da6c5ebfca19f370b921f87019c4df3c3737b2" target="_blank"></a>

选择排序

1.直接选择排序

原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。

要点：

void selectsort(node l[])

int i,j,k;//分别为有序区，无序区，无序区最小元素指针

for(i=0;i&lt;length;i++)

k=i;

for(j=i+1;j&lt;length;j++)

if(l[j]&lt;l[k])

k=j;

if(k!=i)//若发现最小元素，则移动到有序区

int temp=l[k];

l[k]=l[i];

l[i]=l[temp];

2.堆排序

原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。

要点：建堆、交换、调整堆

void heapsort(node l[])

buildingheap(l);//建堆（大根堆）

for(int i=n;i&gt;0;i--)//交换

l[i]=l[0];

l[0]=temp;

heapify(l,0,i);//调整堆

<a href="http://b23.photo.store.qq.com/http_imgload.cgi?/rurl4_b=1ea94769d009bfaa1e6c7ee9a77178262e6141297a72a1804e6a17ab4fb52e1de5427384cb40f47ff434bc8f0bdbcc92f3842af6956c013b5b9a337d726dd60960ff500e05bb14dc124efaf0c2e3fa73d33f643c" target="_blank"></a>

void buildingheap(node l[])

{ for(i=length/2 -1;i&gt;0;i--)

heapify(l,i,length);

归并排序

原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。

要点：归并、分治

void mergesort(node l[],int m,int n)

int k;

if(m&lt;n)

k=(m+n)/2;

mergesort(l,m,k);

mergesort(l,k+1,n);

merge(l,m,k,n);

<a href="http://b24.photo.store.qq.com/http_imgload.cgi?/rurl4_b=1ea94769d009bfaa1e6c7ee9a7717826cfe8ad938281c93d6b0d6a20e5f1d78a3c330cfaa6b7dd15ab32e731045251b663a9700af5f63172dfb409d9ddd2a12e0d67b557e0252a3e4b95250740a05f2364a24ec7" target="_blank"></a>

基数排序

原理：将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。

要点：对关键字的选取，元素分配收集。

void radixsort(node l[],length,maxradix)

int m,n,k,lsp;

k=1;m=1;

int temp[10][length-1];

empty(temp); //清空临时空间

while(k&lt;maxradix) //遍历所有关键字

for(int i=0;i&lt;length;i++) //分配过程

if(l[i]&lt;m)

temp[0][n]=l[i];

else

lsp=(l[i]/m)%10; //确定关键字

temp[lsp][n]=l[i];

n++;

collectelement(l,temp); //收集

n=0;

m=m*10;

k++;

原文链接：http://blog.csdn.net/yexinghai/article/details/4649923