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); }}
评论