简单排序算法小结及实现(The implementation of three easy sort algorithm)
三种简单排序算法分别的冒泡法,选择排序法和插入法.
三种排序算法的最差运行效率都要达到O(n*n)
1冒泡排序法:
void bubbleSort(Type* arr,long len)/*bubble sort algorithm*/
{
long i=0,j=0;/*iterator value*/
assertF(arr!=NULL,"In bubble sort,arr is NULL\n");
for (i=len;i>1;i--)
for(j=0;j<i-1;j++)
if(arr[j]>arr[j+1])swapArrData(arr,j,j+1);
}
从数组的后面位置开始,如果发现有比前面一个位置处的数更小的元素,则把交换这两个数的位置,形成一个类似轻的气泡在水中上升的排序过程.
2插入排序法:
void insertSort(Type* arr,long len)/*InsertSort algorithm*/
{
long i=0,j=0;/*iterator value*/
Type tmpData;
assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
for(i=1;i<len;i++)
{
j=i;
tmpData=arr[i];
while(tmpData<arr[j-1]&&j>0)
{
arr[j]=arr[j-1];
j--;
}
arr[j]=tmpData;
}
}
插入排序算法思路是:
假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.
3选择排序法:
void selectionSort(Type* arr,long len)
{
long i=0,j=0;/*iterator value*/
long maxPos;
assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
for(i=len-1;i>=1;i--)
{
maxPos=i;
for(j=0;j<i;j++)
if(arr[maxPos]<arr[j])maxPos=j;
if(maxPos!=i)swapArrData(arr,maxPos,i);
}
}
选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.
由于这三种算法相对简单,运行效率也比较低,在元素个数比较少的时候用一个问题也是不大的.但当要排序的元素个数>=10000时,基本已经失去的使用价值,在当前的主流机器上,
10000个元素时,排序的时间单位差不多是秒.(相对而言,)
而到了100000个元素的时候,排序的时间单位已经是分钟了,此时,快速排序的运行时间单位
仍是百分之一秒呢.
参:
http://blog.csdn.net/EmilMatthew/archive/2005/09/04/471018.aspx