STL经典算法集锦<八>之Int-STL经典算法我实现

STL经典算法集锦<八>之IntroSort

STL的sort算法的优化策略：

1、数据量大时采用QuickSort，分段递归排序。

2、一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来的额外负荷，就改用Insertion Sort。

3、如果层次过深，还会改用HeapSort

4、 “三点中值”获取好的分割

IntroSort的实现代码为：

//数据量的分界线，决定了使用quick sort/heap sort还是insertion sort
const int threshold=16;

//堆排序用到的辅助函数
int parent(int i)
{
    return (int)((i-1)/2);
}
 
int left(int i)
{
    return 2 * i+1;
}
 
int right(int i)
{
    return (2 * i + 2);
}
 
void heapShiftDown(int heap[], int i, int begin,int end)
{
    int l = left(i-begin)+begin;
    int r = right(i-begin)+begin;
    int largest=i;
	//找出左右字节点与父节点中的最大者
    if(l < end && heap[l] > heap[largest])
        largest = l;
    if(r < end && heap[r] > heap[largest])
        largest = r;
	//若最大者不为父节点，则需交换数据，并持续向下滚动至满足最大堆特性
    if(largest != i)
    {
		swap(heap[largest],heap[i]);
        heapShiftDown(heap, largest, begin,end);
    }
}
 //自底向上的开始建堆，即从堆的倒数第二层开始
void buildHeap(int heap[],int begin,int end)
{
    for(int i = (begin+end)/2; i >= begin; i--)
    {
        heapShiftDown(heap, i, begin,end);
    }
}
 
 //堆排序
void heapSort(int heap[], int begin,int end)
{
    buildHeap(heap,begin,end);
    for(int i = end; i >begin; i--)
    {
		swap(heap[begin],heap[i]);
        heapShiftDown(heap,begin,begin, i);
    }
}

//插入排序
void insertionSort(int array[],int len)
{
    int i,j,temp;
    for(i=1;i<len;i++)
    {
      temp = array[i];//store the original sorted array in temp
      for(j=i;j>0 && temp < array[j-1];j--)//compare the new array with temp(maybe -1?)
      {
          array[j]=array[j-1];//all larger elements are moved one pot to the right
      }
      array[j]=temp;
    }
}

//三点中值
int median3(int array[],int first,int median,int end)
{
		if(array[first]<array[median])
		{
				if(array[median]<array[end])
						return median;
				else if(array[first]<array[end])
						return end;
				else
						return first;
		}
		else if(array[first]<array[end])
				return first;
		else if(array[median]<array[end])
				return end;
		else 
				return median;
}

//对数组分割
int partition(int array[],int left,int right,int p)
{
		//选择最右侧的元素作为分割标准
		int index = left;
		swap(array[p],array[right]);
		int pivot = array[right]; 
	    //将所有小于标准的点移动到index的左侧	
        for (int i=left; i<right; i++)
        {
                if (array[i] < pivot)    
                        swap(array[index++],array[i]);
        }
		//将标准与index指向的元素交换，返回index，即分割位置
        swap(array[right],array[index]);
        return index;
}

//递归的对数组进行分割排序
void introSortLoop(int array[],int begin,int end,int depthLimit)
{
		while((end-begin+1)>threshold) //子数组数据量大小，则交给后面的插入排序进行处理
		{
				if(depthLimit==0)      //递归深度过大，则由堆排序代替
				{
						heapSort(array,begin,end);
						return ;
				}
				--depthLimit;
				//使用quick sort进行排序
				int cut=partition(array,begin,end,
								median3(array,begin,begin+(end-begin)/2,end)); 
				introSortLoop(array,cut,end,depthLimit);
				end=cut;    //对左半段进行递归的sort
		}
}

//计算最大容忍的递归深度
int lg(int n)
{
		int k;
		for(k=0;n>1;n>>=1) ++k;
		return k;
}

//霸气的introsort
void introSort(int array[],int len)
{
		if(len!=1)
		{
				introSortLoop(array,0,len-1,lg(len)*2);
				insertionSort(array,len);
		}
}

注：更多关于STL原版IntroSort的实现的可以参考：
http://blog.csdn.net/xinhanggebuguake/article/details/7547066

结篇想说的话：从去年二月份开始看《STL源码剖析》，到今年年初看SGI STL2.91版本的代码，再到最近亲自把所有重点代码自己实现，此期间经历了太长的时间。当然在学习STL的过程中自己也取得了长足的进步。STL之经典毋庸置疑，经历了书籍，源码，自己实现的一个过程，觉得能把这个过程坚持下来的人不会太多，而自己是其中一个，怎能不骄傲。在这个找实习的季节里屡屡倍受打击，也只有这样的一份坚持，让我坚信付出终有回报，加油。

STL经典算法集锦&lt;八&gt;之Int

STL经典算法集锦<八>之IntroSort

STL经典算法集锦<八>之Int