linux c 兑现八大排序算法总结（转）

linux c 实现八大排序算法总结（转）

插入排序

1.直接插入排序

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

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

实现：

[liul@test algorithms]$ more InsertSort.c ?

?

[cpp]?view plaincopy

1. #include<stdio.h>??
2. ??
3. void?InsertSort(int?L[],int?length)??
4. {??
5. ??int?i,j,Tmp;??
6. ??for(i=1;i<length;i++)??
7. ??{??
8. ????j=i+1;???
9. ????if(L[j]<L[i])??
10. ????{??
11. ??????Tmp=L[j];??
12. ??????while(L[0]<L[i])??
13. ??????{??
14. ????????L[i+1]=L[i];??
15. ????????i--;??
16. ??????}??
17. ??????L[i+1]=Tmp;??
18. ????}??
19. ??}??
20. }??
21. ??
22. main()??
23. {??
24. ??int?i,length=7;??
25. ??int?L[7]={4,7,6,9,8,7,9};??
26. ??InsertSort(L,5);??
27. ??for(i=0;i<length;i++)??
28. ??{??
29. ????printf("%d?",L[i]);??
30. ??}??
31. ??printf("\n");??
32. }??
33. ??
34. ??
35. [liul@test?algorithms]$?gcc?InsertSort.c?-o?InsertSort??
36. [liul@test?algorithms]$?./InsertSort???
37. 4?6?7?7?8?9?9??

?

2.希尔排序

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

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

实现：

?

[cpp]?view plaincopy

1. [liul@test?algorithms]$?more?ShellSort.c???
2. #include<stdio.h>??
3. ??
4. void?ShellSort(int?L[],int?length)??
5. {??
6. ??int?i,j,Tmp,k=length-1;??
7. ??while(k>0)??
8. ??{??
9. ????k/=2;??
10. ????for(i=k;i<length;i++)??
11. ????{??
12. ??????Tmp=L[i];??
13. ??????j=i-k;??
14. ??????while(j>=0?&&?Tmp<L[j])??
15. ??????{??
16. ????????L[j+k]=L[j];??
17. ????????j=j-k;??
18. ??????}??
19. ??????L[j+k]=Tmp;??
20. ????}??
21. ??}??
22. }??
23. ??
24. int?main()??
25. {???
26. ??int?i,length=8;??
27. ??int?L[8]={4,7,6,9,8,7,9,2};??
28. ??ShellSort(L,8);??
29. ??for(i=0;i<length;i++)??
30. ??{??
31. ????printf("%d?",L[i]);??
32. ??}??
33. ??printf("\n");??
34. }??
35. [liul@test?algorithms]$?gcc?ShellSort.c?-o?ShellSort??
36. [liul@test?algorithms]$?./ShellSort???
37. 2?4?6?7?7?8?9?9???
38. [liul@test?algorithms]$???

?

交换排序

1.冒泡排序

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

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

实现：

?

[cpp]?view plaincopy

1. [liul@test?algorithms]$?more?BubbleSort.c???
2. #include<stdio.h>??
3. void?BubbleSort(int?L[],int?length)??
4. {??
5. ??int?i,j,Tmp;??
6. ??for(i=0;i<length;i++)??
7. ??for(j=0;j<length-i;j++)??
8. ??{??
9. ????if(L[j]>L[j+1])??
10. ????{??
11. ??????Tmp=L[j];??
12. ??????L[j]=L[j+1];??
13. ??????L[j+1]=Tmp;??
14. ????}??
15. ??}??
16. }??
17. main()??
18. {??
19. ??int?i,length=7;??
20. ??int?L[7]={4,7,6,9,8,7,9};??
21. ??BubbleSort(L,5);??
22. ??for(i=0;i<length;i++)??
23. ??{??
24. ????printf("%d?",L[i]);??
25. ??}??
26. ??printf("\n");??
27. }??
28. [liul@test?algorithms]$?gcc?BubbleSort.c?-o?BubbleSort??
29. [liul@test?algorithms]$?./BubbleSort???
30. 4?6?7?7?8?9?9???
31. [liul@test?algorithms]$???

?

2.快速排序

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

要点：递归、分治

实现：

选择排序

1.直接选择排序

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

要点：

实现：

Void?SelectSort(Node?L[])

{

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

For(i=0;i<length;i++)

{

k=i;

For(j=i+1;j<length;j++)

{

If(L[j]<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>0;i--)//交换

{

Int?temp=L[i];

L[i]=L[0];

L[0]=temp;

Heapify(L,0,i);//调整堆

}

}

Void?BuildingHeap(Node?L[])

{?For(i=length/2?-1;i>0;i--)

Heapify(L,i,length);

}

归并排序

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

要点：归并、分治

实现：

?

[cpp]?view plaincopy

1. Void?MergeSort(Node?L[],int?m,int?n)??
2. {??
3. Int?k;??
4. If(m<n)??
5. {??
6. K=(m+n)/2;??
7. MergeSort(L,m,k);??
8. MergeSort(L,k+1,n);??
9. Merge(L,m,k,n);??
10. }??
11. }??

?

?

[cpp]?view plaincopy

1. [liul@test?algorithms]$?more?MergeSort.c???
2. #include<stdio.h>??
3. #include<stdlib.h>??
4. ??
5. void?Merge(int?L[],int?p,int?q,int?r)??
6. {??
7. ??int?i,k;??
8. ??int?begin1,end1,begin2,end2;??
9. ??int?*?Tmp?=?(int?*)malloc((r-p+1)*sizeof(int));??
10. ??begin1=p;??
11. ??end1=q;??
12. ??begin2=q+1;??
13. ??end2=r;??
14. ??k=0;??
15. ??while((begin1<=end1)&&(begin2<=end2))??
16. ??{??
17. ????if(L[begin1]<L[begin2])??
18. ????{??
19. ??????Tmp[k]=L[begin1];??
20. ??????begin1++;??
21. ????}????
22. ????else??
23. ????{??
24. ??????Tmp[k]=L[begin2];??
25. ??????begin2++;??
26. ????}??
27. ????k++;??
28. ??}??
29. ??while(begin1<=end1)??
30. ??{??
31. ????Tmp[k++]=L[begin1++];??
32. ??}??
33. ??while(begin2<=end2)??
34. ??{??
35. ????Tmp[k++]=L[begin2++];??
36. ??}??
37. ??for(i=0;i<(r-p+1);i++)??
38. ????L[p+i]=Tmp[i];??
39. ??free(Tmp);??
40. }??
41. ??
42. void?MergeSort(int?L[],int?first,int?last)??
43. {??
44. ??int?mid=0;??
45. ??if(first<last)??
46. ??{??
47. ????mid=(first+last)/2;??
48. ????MergeSort(L,first,mid);??
49. ????MergeSort(L,mid+1,last);??
50. ????Merge(L,first,mid,last);??
51. ??}??
52. }??
53. ??
54. int?main()??
55. {???
56. ??int?i,length=8;??
57. ??int?L[8]={4,7,6,9,8,7,9,2};??
58. ??MergeSort(L,0,7);??
59. ??for(i=0;i<length;i++)??
60. ??{??
61. ????printf("%d?",L[i]);??
62. ??}??
63. ??printf("\n");??
64. }??
65. [liul@test?algorithms]$?gcc?MergeSort.c???
66. [liul@test?algorithms]$?gcc?MergeSort.c?-o?MergeSort??
67. [liul@test?algorithms]$?./MergeSort???
68. 2?4?6?7?7?8?9?9???
69. [liul@test?algorithms]$???

?

基数排序

原理：将数字按位数划分出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<maxradix)?//遍历所有关键字

{

For(int?i=0;i<length;i++)?//分配过程

{

If(L[i]<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++;

}

}