正文

[原]自己总结的排序算法2007-12-20 10:13:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/sword2008/31508.html

分享到:

1,快速排序

这个有点难解释,感觉上就是纽来纽去,先从首记录开始也行,从未记录开始也行,以后补上.

Tony Hoare在1962年首次提出了快速排序算法。对快速排序方法的研究表明,至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时,其它排序算法才可能胜过快速排序算法快速排序算法是利用分治技术的典型例子,随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步:

  (1)将问题分成若干大小基本相等的子问题;

  (2)独立地解决这些子问题;

  (3)将子问题归并成原问题的解。

  快速排序的基本思路是:首先我们选择一个中间值middle(程序中我们可使用数组中间值),把比中间值小的放在其左边,比中间值大的放在其右边。由于这个排序算法较复杂,我们先给出其进行一次排序的程序框架(从各类数据结构教材中可得):

void QuickSort(int *pData, int left, int right)
{
  int i, j;
  int middle, iTemp;
  i = left;
  j = right;

  middle = pData[(left + right) / 2]; //求中间值
  do
  {
   while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
    i++;
   while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
    j--;
   if (i <= j) //找到了一对值
   {
    //交换
    iTemp = pData[i];
    pData[i] = pData[j];
    pData[j] = iTemp;
    i++;
    j--;
   }
  } while (i <= j) ; //如果两边扫描的下标交错,就停止(完成一次)

  //当左边部分有值(left<j),递归左半边

  if(left<j)
   QuickSort (pData,left,j);
   //当右边部分有值(right>i),递归右半边
  if(right>i)
   QuickSort (pData,i,right);
}

  由此可见,上述排序算法中采用了递归策略。 

在我设定的一个10000个无序记录集中,快速排序比冒炮节省了差不多一半时间,估计记录越多,这个数量级会更高.

2,选择排序,

选择排序和冒泡如果不仔细看,光从字面解释,很多人都弄混,解释这个很简单,举个例子就行.

如:2,6,1,4

首先将2和所有记录遍历,找出比他小的交换位置,于是(第一个记录)

1,6,2,4

第二次

将6遍历,找出小的交换(第二个记录)

1,2,6,4

第三次......

1,2,4,6完成!

 

3,冒泡

这个就更加简单理解

两两相互之间比较,大(或者小的)放到前面,但必须遍历N-1次.

感觉上如果是无序的记录让他遍历效率会高.

如,2,6,1,4

2,1,4,6(小的交换后继续和后面的记录交换)

1,2,4,6完成``````(N-1次???好象是说选择排序了,忘记了.)

数据量少的时候可以用冒泡,某些人说过冒泡效率最低```````

当然还有改良的冒泡双琏算法.

void CTestDlg::BubbleSort(int *pData,int iNum)  //冒泡
{
 int i,j;
 int temp;
 for(i=iNum-1;i>0;i--)  //iNum-1次
  for(j=0;j<i;j++)
  {
   if(pData[j]>pData[j+1])
   {
    temp  =pData[j];
    pData[j] =pData[j+1];
    pData[j+1] =temp;
   }
  }
}

4插入排序

将第一个记录看成已经排好的序列,其次数据一个一个与之前最大的记录比较,子成序列,听说是如果有序的记录集合排序效果好.

void CTestDlg::insert_sort(int * list, int length)
{
        int i, j, temp;
        for(i = 1; i < length; i ++)
        {
                temp = list[i];
                j = i - 1;
                while((list[j] > temp)&&(j >= 0))
                {
                        list[j+1] = list[j];
                        j --;
                }
                list[j+1] = temp;
            //    show_list(list, length);
        }
}

阅读(2595) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册