数据结构学习：：关于排序

时间：2022-06-11 13:39:59

近几天重新学习数据结构，其实也不算重新，因为当年根本没有学过。（像堆排序，基数排序等）。主要学习的是内部排序这一块，马上趁热打铁，将心得体会写一下。

内部排序包括了以下几种类别：插入排序，选择排序，交换排序，归并排序和基数排序。这是根据排序算法的本质特征来划分的。

首先要给出的当然是数据结构了：

Code:
  1. typedef int KeyType;  
  2.   
  3. typedef struct{  
  4.     KeyType *r;  
  5.     int length;  
  6. }SqList;  

插入排序

顾名思义，这是通过将元素插入适当的位置进行排序的算法。

首先说简单插入排序，算法就是认为前i-1个元素是有序的，然后从i开始，通过查找将元素i插入到适当的位置。看看代码：

Code:
  1. void InsertSort(SqList &list){  
  2.       
  3.     int i,j;  
  4.     KeyType tmp;  
  5.     for (i=1;i<list.length;i++)  
  6.         if (Compare(list.r[i],list.r[i-1])< 0) {  
  7.             tmp = list.r[i];  
  8.             list.r[i] = list.r[i-1];  
  9.               
  10.             for (j=( i-2<0?0:i-2 ); Compare(list.r[j], tmp) > 0; j--)  // as soon as list.r[j]> tmp(which is going to insert into the list) lsit.r[j] need   
  11.                 list.r[j+1]=list.r[j];  
  12.               
  13.             list.r[j+1]=tmp;  
  14.         }  
  15.       
  16. }  

说说代码，i从1开始，首先比较r[i]跟r[i-1]，如果r[i]小，则表示r[i]需要往前插，此时，记下r[i]，然后顺便将r[i-1]往后移。其实这句可以不写，因为后面移动元素的时候可以完成这项工作。

下面做的事情是，从i-2开始往前比较，因为i-1比较过了。比较到什么时候停呢？直到找到一个r[j]，它比tmp要小，其实应该叫ins，表示要插入的元素，这时就停了。就是说一天没找到比tmp小的元素，就将这个r[j]往后挪: r[j+1]=r[j] 然后 j--,继续往前找。最后停下来之后，将tmp插入到r[j+1]的位置，为什么？因为r[j]比tmp小啊，所以j+1就是插入点了。

这里要注意一下的是，书上的源码是数列从下标1开始存储，用r[0]做哨兵，我做了修改，不过就没有那么方便了，需要为i=1的时候做一个修正。

然后当时我就想，既然插入排序是往前查找一个比 r[i] 小的数，查找家族中有折半查找啊，通过它不就可以提高算法效率了吗？果然下一页就是使用折半查找改进的插入排序，代码：

Code:
  1. void halfInsertSort(SqList &list){  
  2.       
  3.     int low, high,mid;  
  4.     int i,j;  
  5.     KeyType ins;  
  6.     for (i=1;i<list.length;i++)  
  7.         if (Compare(list.r[i],list.r[i-1]) < 0 )  {  
  8.             //ins is the element which is going to be inserted.  
  9.             ins=list.r[i];  
  10.             list.r[i]=list.r[i-1];  
  11.   
  12.             low = 0;  
  13.             high = i-1;  
  14.             while (low<=high){  
  15.                 mid = (low + high) /2;  
  16.                 //If ins > r[mid] , it means the inserting point is at the posterior segment, so move low to mid+1   
  17.                 if (Compare(ins,list.r[mid]) >= 0 ) low=mid+1;  
  18.                 else high = mid-1;  
  19.             }  
  20.   
  21.             //move elements  
  22.             //Attention: low = high+1  
  23.             for (j=i-1;j>low;j--) list.r[j]=list.r[j-1];  
  24.               
  25.             //insert ins to the inserting point  
  26.             list.r[low] = ins;    
  27.   
  28.         }  
  29.   
  30. }  

整个步骤都是一样的，还是从i =1开始，比较i和i-1，如果i小，即是由插入的可能，然后接下来的事情就不同了。接下来是折半查找啊。经典算法了：low=0,high=i-1。这就是说，要在区间[0,i-1]中找到一个最终插入的点。有人可能要问，折半查找，通常区间中肯定有一个元素跟ins（被插入元素）是相等的，就是说能定位到唯一一个点，然后这里通常都找不到跟ins一样的元素，应该是怎样的呢？

我也想过这个问题。不妨这样来想，用二分查找，是为了找到一个插入点，而它应该就是离ins最近，然后又比它小的元素。我们用ins跟r[mid]比较，如果ins比这个中间元素要大，那表示说，在后半个区间里，还可能会有比ins小而且离ins跟近的元素。反之，如果Ins比中间元素小，那就继续向前找咯。  其次，最终循环结束的条件是low>high，而这个时候的前一状态，是low=high。我们可以肯定一点，无论如何，low和high最后肯定会有相等的时候。而这个时候mid=low=high，而这时的r[mid]，应该就是我们要找的元素了。看看最后的比较吧：如果元素比ins比较小，还是一样，low=mid+1=low+1, 如果元素比ins大，high=mid-1=high-1。我们容易知道，最后的这个元素，其实是有可能比ins大，也有可能小的，如果这个元素是比ins小的，那插入点在这个元素之后，如果这个元素比ins大，插入点就是这个元素所在的下标。我们不妨对比一下，这两行“如果”，那么插入点是什么就出来了：low或者high+1. 事实上，他们两个也是相等的，因此，用哪个都行。

后面还有一个二路插入排序和希尔排序。还没有将代码写出来，所以暂时跳过。：）

交换排序

接下来是交换排序。就是说，这类排序是通过交换两个元素来实现的。经典的冒泡排序就是交换排序的典型例子。

我们来看冒泡排序的代码：

Code:
  1. void BubbleSort(SqList &list){  
  2.       
  3.     int i,j;  
  4.     for (i=list.length-1;i>=0;i--)  
  5.         for (j=0;j<i;j++){  
  6.             if (Compare(list.r[j],list.r[j+1]) > 0 ) //If r[j]>r[j+1] then let r[j+1] move fowards.   
  7.                 Swap(list.r[j],list.r[j+1]);  
  8.         }  
  9.   
  10. }  

呵呵，很简单的一个算法。对算法的基本理解是：让大（或者小）的元素往数组后面走，第一次是就将最大的放到最后，然后将第二大的放在倒数第二个位置，以此类推。体现在算法中就是两层循环，外循环控制的是元素最终放置的位置，即从最后一个往前推，外层循环每完成一次，即有一个元素放置在后面。内层循环控制元素的“冒泡”。即从第一个元素一直到i-1,i是最终放置的位置。如果r[j]比r[j+1]大，就把他俩交换。这样最终肯定将前i个元素中最大的那个移动到i处。

接下来出场的是快速排序。快排被教科书上定性为拥有最佳平均性能的排序算法。那当然是要着重掌握的了。快速排序的核心观点是，如果能够将一个无序序列对一个点而言分成两段，在点的前面的一段中的所有元素都比该店的元素要小，而后段的所有元素都比该点的元素要大，而这个点称为pivot, 枢轴。如果能这样做的话，就可以不断对子序列进行同样操作，即递归的方法对一个无序序列进行排序了。

还是看看代码吧：

Code:
  1. void quickSort(SqList &list,int low ,int high){  
  2.   
  3.   
  4.     if (low < high) {  
  5.           
  6.         int pivot_location = partition(list,low,high);  
  7.         quickSort(list,low,pivot_location - 1 );  
  8.         quickSort(list,pivot_location + 1, high);  
  9.       
  10.     }  
  11. }  
  12.   
  13. int partition(SqList &list,int low,int high){  
  14.           
  15.     KeyType pivot_key = list.r[low];  
  16.       
  17.     while (low<high){  
  18.           
  19.         while (low<high && list.r[high] >= pivot_key ) high--;  
  20.         //Swap(list.r[low],list.r[high]);  
  21.         list.r[low] = list.r[high];  
  22.   
  23.         while (low<high && list.r[low] <= pivot_key) low++;  
  24.         //Swap(list.r[low],list.r[high]);  
  25.         list.r[high] = list.r[low];  
  26.         }  
  27.         list.r[low] = pivot_key;  
  28.         return low;  
  29. }  

主体很简单，就是一个递归调用，定义了一个头low，一个尾high，两个指针，表示的是序列的头尾。关键的函数是Partition，它负责对子序列进行分段，并且返回枢轴的位置。

所以重点还是在如何分段和计算枢轴，书上的算法是：取序列的第一个元素作为枢轴元素，然后从high，也就是序列的尾部从后往前找：high--，找到第一个小于枢轴元素的元素，然后将这个元素赋给r[low]；然后从序列的头部从前往后找：low++，将找到的第一个大于枢轴元素的元素赋给r[high]。重复着两个动作，直到low>=high，其实也就是low=high，最终跳出循环的条件肯定就是low和high指向同一个元素了。而这个元素所在的位置，应该是最后一个被找到并且的元素（不管是比枢轴元素大，还是比他小），而且，这个位置恰恰就是枢轴元素应该在的位置，所以将枢轴元素放回去，返回low或者high都可以。（二者相等）

看回这个方法本身，首先，令第一个元素为枢轴元素，然后从头和尾两端进行推压，将靠后的比枢轴元素小的元素往前挪，将靠前的比枢轴元素大的元素往后挪，通过前后元素的反复交换，从而最终得到一个对枢轴元素而言，分别较大和较小的序列。（个人感觉还是很玄妙的，而且仍然没有领悟到它的精髓，请大家指教哈）

选择排序

简单选择排序的策略是从i到n的序列中，选择里面最小（或者大）的元素放在i处。这是最最朴素的排序算法了。这没什么好说的了，贴代码完事：

Code:
  1. void SelectSort(SqList &list){  
  2.       
  3.     int i,j;  
  4.     int max_pointer;  
  5.     KeyType max;  
  6.       
  7.   
  8.     for (i=0;i<list.length-1;i++){  
  9.           
  10.         max = list.r[i];  
  11.         max_pointer = i;  
  12.   
  13.         for (j=i+1;j<list.length;j++)     
  14.             if (Compare(list.r[j],max) > 0 ) {  
  15.                   
  16.                  max = list.r[j];  
  17.                  max_pointer = j;  
  18.             }  
  19.   
  20.   
  21.         if (max_pointer!=i) Swap(list.r[i],list.r[max_pointer]);  
  22.   
  23.     }  
  24.       
  25. }  

重点是堆排序。

还是要说一下改进简单排序算法的思想。由于在选择最小/最大元素的过程，有许多重复的比较，这就为改进提供了可能。怎么重复法呢？比如A>B，B>C，那么肯定A>C，根本无需再做比较。这种排序思想就是锦标赛排序，就是说跟比赛的晋级是一样的道理，两两相比，强者晋级，然后这些强者再进行两两相比。结果就出现了二叉树的形状。

可以使用完全二叉树这种数据结构来实现，其中，每个非终端节点都是孩子结点中的较小者（或较大者），于是根节点上的就是最小或最大的元素。那如何实现排序输出呢？方法是首先输入根节点，然后将叶子节点中等于根节点的那个节点设为MAX（某个大值），然后再按照父节点是孩子节点中较小者（较大者）这个原则来重新调整二叉树。重复以上步骤，直到全部节点都输出完毕。

然而这个方法还是被批评辅助空间较多，与MAX进行多余比较。因此J.willioms在1964年提出了堆排序（我膜拜一下）。

堆排序，首先要介绍的是堆，这种数据结构，它是一棵完全二叉树（因此可以使用数组来实现），其中，堆中的所有的父亲节点都比它的两个孩子要大（或者小）

堆排序算法即是利用了堆这种数据结构，以大头堆为例（即父节点比孩子节点都大的堆）如果存在这样的堆，则根节点一定是最大的元素，将其输出，然后对剩余的n-1个结点重新进行堆重建，结果得到的堆的根节点就是次大的元素。重复执行上述步骤，即可完成堆排序。

那如何建立堆呢？这个问题是最关键的。

思想很简单，对一棵无序的完全二叉树，从最后一个非终端节点开始到根节点进行调整，将父节点与孩子节点中最大的那个交换。当然如果父亲节点已经是三者中最大的那个，就当然不用换了。如果发生了交换，需要注意，交换后的孩子节点（他可能也是某子树中的父亲节点）有没有破坏堆的性质，如果有，则需要继续进行调整，直到到达终端节点。

按照上面的步骤得到一个堆之后，还需要进一步的调整，已使之成为一个有序的完全二叉树。如何办到呢？方法是，将根节点，即最大的元素，与二叉树中最后的节点交换，这就等于说，将最大的元素放到最后。然后对1-n-1的完全二叉树进行堆调整。因为是对1-n-1这些节点进行调整，所以最大的元素已经被排除在外了。然后调整后，又得到一个次大的元素，又可以将其放置在n-1的位置上，将n-1位置上原来的元素放在堆顶。依此步骤重复，直到最后堆剩一个元素。至此完全二叉树有序。

来看看代码吧：

Code:
  1. void heapSort(HeapList &list){  
  2.       
  3.     int i ;  
  4.     for (i=list.length/2-1;i>=0;i--){  
  5.         heapAdjust(list,i,list.length-1);     
  6.     }  
  7.       
  8.     for (i=list.length-1;i>=0;i--){  
  9.         Swap(list.r[0],list.r[i]);  
  10.         heapAdjust(list,0,i-1);  
  11.   
  12.     }  
  13.   
  14. }  
  15.   
  16. void heapAdjust(HeapList &list,int first,int last){  
  17.       
  18.     int j;  
  19.       
  20.     for (j=(first+1)*2-1 ; j<=last; j=(j+1)*2-1){  
  21.           
  22.         if ( j<last && Compare(list.r[j],list.r[j+1])<0  ) j++; //this means select the bigger one between r[j] and r[j+1]  
  23.           
  24.       
  25.         if ( Compare(list.r[first],list.r[j])>0 ) {   
  26.             break;   
  27.         }   
  28.           
  29.         Swap(list.r[first],list.r[j]);  
  30.         first=j;  
  31.     }  
  32.   
  33.   
  34. }  

需要注意的是在函数heapAdjust中，由于我处理的完全二叉树是从下标0开始的，所以对左孩子进行定位时，语句是：j=(j+1)*2-1。

归并排序

归并排序是基于一种归并的思想，即对两个分别有序的序列，可以进行一种归并的操作，使这两段序列合并成有序的一段。算法也很简单，即从头到尾比较两个序列，将小的元素放在新的序列中，知道某一段序列结束，然后将另一段序列中剩下的元素全部拷贝到新序列中，算法结束。代码如下：

Code:
  1. typedef struct{  
  2.     KeyType r[MAX_LENGTH];  
  3.     int length;  
  4. }SqList_ex;  

以上是数据结构，注意结构体中的数组不能用指针。为什么，下面会详述。

Code:
  1. void Merge(SqList_ex source,SqList_ex &target, int seg1,int seg1_end,int seg2_end){  
  2.       
  3.     int i,j;  
  4.     int k=seg1;  
  5.     for (i=seg1,j=seg1_end+1; i<=seg1_end&&j<=seg2_end; ) {  
  6.           
  7.         if (Compare (source.r[i], source.r[j]) <0 ) target.r[k++]=source.r[i++];  
  8.         else target.r[k++]=source.r[j++];
  9.   
  10.     }  
  11.     if (i<=seg1_end)   
  12.         for (;i<=seg1_end;i++) {  
  13.             target.r[k++]=source.r[i];  
  14.         }  
  15.     if (j<=seg2_end)  
  16.         for (;j<=seg2_end;j++) {  
  17.             target.r[k++]=source.r[j];  
  18.         }  
  19.       
  20. }  

算法是很简单的，需要解释的是几个参数，呵呵。

source是需要被合并的结构体（里面包含了一个数组和它的长度），target是合并后的结构体。seg1，seg1_end是source中数组第一段的起始下表和结束下标，seg1_end+1到seg2_end是第二段的起始下标和结束下标。注意它们是分别有序的两段序列。

这个不是重点，重点是source和target。看看这个函数是怎样调用的：

Code:
  1. Merge(list,list,head,mid,tail);  

source跟target的实参都是同一个list结构体！有人会问，这怎么回事啊。自己跟自己归并，最后又是写回自己上，不会出错吗？

这里就涉及C语言参数传递和C++的引用了。

因为C语言的参数传递基本都是值传递（还有一中是指针传递，这里不涉及，所以就不说了~）结构体参数也是值传递，因此，在Merge函数中，作为实参传进来的list变量已经被拷贝到内存的另一块地方了，而它的新名字叫做source。 再看看我们的target，虽然传进来的实参仍然是list，但是，由于target是一个引用变量，也就是说，进行参数传递，或者说形参初始化的时候，只会对这个引用变量target进行赋值，即SqList &target=list，这时候，target就像是list另一个名字一样，因此对target进行修改，就恰恰是对list进行修改。 总的来说，在Merge的过程中，源数组先拷贝了一份，放在别的一个地方，然后进行归并并且将结果写回到原来的数组上。这样就保证了归并过程是有效的。

有一点有趣的事情可以跟大家分享一下，在我原来定义的数据结构中SqList（看回本文开始的地方），数组并不是使用[]的定义方式，而是使用了指针，因为指针更能节省内存，不需要开辟长度为MAX_LENGTH这么大的内存空间。但是在写归并排序的过程中，我发现，使用指针的顺序表数据结构是行不通的。 上面代码都一点不变，但是使用数组指针的结构体

Code:
  1. 1. typedef int KeyType;    
  2. 2.     
  3. 3. typedef struct{    
  4. 4.     KeyType *r;    
  5. 5.     int length;    
  6. 6. }SqList;    
就是会出错。为什么呢？呵呵，跟对象的深浅克隆有异曲同工之妙的。 大家不妨想想是不是？
完整的代码放上来：
Code:
  1. void mergeSort(SqList_ex &list,int head ,int tail){  
  2.       
  3.     int mid;  
  4.       
  5.     if (head == tail) return;  
  6.     mid = (head + tail) / 2;  
  7.       
  8.     mergeSort(list,head,mid);  
  9.     mergeSort(list,mid+1,tail);  
  10.       
  11.     Merge(list,list,head,mid,tail);  
  12.       
  13. } 
整个归并排序的过程就是一个递归的过程。将无序序列分成两段，因为他们还是无序的，因此对他们进行递归的再次归并排序，当他们都归并有序后，再进行Merge的归并操作即可。
反回来说，就是先把相邻的两个元素进行合并（它们长度为1，肯定分别有序），然后再将相邻的2个有序的长度为2的子序列进行合并，最终实现整个序列的有序化。这个方法其实真名是二路归并排序。其实还有多路归并排序，不过属于外部排序的范畴，以后再写一篇学习日志了。
 

to be con..

标签：

相关文章