1,快速排序

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

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

　　（1）将问题分成若干大小基本相等的子问题；

　　（2）独立地解决这些子问题；

　　（3）将子问题归并成原问题的解。

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

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

在我设定的一个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);
        }
}

评论