sort.cpp

几个小排序

#include <iostream.h>


/*
快速排序思想：
快速排序是分治思想的一种应用，它先选取一个支点，然后把小于支点的元素交换
到支点的前边，把大于支点的元素交换到支点的右边。然后再对支点左边部分和右
边部分进行同样的处理，这样若干次之后，数据就会变得有序。

  下面的实现使用了递归
  建立两个游标：iLow，iHigh；iLow指向序列的第一个元素，iHigh指向最后一个
  
	先选第一个元素作为支点，并把它的值存贮在一个辅助变量里。那么第一个位置就
	变为空并可以放置其他的元素。 这样从iHigh指向的元素开始向前移动游标iHigh
	查找比支点小的元素，如果找到，则把它放置到空置了的位置（现在是第一个位置）
	
	  然后iHigh游标停止移动，这时iHigh指向的位置被空置，然后移动iLow游标寻找比
	  支点大的元素放置到iHigh指向的空置的位置，如此往复直到iLow与iHigh相等。
	  最后使用递归对左右两部分进行同样处理
*/
int QuickSort(long* Array, int iLow, int iHigh)//快速排序
{
    if(iLow >= iHigh) return 1; //递归结束条件
    long pivot = Array[iLow];
    int iLowSaved = iLow, iHighSaved = iHigh; //保未改变的iLow，iHigh值保存起来
    while (iLow < iHigh)
    {
        while (Array[iHigh] >= pivot && iHigh > iLow) //寻找比支点大的元素
			iHigh -- ;
        Array[iLow] = Array[iHigh]; //把找到的元素放置到空置的位置
        while (Array[iLow] < pivot && iLow < iHigh) //寻找比支点小的元素
			iLow ++ ;
        Array[iHigh] = Array[iLow]; //把找到的元素放置到空置的位置
    }
    Array[iLow] = pivot; //把支点值放置到支点位置，这时支点位置是空置的
    //对左右部分分别进行递归处理
    QuickSort(Array, iLowSaved, iHigh-1);
    QuickSort(Array, iLow+1, iHighSaved);
    return 0;
}

/*
冒泡排序思想(升序，降序同理，后面的算法一样都是升序):
从头到尾对数据进行两两比较进行交换,小的放前大的放后。
这样一次下来，最大的元素就会被交换的最后，然后下一次
循环就不用对最后一个元素进行比较交换了，所以呢每一次
比较交换的次数都比上一次循环的次数少一，这样N次之后
数据就变得升序排列了
*/
void bubblesort(long a[],int length)//冒泡排序
{
  long i,temp;
  for(int pass=1;pass<length;pass++)//共比较length-1轮
  {
    for(i=0;i<length-pass;i++)//比较一轮
	{
		if(a[i]>a[i+1])//一次交换
		{
			temp=a[i];
			a[i]=a[i+1];
			a[i+1]=temp;
		}
	}

  }
}
/*
选择排序思想:
每一次都从无序的数据中找出最小的元素，然后和前面已经有序的元素序列
的后一个元素进行交换，这样整个源序列就会分成两部分，前面一部分是已经
排好序的有序序列，后面一部分是无序的，用于选出最小的元素。
循环N次之后，前面的有序序列加长到跟源序列一样长，后面的无序部分长度变
为0，排序就完成了。
*/
void SelectSort(long Array[],int iLength)//选择排序
{
   
    long lMin, lSwap;
    int i, j, iMinPos;
    for(i=0; i < iLength-1; i++)
    {
		lMin = Array[i];
		iMinPos = i;
		for(j=i + 1; j <= iLength-1; j++) //从无序的元素中找出最小的元素
		{
			if(Array[j] < lMin)
			{
				iMinPos = j;
				lMin = Array[j];
			}
		}
		//把选出的元素交换拼接到有序序列的最后
		lSwap = Array[i];
		Array[i] = Array[iMinPos];
		Array[iMinPos] = lSwap;
    }
   
}
/*
插入排序思想：
把源数据序列看成两半，前面一半是有序的，后面一半是无序的，把无序的数据从头到尾
逐个逐个的插入到前面的有序数据中，使得有序的数据的个数不断增大，同时无序的数据
个数就越来越少，最后所有元素都会变得有序。
*/
void InsertSort(long Array[],int iLength )
{
	
	
	int i=1, j=0;
	long temp;
	for(i=1; i<iLength; i++)
	{
		temp = Array[i];   //取出序列后面无序数据的第一个元素值
		for(j=i; j>0; j--) //和前面的有序数据逐个进行比较找出合适的插入位置
		{
			if(Array[j - 1] > temp)  //如果该元素比插入值大则后移
				Array[j] = Array[j - 1];
			else //如果该元素比插入值小，那么该位置的后一位就是插入元素的位置
				break;   
		}
		Array[j] = temp;
	}
	
	
}


/*
堆排序思想：
堆：数据元素从1到N排列成一棵二叉树，而且这棵树的每一个子树的根都是该树
中的元素的最小或最大的元素
这样如果一个无序数据集合是一个堆那么，根元素就是最小或最大的元素
堆排序就是不断对剩下的数据建堆，把最小或最大的元素析透出来。

  下面的算法，就是从最后一个元素开始，依据一个节点比父节点数值大的原则对
  所有元素进行调整，这样调整一次就形成一个堆，第一个元素就是最小的元素。
  然后再对剩下的无序数据再进行建堆，注意这时后面的无序数据元素的序数都
  要改变，如第一次建堆后，第二个元素就会变成堆的第一个元素。
*/
void HeapSort(long Array[],int iLength)
{
	
	
	int i, j, p;
	long swap;
	
	for(i=0; i<iLength-1; i++)
	{
		for(j = iLength - 1; j>i; j--) //从最后倒数上去比较字节点和父节点
		{
			p = (j - i - 1)/2 + i;   //计算父节点数组下标
			//注意到树节点序数跟数组下标不是等同的，因为建堆的元素个数逐个递减
			
			if(Array[j] < Array[p])  //如果父节点数值大则交换父节点和字节点
			{
				swap = Array[j];
				Array[j] = Array[p];
				Array[p] = swap;
			}
		}
	}
	
	
}

void main()
{
	////////////////////////////////////////////////////////////////////////
	long a[10]={11,22,8,9,7,5,7,1000,12,3};
	QuickSort(a,0,9);
	for(int i=0;i<10;i++)
	{
	
	cout<<a[i]<<"  ";
	}
	cout<<endl;
	///////////////////////////////////////////////////////////////////////
	long b[10]={11,22,8,9,7,5,7,1000,12,3};
	bubblesort(b,10);
	
    for(i=0;i<10;i++)
	{
		
		cout<<b[i]<<"  ";
	}
	cout<<endl;
	////////////////////////////////////////////////////////////////////
	long c[10]={11,22,8,9,7,5,7,1000,12,3};
	SelectSort(c,10);
	
    for(i=0;i<10;i++)
	{
		
		cout<<c[i]<<"  ";
	}

	cout<<endl;
	//////////////////////////////////////////////////////////////////
	long d[10]={11,22,8,9,7,5,7,1000,12,3};
	InsertSort(d,10);
	
    for(i=0;i<10;i++)
	{
		
		cout<<d[i]<<"  ";
	}
	cout<<endl;
	////////////////////////////////////////////////////////////////////
	long e[10]={11,22,8,9,7,5,7,1000,12,3};
	HeapSort(e,10);
	
    for(i=0;i<10;i++)
	{
		
		cout<<e[i]<<"  ";
	}
	cout<<endl;
}