五大基本排序算法.docx

《五大基本排序算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一.选择排序算法：算法基本原理：一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，否则交换min与i位置上数。算法实现：#include//选择排序，如果第一个数字小于后面的则向后移动，依次类推该排序时不稳定的，时间复杂度是N平方voidmain(){intarray[10]={112,4,2,3,5,33,6,7,8,9};//定义一个数组intlength=sizeof(array)/sizeo

2、f(array[0]);//得到数组的长度intk=0,s=0,i=0,j=0;//k保存临时结果，s，i，j为循环变量//选择排序开始for(i=0;iarray[j]){k=array[i];array[i]=array[j];array[j]=k;}}}//选择排序结束，输出显示排序的结果for(s=0;s

3、（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。算法实现：#include//冒泡排序,开始的时候两个数进行比较，大的向后小的向前，第一次比较很容易的就把最大的一个数字放到了最后小的呢，继续向前，第二次当然也找到了第二个大的，放到倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让k=j保存最后的那个数的下标，这样k后面的数都是排序好的了,这个排序是稳定的，时间复杂度是N平方voidmain(){intarray[10]={1,2,1

4、1,22,33,4,23,234,4,6};intlength=sizeof(array)/sizeof(array[0]);intk=0,s=0,i=0,j=0,m=0;//冒泡排序开始for(i=length-1;i>0;i=k){for(j=0,k=0;jarray[j+1])//把比较出来大的数据向后移动{m=array[j];array[j]=array[j+1];array[j+1]=m;k=j;}}}//冒泡排序结束，输出显示排序的结果for(s=0;s

5、y[s]);}}三.快速排序算法基本原理：快速排序（Quicksort）是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。算法实现：#include//快速排序开始，使用递归方法，取其中一个数（任意基本上都是以第一个为准），先从后面比较，如果这个数比后面的大交换之，如果不大继续比较直到大为止，如果大，则交换之，再到前面比较

6、，如果前面的比这个数小交换之再和后面的比较，第一趟下来比它小的就在前面了，比它大的就在后面喽，然后再把该数组分成两部分使用递归，直到最后排序完成voidpaixu(intarray[],intlow,inthight){inti,j,t,m;if(lowt)//开始和后面的比较，如果后面的比他大继续，如果后面的比它小交换之{j--;}if(i

7、ray[i]=array[j];array[j]=m;i++;//让前面的向后移动一个继续比较}while(i